Deterministic K-Set Structure

Summary: Deterministic k-set algorithm for insertion-deletion streams that outputs the exact (item,frequency) set when distinct items ≤ k and nil otherwise. Space matches the information-theoretic lower bound up to a logarithmic factor, yielding a deterministic near-optimal structure. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1400
Venue: PODS
Year: 2006
Pagerank: 4.1945683e-05
Overall Rank: 12,490 | 13.11%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Sumit Ganguly
2. Anirban Majumder

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
3,838	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD	6.7134945e-05
11,329	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	4.1945683e-05
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
2,759	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1636123e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05