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
3369
Venue
SIGMOD
Year
2002
Pagerank
0.00015941524
Overall Rank
852 | 94.08%
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.00035426067
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
654 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00018613167
934 Flexible Database Generators 2005 VLDB 0.00015227409
1,392 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012229045
1,717 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010793312
1,737 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00010720294
2,364 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 8.9554751e-05
2,629 Online Outlier Detection in Sensor Data Using Non-Parametric Models 2006 VLDB 8.4160309e-05
3,050 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.6512619e-05
3,486 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.0502199e-05
3,543 Approximation Techniques for Spatial Data 2004 SIGMOD 6.9917053e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6271553e-05
4,334 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.2798179e-05
4,350 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2645054e-05
4,359 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2569955e-05
4,382 Rectangle-Efficient Aggregation in Spatial Data Streams 2012 PODS 6.2386853e-05
4,824 Managing Massive Time Series Streams with Multi-Scale Compressed Trickles 2009 VLDB 5.8947137e-05
5,457 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.4970777e-05
5,632 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 5.4014372e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
5,879 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 5.2908101e-05
6,345 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.1023048e-05
6,511 Fast Range-Summable Random Variables for Efficient Aggregate Estimation 2006 SIGMOD 5.032518e-05
6,637 Approximating and Testing k-Histogram Distributions in Sub-linear Time 2012 PODS 4.9816401e-05
7,136 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 4.8220711e-05
7,358 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7529363e-05
7,645 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6896215e-05
7,699 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6746076e-05
7,728 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 4.666214e-05
9,240 ZIP: Lazy Imputation during Query Processing 2024 VLDB 4.3690661e-05
9,507 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 4.3341665e-05
11,821 Are Few Bins Enough: Testing Histogram Distributions 2016 PODS 4.1945683e-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
59 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064501896
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044744986
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
273 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00029390945
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026702512
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
429 The Aqua Approximate Query Answering System 1999 SIGMOD 0.00023476494
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021380733
529 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00020828852
996 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014741524
1,127 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00013819179
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
2,835 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.0448428e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,120 Global Optimization of Histograms 2001 SIGMOD 0.00013856211
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
8,090 Probabilistic Histograms for Probabilistic Data 2009 VLDB 4.5888589e-05
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
3,619 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9084829e-05
996 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014741524
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
5,879 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 5.2908101e-05
11,434 Data-Independent Space Partitionings for Summaries 2021 PODS 4.1945683e-05