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.0001431602
Overall Rank
742 | 95.02%
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.0002867034
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
584 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00015954725
955 Flexible Database Generators 2005 VLDB 0.00012866364
1,066 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012192801
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011777105
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010681774
1,580 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010180835
2,359 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.5813849e-05
3,052 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7052471e-05
3,094 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6533343e-05
3,211 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.536045e-05
3,562 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.2046519e-05
3,758 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0437238e-05
4,324 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6656407e-05
4,348 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.6469144e-05
4,865 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.3763323e-05
4,992 Managing Massive Time Series Streams with Multi-Scale Compressed Trickles 2009 VLDB 6.3237119e-05
5,327 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.1783009e-05
5,534 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0923159e-05
5,580 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.0769576e-05
5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9961546e-05
6,241 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.8381762e-05
6,639 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 5.7259633e-05
6,865 Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006 SIGMOD 5.6603286e-05
7,320 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5538431e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
7,561 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4958573e-05
7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4792473e-05
7,916 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4276156e-05
9,455 ZIP: Lazy Imputation during Query Processing 2024 VLDB 5.1735482e-05
9,818 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1257999e-05
12,319 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.9793485e-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.00047731453
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
83 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00035978046
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027134723
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024218831
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023363722
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022413521
283 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022214789
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021311793
336 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00020657819
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019829769
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017962189
866 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00013381261
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012594522
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011548537
2,538 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.3284106e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 842 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD
2 1,687 Global Optimization of Histograms 2001 SIGMOD
3 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
4 8,206 Probabilistic Histograms for Probabilistic Data 2009 VLDB
5 1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD
6 5,004 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS
7 866 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,534 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS
10 11,939 Data-Independent Space Partitionings for Summaries 2021 PODS