The Taub Faculty of Computer Science Events and Talks

Stream monitoring is fundamental in many data stream applications, such as financial data trackers, security, anomaly detection, and load balancing. To cope with high-speed data streams, these applications require algorithms that are both time and space efficient to cope with high-speed data streams. Space efficiency is needed due to the memory hierarchy structure, to enable cache residency and to avoid page swapping. Even if the potential computing cost is low, this residency is critical for good performance (e.g., constant time algorithms may be inefficient if they access the DRAM for each element). To that end, stream processing algorithms often build compact approximate sketches (synopses) of the input streams. This work improves the speed and space requirements for streaming problems.