Frequency Estimation of Internet Packet Streams with Limited Space

By Erik D. Demaine, A. López-Ortiz, J. Ian Munro. Embedded Systems and Applications, 2002

525 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/ece890238d1cbc2bdd707cfea7e9877083d6e944

How researchers see this paper

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

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Taming the underlying challenges of reliable multihop routing in sensor networks (2003, methodology): “Finally, [6] showed a simple FREQUENCY algorithm that estimates frequency of Internet packet streams with limited space.”
Private and Continual Release of Statistics (2010, background): “The basic idea is to release two types of noisy p-sums: 1) a noisy p-sum for every item, that is, Σ̂[1, 1], Σ̂[2, 2], .”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, methodology): “The sampling algorithm Probabilistic-InPlace [17] solves FindCandidateTop(S, k, m 2 ) by using m counters.”
What's hot and what's not: tracking most frequent items dynamically (2003, methodology): “The recall of the Frequent algorithm looks reasonably good especially as time progresses, but its precision, which begins poorly, appears to degrade further.”
Approximate counts and quantiles over sliding windows (2004, methodology): “The same algorithm has been rediscovered recently by Demaine et al [10] and Karp et al [16], who reduced the processing time to O(1) in the worst case.”
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams (2009, methodology): “Gilbert et al. [9] gave an algorithm for the model in which elements may also be “deleted” from the stream.”
Real-time Power-Aware Routing in Sensor Networks (2006, methodology): “Similar to MT [7], we use the FREQUENCY algorithm [14] to manage the neighbor table.”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, methodology): “The MG algorithm was rediscovered several times [6, 14].”
Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, background): “The sample-based approaches keep track of counters [14, 28, 34].”
Issues in data stream management (2003, unknown): “[25, 40, 54].”
Finding Hierarchical Heavy Hitters in Data Streams (2003, background): “A heavy hitter (HH) is an element whose frequency in a data set is no smaller than a user-supplied threshold; the problem of (cid:12)nding HHs in data streams has been studied extensively [3, 6, 16, 22, 4].”