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.

BibTeX

@InProceedings{SlidingWindow_IMC2003,
  AUTHOR        = {Lukasz Golab and David DeHaan and Erik D. Demaine and
                   Alejandro L\'opez-Ortiz and J. Ian Munro},
  TITLE         = {Identifying Frequent Items in Sliding Windows over On-Line
                   Packet Streams},
  BOOKTITLE     = {Proceedings of the ACM SIGCOMM Internet Measurement
                   Conference (IMC 2003)},
  bookurl       = {http://www.icir.org/vern/imc-2003/},
  ADDRESS       = {Miami, Florida},
  MONTH         = {October 27--29},
  YEAR          = 2003,
  PAGES         = {173--178},

  length        = {6 pages},
  papers        = {NetworkStats_ESA2002; SlidingWindow_SSDBM2004},
  doi           = {https://dx.doi.org/10.1145/948205.948227},
  dblp          = {https://dblp.org/rec/conf/imc/GolabDDLM03},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1145/948205.948227">ACM</A>.},
}

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.

Comments:

This paper is also available from ACM.

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)

SlidingWindow_SSDBM2004 (Finding Frequent Items in Sliding Windows with Multinomially-Distributed Item Frequencies)