Paper by Erik D. Demaine
- 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.
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.
- The paper is 6 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by