@inproceedings{ca5c7c94b1ff4fbbba5df5899f53b2ed,
title = "A simpler and more efficient deterministic scheme for finding frequent items over sliding windows",
abstract = "In this paper, we give a simple scheme for identifying ε-approximate frequent items over a sliding window of size n. Our scheme is deterministic and does not make any assumption on the distribution of the item frequencies. It supports O(1/ε) update and query time, and uses O(1/ε) space. It is very simple; its main data structures are just a few short queues whose entries store the position of some items in the sliding window. We also extend our scheme for variable-size window. This extended scheme uses O(1/ε log(εn)) space.",
keywords = "Data mining, Frequent items, Network monitoring, Streaming algorithms",
author = "Lee, \{L. K.\} and Ting, \{H. F.\}",
year = "2006",
month = jun,
day = "26",
doi = "10.1145/1142351.1142393",
language = "English",
isbn = "1595933182",
series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
pages = "290--297",
booktitle = "Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006",
note = "25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006 ; Conference date: 26-06-2006 Through 28-06-2006",
}