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.00024218831
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.00052121228
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.0002211981
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021384073
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021311793
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
564 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00016296665
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
842 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013540697
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012594522
1,082 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012122749
1,173 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00011686985
1,183 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00011616705
1,785 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.6482655e-05
2,000 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 9.2112617e-05
2,140 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB 8.9682092e-05
2,322 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.6361485e-05
2,368 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.5622073e-05
2,655 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.1706092e-05
2,855 iReduct: Differential Privacy with Reduced Relative Errors 2011 SIGMOD 7.9391282e-05
3,092 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.6563998e-05
3,163 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5789852e-05
3,184 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5577589e-05
3,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4424817e-05
3,424 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 7.3117029e-05
3,557 Promotion Analysis in Multi-Dimensional Space 2009 VLDB 7.2079402e-05
4,272 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.6925708e-05
4,282 MDL Summarization with Holes 2005 VLDB 6.6890966e-05
4,374 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6300924e-05
4,416 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.6089486e-05
4,462 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5880099e-05
5,622 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0614658e-05
5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.9961546e-05
6,052 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9028248e-05
6,781 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.6836871e-05
6,954 Querying Big Data by Accessing Small Data 2015 PODS 5.6350266e-05
7,493 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5103311e-05
7,701 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 5.474978e-05
8,295 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 5.3612406e-05
9,387 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1868213e-05
9,467 Context-sensitive Ranking for Document Retrieval 2011 SIGMOD 5.1718701e-05
9,669 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 5.1453267e-05
9,845 Detecting Attribute Dependencies from Query Feedback 2007 VLDB 5.1213286e-05
10,316 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 5.0377739e-05
11,290 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9793485e-05
11,472 The Moments Method for Approximate Data Cube Queries 2024 PODS 4.9793485e-05
12,039 FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data 2021 VLDB 4.9793485e-05
12,255 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.9793485e-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.0023947656
9 Online Aggregation 1997 SIGMOD 0.00076195956
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.00071084324
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028633995
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027134723
214 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00024656893
323 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.0002100085
967 Recovering Information from Summary Data 1997 VLDB 0.00012794553
1,106 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011994008
3,967 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8905715e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,004 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS
2 5,785 Extended Wavelets for Multiple Measures 2003 SIGMOD
3 214 On the Computation of Multidimensional Aggregates 1996 VLDB
4 3,841 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,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
8 169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD
9 309 Approximate Query Processing Using Wavelets 2000 VLDB
10 4,798 Aggregation Algorithms for Very Large Compressed Data Warehouses 1999 VLDB