Efficient Computation of Frequent and Top-k Elements in Data Streams

By Ahmed Metwally, D. Agrawal, A. El Abbadi. International Conference on Database Theory, 2005

823 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/72f15aba2e67b1cc9cd1fb12c99e101c4c1aae4b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Hong Cheng
2. Jiawei Han
3. Elaine Shi
4. Xifeng Yan
5. Dong Xin
6. Peter Bailis
7. D. Narayanan
8. T-H. Hubert Chan

In Computer Networks and Communications

1. Hong Cheng
2. Jiawei Han
3. Xifeng Yan
4. Elaine Shi
5. T-H. Hubert Chan
6. Dong Xin
7. Michael M. Mitzenmacher
8. Rui Miao

In Signal Processing

1. Hong Cheng
2. Jiawei Han
3. Dong Xin
4. Xifeng Yan
5. Michael M. Mitzenmacher
6. Srinivas Narayana
7. Qun Huang
8. Jennifer Rexford

Citations in the corpus

• Heavy-Hitter Detection Entirely in the Data Plane (2016, methodology): “Further, maintaining data structures like sorted linked lists [28] or priority queues [41] requires multiple memory accesses within the per-packet time budget.”
• Private and Continual Release of Statistics (2010, background): “The counter is also an important primitive in numerous data streaming algorithms [2, 14, 16].”
• MacroBase: Analytic Monitoring for the Internet of Things (2016, methodology): “In MacroBase, we leverage techniques from the sketching and streaming literature [14], specifically in our AMC sketch [16, 37] and FDR sampler [12,19].”
• PINT: Probabilistic In-band Network Telemetry (2020, methodology): “We can then use a heavy hitters algorithm like Space Saving [50] to estimate the frequency of values in the sampled substream to within an additive error of ε a , using O ( ε − 1 a ) space.”
• Frequent pattern mining: current status and future directions (2007, methodology): “Metwally et al. proposed a method for computing frequent and top-k elements in data streams by carefully using buffer space (Metwally et al. 2005).”
• TIME SERIES DATA MINING (2010, methodology): “In that case, we provide an approximation of the Top-K patterns using the Space Saving algorithm (Metwally et al. 2005) applied to the frequent time series patterns scenario.”
• MacroBase: Prioritizing Attention in Fast Data (2016, methodology): “Initially, we implemented the MDP item counter using the SpaceSaving algorithm [59], which provides empirically good performance [26] and has extensions in the exponentially decayed setting [27].”
• Elastic sketch: adaptive and fast network-wide measurements (2018, methodology): “• Heavy hitter detection:We compare six approaches: SpaceSaving (SS) [15], Count/CM sketch [10, 14] with a minheap (CountHeap/CMHeap), UnivMon [2], HashPipe [16] and Elastic.”