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
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 |
|---|---|---|---|---|
| 178 | Boosting the Accuracy of Differentially Private Histograms Through Consistency | 2010 | VLDB | 0.00037697111 |
| 269 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029656549 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 402 | Mergeable Summaries | 2012 | PODS | 0.00024196343 |
| 1,488 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011699446 |
| 3,900 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.6518011e-05 |
| 5,013 | A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries | 1998 | PODS | 5.7598528e-05 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,064 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014356481 |
| 116 | Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries | 1988 | SIGMOD | 0.00046148737 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 64 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063612837 |
| 8,893 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD | 4.4275272e-05 |
| 3,619 | Fast Algorithms For Hierarchical Range Histogram Construction | 2002 | PODS | 6.9084829e-05 |
| 5,879 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.2908101e-05 |
| 842 | Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data | 2001 | SIGMOD | 0.00016031973 |
| 996 | Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes | 2000 | SIGMOD | 0.00014741524 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |