DBScholar

Back to papers

Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets

Summary: Wavelet-based compact data cube for sparse, high-dimensional data enables approximate OLAP aggregates. Two I/O-efficient construction algorithms; online queries require one to a few I/Os with tunable accuracy, outperforming histograms and random sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h3463f892239c8b01
Venue
SIGMOD
Year
1999
Pagerank
0.00024210103
Overall Rank
222 | 98.51%
DOI
10.1145/304182.304199

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{vitter_sigmod99,
        title = {{Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets}},
        author = {Vitter, Jeffrey Scott and Wang, Min},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304199},
        url = {https://dl.acm.org/doi/10.1145/304182.304199},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022713652
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022112534
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021376597
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.0002130211
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
479 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017623894
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016297598
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
843 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013534623
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012588952
1,061 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012208639
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001168187
1,182 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011615497
1,785 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.6438009e-05
2,003 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2071735e-05
2,142 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB 8.9644817e-05
2,324 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.6332031e-05
2,370 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.5582212e-05
2,654 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1670397e-05
2,855 iReduct: Differential Privacy with Reduced Relative Errors 2011 SIGMOD 7.93537e-05
3,094 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.6528924e-05
3,164 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5756378e-05
3,185 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5542356e-05
3,303 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4400795e-05
3,424 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 7.3084429e-05
3,559 Promotion Analysis in Multi-Dimensional Space 2009 VLDB 7.2045401e-05
4,272 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.6896372e-05
4,284 MDL Summarization with Holes 2005 VLDB 6.6859406e-05
4,377 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6269629e-05
4,418 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6058591e-05
4,463 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5861255e-05
5,623 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0586084e-05
5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9933192e-05
6,054 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9000316e-05
6,786 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.6811262e-05
6,948 Querying Big Data by Accessing Small Data 2015 PODS 5.6350267e-05
7,496 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5081355e-05
7,707 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 5.4723863e-05
8,301 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 5.3587028e-05
9,396 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1843659e-05
9,478 Context-sensitive Ranking for Document Retrieval 2011 SIGMOD 5.1694218e-05
9,676 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.142891e-05
9,852 Detecting Attribute Dependencies from Query Feedback 2007 VLDB 5.1189247e-05
10,318 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0363234e-05
11,298 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9769913e-05
11,478 The Moments Method for Approximate Data Cube Queries 2024 PODS 4.9769913e-05
12,045 FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data 2021 VLDB 4.9769913e-05
12,261 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.9769913e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023943337
9 Online Aggregation 1997 SIGMOD 0.00076265429
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.00071056708
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
214 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00024650285
323 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.00020991685
969 Recovering Information from Summary Data 1997 VLDB 0.00012788914
1,107 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011988445
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,007 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS
2 5,787 Extended Wavelets for Multiple Measures 2003 SIGMOD
3 214 On the Computation of Multidimensional Aggregates 1996 VLDB
4 3,842 High-Dimensional OLAP: A Minimal Cubing Approach 2004 VLDB
5 312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB
6 323 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD
7 3,303 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
8 169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
9 4,801 Aggregation Algorithms for Very Large Compressed Data Warehouses 1999 VLDB
10 309 Approximate Query Processing Using Wavelets 2000 VLDB