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.00037726596 |
| 270 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029648047 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.0002737538 |
| 398 | Mergeable Summaries | 2012 | PODS | 0.00024383201 |
| 1,485 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011698762 |
| 3,902 | Tight bounds for 2-dimensional indexing schemes | 1998 | PODS | 6.6454492e-05 |
| 5,010 | A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries | 1998 | PODS | 5.7545425e-05 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,065 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014344675 |
| 114 | Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries | 1988 | SIGMOD | 0.00046317654 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.0002737538 |
| 63 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063595699 |
| 8,893 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD | 4.4232868e-05 |
| 3,621 | Fast Algorithms For Hierarchical Range Histogram Construction | 2002 | PODS | 6.9022467e-05 |
| 5,832 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.3085972e-05 |
| 838 | Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data | 2001 | SIGMOD | 0.00016024923 |
| 995 | Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes | 2000 | SIGMOD | 0.00014745185 |
| 849 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015919478 |