A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows

Summary: Deterministic, distribution-free scheme for ε-approximate frequent items over sliding windows using a few short position-queues, emphasizing extreme simplicity. Achieves O(1/ε) update/query and O(1/ε) space (variable-size window: O((1/ε)·log(εn))). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1400
Venue: PODS
Year: 2006
Pagerank: 8.1006881e-05
Overall Rank: 2,808 | 80.74%
DOI: 10.1145/1142351.1142393

Incoming Non-self Citations Over Time

Authors

1. L.K. Lee (University of Hong Kong)
2. H.F. Ting (University of Hong Kong)

BibTeX Citation

@inproceedings{lee_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142393},
        doi = {10.1145/1142351.1142393},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lee, L.K. and Ting, H.F.},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
5,802	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	6.0843083e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05
7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.5422948e-05
8,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.4574671e-05
8,603	Stream Frequency over Interval Queries	2019	VLDB	5.4041343e-05
9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	5.2755515e-05
10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB
2	2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS
3	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
4	12,629	Variance Estimation over Sliding Windows	2007	PODS
5	8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB
6	8,603	Stream Frequency over Interval Queries	2019	VLDB
7	122	Approximate Frequency Counts over Data Streams	2002	VLDB
8	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
9	885	Finding Frequent Items in Data Streams	2008	VLDB
10	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS