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
3431
Venue
SIGMOD
Year
2002
Pagerank
0.00014620977
Overall Rank
723 | 95.05%
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
150 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00029208207
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
572 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00016316092
938 Flexible Database Generators 2005 VLDB 0.00013089351
1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012440928
1,170 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011827259
1,397 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010906135
1,573 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010328171
2,340 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.7246796e-05
3,044 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.820774e-05
3,086 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7708642e-05
3,150 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.7055991e-05
3,545 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.3249967e-05
3,703 Approximation Techniques for Spatial Data 2004 SIGMOD 7.1829776e-05
4,229 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.8181027e-05
4,258 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.7994155e-05
4,755 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.5226838e-05
4,882 Managing Massive Time Series Streams with Multi-Scale Compressed Trickles 2009 VLDB 6.4651572e-05
5,216 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.3121293e-05
5,421 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.2245831e-05
5,459 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.2108888e-05
5,650 Extended Wavelets for Multiple Measures 2003 SIGMOD 6.1337629e-05
6,138 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.9640712e-05
6,510 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 5.8569033e-05
6,727 Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006 SIGMOD 5.7902041e-05
7,177 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.6806091e-05
7,256 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.6625146e-05
7,433 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.6197531e-05
7,554 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.6001388e-05
7,752 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.5521918e-05
9,285 ZIP: Lazy Imputation during Query Processing 2024 VLDB 5.292293e-05
9,642 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.2434488e-05
12,024 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 5.093636e-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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
75 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00037277061
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036378991
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
168 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027541029
213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024723025
235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023783792
267 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022798161
274 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022645621
311 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021760621
327 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00021091539
339 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020723773
365 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00020041735
448 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00018292618
850 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00013619394
977 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012864017
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
1,186 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011764128
2,493 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.5070756e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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