DBScholar

Back to papers

Fast Incremental Maintenance of Approximate Histograms

Summary: Sampling-based incremental maintenance keeps equi-depth and Compressed histograms continuously current, scheduling work only when needed for orders-of-magnitude better cardinality estimates. An efficiently maintained up-to-date uniform backing sample also generalizes to dynamic-sampling applications. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h9f11f3d0d758622f
Venue
VLDB
Year
1997
Pagerank
0.00023327437
Overall Rank
242 | 98.38%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gibbons_vldb97,
        title = {{Fast Incremental Maintenance of Approximate Histograms}},
        author = {Gibbons, Phillip B. and Matias, Yossi and Poosala, Viswanath},
        journal = {PVLDB},
        series = {{VLDB} '97},
        pages = {466},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 46 of 46 citing papers.

Rank Citing Paper Year Venue Pagerank
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036097627
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034050614
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
259 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022881075
268 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022654182
316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021238056
337 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00020593498
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
442 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018182341
450 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.0001806593
457 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017915659
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016236872
745 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014267268
844 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013498392
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
861 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013374869
935 Dynamic Sample Selection for Approximate Query Processing 2003 SIGMOD 0.00012968914
951 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00012886042
1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012551491
1,246 Compressing SQL Workloads 2002 SIGMOD 0.00011355447
1,754 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7111856e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
2,184 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.8972748e-05
2,614 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.2023561e-05
2,820 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9529694e-05
3,081 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6515625e-05
3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6394636e-05
3,371 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3493132e-05
3,993 Data Canopy: Accelerating Exploratory Statistical Analysis 2017 SIGMOD 6.8565106e-05
4,269 Selectivity Estimation for Spatio-Temporal Queries to Moving Objects 2002 SIGMOD 6.6778228e-05
4,962 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3244317e-05
5,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0707348e-05
5,591 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.0553413e-05
6,195 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.8374071e-05
6,653 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 5.7044094e-05
6,800 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.662589e-05
7,512 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.490671e-05
10,346 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0197268e-05
11,989 Data-Independent Space Partitionings for Summaries 2021 PODS 4.9605343e-05
12,368 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.9605343e-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
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023948467
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
3,977 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8707656e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD
2 745 Dynamic Multidimensional Histograms 2002 SIGMOD
3 806 Universality of Serial Histograms 1993 VLDB
4 5,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS
5 37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD
6 7,584 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
7 450 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB
8 518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD
9 285 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
10 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD