Data-Independent Space Partitionings for Summaries
Summary: Poses continuous binning: select a small set of data-independent multidimensional bins (possibly overlapping) so query boxes can be approximated by additive composition, avoiding a single equiwidth grid. Defines quality metrics, shows NP-hardness, and gives algorithms (including synthetic point-set construction) for compact multi-histogram summaries that improve range-query accuracy while supporting dynamic updates and privacy-preserving publishing. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Graham Cormode (University of Warwick)
- 2. Minos Garofalakis (ATHENA Research Center)
- 3. Michael Shekelyan (King's College London)
BibTeX Citation
@inproceedings{cormode_pods21,
address = {New York, NY, USA},
series = {{PODS} '21},
title = {{Data-Independent Space Partitionings for Summaries}},
url = {https://dl.acm.org/doi/10.1145/3452021.3458316},
doi = {10.1145/3452021.3458316},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Cormode, Graham and Garofalakis, Minos and Shekelyan, Michael},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 121 | Boosting the Accuracy of Differentially Private Histograms Through Consistency | 2010 | VLDB | 0.00031639377 |
| 235 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00023783792 |
| 267 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00022798161 |
| 451 | Mergeable Summaries | 2012 | PODS | 0.00018151445 |
| 1,512 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00010536001 |
| 3,972 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.9814651e-05 |
| 4,730 | A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries | 1998 | PODS | 6.5348792e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 817 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD |
| 2 | 118 | Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries | 1988 | SIGMOD |
| 3 | 267 | Optimal Histograms with Quality Guarantees | 1998 | VLDB |
| 4 | 35 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD |
| 5 | 8,998 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD |
| 6 | 4,889 | Fast Algorithms For Hierarchical Range Histogram Construction | 2002 | PODS |
| 7 | 5,421 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS |
| 8 | 692 | Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data | 2001 | SIGMOD |
| 9 | 850 | Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes | 2000 | SIGMOD |
| 10 | 723 | Dynamic Multidimensional Histograms | 2002 | SIGMOD |