Database Paper Browser

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
3370
Venue
SIGMOD
Year
2002
Pagerank
0.00015919478
Overall Rank
849 | 94.11%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
194 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00035402379
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
654 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00018594644
933 Flexible Database Generators 2005 VLDB 0.00015220613
1,394 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012218557
1,712 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010786152
1,727 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00010731889
2,364 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 8.955077e-05
2,635 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.4081184e-05
3,123 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5270618e-05
3,491 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.0436671e-05
3,540 Approximation Techniques for Spatial Data 2004 SIGMOD 6.9922652e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6227223e-05
4,347 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2588401e-05
4,352 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2542257e-05
4,379 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.2326895e-05
4,463 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.1563782e-05
4,828 Managing Massive Time Series Streams with Multi-Scale Compressed Trickles 2009 VLDB 5.8890363e-05
5,465 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.491937e-05
5,642 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 5.3964761e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
5,832 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 5.3085972e-05
6,341 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.0980049e-05
6,506 Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006 SIGMOD 5.0276813e-05
6,634 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 4.9784928e-05
7,134 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 4.8174665e-05
7,340 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7526052e-05
7,644 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6853638e-05
7,697 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6701245e-05
7,725 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 4.6621296e-05
9,247 ZIP: Lazy Imputation during Query Processing 2024 VLDB 4.3648789e-05
9,508 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 4.3300131e-05
11,829 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.1905499e-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
60 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064450997
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044753012
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
275 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029381206
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
369 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025502381
431 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00023397171
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021385343
527 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00020862475
995 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014745185
1,126 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.0001381102
1,240 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013090678
1,254 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013018797
2,840 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.0417349e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,116 Global Optimization of Histograms 2001 SIGMOD 0.00013863484
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
8,092 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5847443e-05
1,240 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013090678
3,621 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9022467e-05
995 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014745185
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
5,832 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 5.3085972e-05
11,437 Data-Independent Space Partitionings for Summaries 2021 PODS 4.1905499e-05