Paper by Erik D. Demaine

Reference:

Lukasz Golab, David DeHaan, Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro, “Identifying Frequent Items in Sliding Windows over On-Line Packet Streams”, in Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC 2003), Miami, Florida, October 27–29, 2003, pages 173–178.

Abstract:

Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring items are important in the analysis of real-time Internet packet streams. While several results exist for computing frequent item queries using limited memory in the infinite stream model, in this paper we consider the limited-memory sliding window model. This model maintains the last N items that have arrived at any given time and forbids the storage of the entire window in memory. We present a deterministic algorithm for identifying frequent items in sliding windows to find over real-time packet streams. The algorithm uses limited memory, requires constant processing time per packet (amortized), makes only one pass over the data, and is shown to work well when tested on TCP traffic logs.

Length:

The paper is 6 pages.

Availability:

The paper is available in PostScript (378k), gzipped PostScript (127k), and PDF (171k).

See information on file formats.

[Google Scholar search]

Related papers:

NetworkStats_ESA2002 (Frequency Estimation of Internet Packet Streams with Limited Space)