Histograms Revisited: When are histograms the best approximation method for aggregates over joins?
Summary: Replace the uniform-bucket assumption with a weaker “random arrangement” model, showing it yields the same histogram approximation formulas and permits tight error bounds. Characterize input regimes where histograms beat sampling/sketching for join-aggregate approximation and where they fail on average. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Alin Dobra
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,981 | Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses | 2018 | VLDB | 9.8687545e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 18 | On Random Sampling over Joins | 1999 | SIGMOD | 0.00092385438 |
| 28 | Accurate Estimation Of The Number Of Tuples Satisfying A Condition | 1984 | SIGMOD | 0.00080435857 |
| 99 | On the Propagation of Errors in the Size of Join Results | 1991 | SIGMOD | 0.00050022914 |
| 327 | Balancing Histogram Optimality and Practicality for Query Result Size Estimation | 1995 | SIGMOD | 0.00027308479 |
| 549 | Tracking Join and Self-Join Sizes in Limited Storage | 1999 | PODS | 0.00020376603 |
| 808 | Universality of Serial Histograms | 1993 | VLDB | 0.00016432772 |
| 1,064 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014356481 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 530 | Random Sampling for Histogram Construction: How much is enough? | 1998 | SIGMOD | 0.00020803682 |
| 8,893 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD | 4.4275272e-05 |
| 5,879 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.2908101e-05 |
| 1,064 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD | 0.00014356481 |
| 808 | Universality of Serial Histograms | 1993 | VLDB | 0.00016432772 |
| 269 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029656549 |
| 996 | Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes | 2000 | SIGMOD | 0.00014741524 |
| 327 | Balancing Histogram Optimality and Practicality for Query Result Size Estimation | 1995 | SIGMOD | 0.00027308479 |
| 361 | Histogram-Based Approximation of Set-Valued Query Answers | 1999 | VLDB | 0.00025775749 |