Database Paper Browser

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
3099
Venue
SIGMOD
Year
1999
Pagerank
0.00029390945
Overall Rank
273 | 98.11%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072723062
308 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00028142852
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026702512
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
405 Approximate Query Processing Using Wavelets 2000 VLDB 0.00024057494
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
539 Fast Time Sequence Indexing for Arbitrary L_p Norms 2000 VLDB 0.00020666392
739 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00017401518
852 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015941524
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,127 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00013819179
1,335 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00012502131
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.00012191684
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011287495
1,970 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.896375e-05
2,137 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB 9.4719326e-05
2,316 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0419716e-05
2,368 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.9501526e-05
2,580 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.5058814e-05
2,748 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1785955e-05
2,776 iReduct: Differential Privacy with Reduced Relative Errors 2011 SIGMOD 8.1326122e-05
2,808 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0870741e-05
3,113 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5469926e-05
3,121 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.5271941e-05
3,310 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2408955e-05
3,819 Promotion Analysis in Multi-Dimensional Space 2009 VLDB 6.7299866e-05
3,944 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 6.6078243e-05
3,991 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5553055e-05
4,221 MDL Summarization with Holes 2005 VLDB 6.348988e-05
4,659 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.0160083e-05
4,698 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9887317e-05
4,831 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 5.8924198e-05
5,579 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4245689e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
6,161 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.1753664e-05
6,491 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.0429323e-05
7,085 Querying Big Data by Accessing Small Data 2015 PODS 4.8388174e-05
7,534 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7180004e-05
7,581 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7057641e-05
8,102 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 4.5852446e-05
9,061 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.4039656e-05
9,335 Context-sensitive Ranking for Document Retrieval 2011 SIGMOD 4.3556432e-05
9,340 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 4.3556432e-05
9,524 Detecting Attribute Dependencies from Query Feedback 2007 VLDB 4.3310217e-05
9,950 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 4.2421586e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
10,902 The Moments Method for Approximate Data Cube Queries 2024 PODS 4.1945683e-05
11,539 FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data 2021 VLDB 4.1945683e-05
11,751 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.1945683e-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.0040449103
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.0011708144
14 Online Aggregation 1997 SIGMOD 0.0010801504
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
247 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00030927763
366 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.0002552977
523 Recovering Information from Summary Data 1997 VLDB 0.00021089782
1,359 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.0001238588
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6584217e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,619 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9084829e-05
5,783 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.3289633e-05
247 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00030927763
3,157 High-Dimensional OLAP: A Minimal Cubing Approach 2004 VLDB 7.4656511e-05
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026702512
366 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.0002552977
3,310 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2408955e-05
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
4,954 Aggregation Algorithms for Very Large Compressed Data Warehouses 1999 VLDB 5.8053789e-05
405 Approximate Query Processing Using Wavelets 2000 VLDB 0.00024057494