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: h966fff484e9274a8
Venue: PODS
Year: 2016
Pagerank: 5.3942942e-05
Overall Rank: 8,094 | 45.59%
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,684	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	4.9793485e-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.00064420972
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.0003006035
6,121	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8800995e-05

Semantically Similar Papers

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