Space Lower Bounds for Itemset Frequency Sketches

Summary: Shows space lower bounds for approximate itemset frequency estimation and threshold (frequent-itemset) detection: there exist database families forcing any sketch to be as large as a uniform sample. Hence uniform sampling is space-optimal up to constant or iterated-log factors. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1672
Venue: PODS
Year: 2016
Pagerank: 5.5181056e-05
Overall Rank: 7,926 | 45.63%
DOI: 10.1145/2902251.2902278

Incoming Non-self Citations Over Time

Authors

1. Edo Liberty (Yahoo)
2. Michael Mitzenmacher (Harvard University)
3. Justin Thaler (Yahoo)
4. Jonathan Ullman (Northeastern University)

BibTeX Citation

@inproceedings{liberty_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Space Lower Bounds for Itemset Frequency Sketches}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902278},
        doi = {10.1145/2902251.2902278},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Liberty, Edo and Mitzenmacher, Michael and Thaler, Justin and Ullman, Jonathan},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,368	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	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
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006567919
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB
2	8,551	Computational Complexity of Itemset Frequency Satisfiability	2004	PODS
3	122	Approximate Frequency Counts over Data Streams	2002	VLDB
4	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
5	885	Finding Frequent Items in Data Streams	2008	VLDB
6	7,918	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS
7	12,176	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
8	7,657	Mining Frequent Itemsets over Uncertain Databases	2012	VLDB
9	8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB
10	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS