DBScholar

Back to papers

REHIST: Relative Error Histogram Construction Algorithms

Summary: REHIST constructs histograms under relative-error metrics, addressing the limits of absolute-error histograms and wavelet schemes. It provides optimal and fast approximation algorithms with guarantees, plus empirical validation on synthetic and real data showing improved relative-error accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hd7a033042ec554ad
Venue
VLDB
Year
2004
Pagerank
7.5583423e-05
Overall Rank
3,168 | 78.77%
DOI
10.1016/B978-012088469-8.50029-2

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{guha_vldb04,
        title = {{REHIST: Relative Error Histogram Construction Algorithms}},
        author = {Guha, Sudipto and Shim, Kyuseok and Woo, Jungchul},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {300--311},
        doi = {10.1016/B978-012088469-8.50029-2},
        url = {https://doi.org/10.1016/B978-012088469-8.50029-2},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
2,332 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.614375e-05
4,290 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.6675308e-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
8,205 Probabilistic Histograms for Probabilistic Data 2009 VLDB 5.3616572e-05
9,422 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1672232e-05
9,859 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1064323e-05
12,368 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.9605343e-05
13,005 FluxCapacitor: Efficient Time-Travel Text Search 2007 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027063233
198 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025558119
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024136952
277 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002235043
285 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022143946
337 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00020593498
806 Universality of Serial Histograms 1993 VLDB 0.00013752086
1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001165008
3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4165176e-05
3,653 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1149642e-05
5,031 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.2950911e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,693 Global Optimization of Histograms 2001 SIGMOD
2 5,031 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS
3 1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD
4 5,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS
5 4,438 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS
6 277 Optimal Histograms with Quality Guarantees 1998 VLDB
7 311 Approximate Query Processing Using Wavelets 2000 VLDB
8 450 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB
9 3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
10 171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD