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)
Incoming Non-self Citations Over Time
Authors
- 1. Edo Liberty
- 2. Michael Mitzenmacher
- 3. Justin Thaler
- 4. Jonathan Ullman
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,162 | Towards Better Bounds for Finding Quasi-Identifiers * | 2023 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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.0010864752 |
| 111 | Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release | 2007 | PODS | 0.00047073785 |
| 166 | Approximate Frequency Counts over Data Streams | 2002 | VLDB | 0.00039361552 |
| 5,902 | The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication | 2015 | PODS | 5.2796864e-05 |
Previous
Page 1 / 1
Next