DBScholar

Back to papers

Dynamic Multidimensional Histograms

Summary: Dynamic multidimensional histograms for continuous streams; a compact dynamic summary tracks distribution and yields on-demand accurate histograms. Algorithms give approximate guarantees on histogram quality; evaluation on real data validates tradeoffs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h938d6316e493ddb4
Venue
SIGMOD
Year
2002
Pagerank
0.00014267268
Overall Rank
745 | 95.01%
DOI
10.1145/564691.564741

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{thaper_sigmod02,
        title = {{Dynamic Multidimensional Histograms}},
        author = {Thaper, Nitin and Guha, Sudipto and Indyk, Piotr and Koudas, Nick},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564741},
        url = {https://dl.acm.org/doi/10.1145/564691.564741},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00028566618
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
588 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00015894454
958 Flexible Database Generators 2005 VLDB 0.00012834376
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011759683
1,439 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010641857
1,583 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010148362
2,364 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5549846e-05
3,060 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.6828463e-05
3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6394636e-05
3,219 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.50928e-05
3,555 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.1877332e-05
3,765 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0178846e-05
4,330 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6454689e-05
4,353 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.6322269e-05
4,888 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.3522397e-05
5,019 Managing Massive Time Series Streams with Multi-Scale Compressed Trickles 2009 VLDB 6.2998569e-05
5,336 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.1613661e-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
5,800 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9735022e-05
6,243 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.8220831e-05
6,653 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 5.7044094e-05
6,890 Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006 SIGMOD 5.6389416e-05
7,342 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5329816e-05
7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5212177e-05
7,581 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4753678e-05
7,654 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4588598e-05
7,935 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4071076e-05
9,496 ZIP: Lazy Imputation during Query Processing 2024 VLDB 5.1540002e-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
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank Cited Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036097627
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027063233
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024136952
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023327437
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
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
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020265363
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
457 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017915659
868 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00013336675
1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012551491
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
1,206 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011510881
2,544 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.2988657e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 844 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD
2 1,693 Global Optimization of Histograms 2001 SIGMOD
3 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
4 1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD
5 8,205 Probabilistic Histograms for Probabilistic Data 2009 VLDB
6 5,031 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS
7 868 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
8 119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD
9 5,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS
10 11,989 Data-Independent Space Partitionings for Summaries 2021 PODS