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
3100
Venue
SIGMOD
Year
1999
Pagerank
0.00029381206
Overall Rank
275 | 98.10%
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.00072660894
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
373 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354685
416 Approximate Query Processing Using Wavelets 2000 VLDB 0.00023773968
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
537 Fast Time Sequence Indexing for Arbitrary L_p Norms 2000 VLDB 0.00020650291
736 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00017414831
849 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015919478
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,126 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.0001381102
1,331 ICICLES: Self-tuning Samples for Approximate Query Answering 2000 VLDB 0.00012553948
1,400 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001219602
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011289028
1,972 Approximate Lineage for Probabilistic Databases 2008 VLDB 9.8937766e-05
2,136 SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads 2003 VLDB 9.4668797e-05
2,322 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0348397e-05
2,377 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.9359321e-05
2,583 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.4973431e-05
2,752 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 8.1723418e-05
2,798 iReduct: Differential Privacy with Reduced Relative Errors 2011 SIGMOD 8.1092023e-05
2,813 A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries 2001 SIGMOD 8.0816314e-05
3,114 Structure and Value Synopses for XML Data Graphs 2002 VLDB 7.5419224e-05
3,127 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.5200903e-05
3,292 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2598265e-05
3,820 Promotion Analysis in Multi-Dimensional Space 2009 VLDB 6.7266035e-05
3,944 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 6.6056349e-05
3,989 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.5545373e-05
4,218 MDL Summarization with Holes 2005 VLDB 6.3436747e-05
4,656 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.0101164e-05
4,696 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 5.9843254e-05
4,815 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 5.8978716e-05
5,588 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4193309e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
6,170 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.1708554e-05
6,485 Robust Estimation With Sampling and Approximate Pre-Aggregation 2003 VLDB 5.0386161e-05
7,061 Querying Big Data by Accessing Small Data 2015 PODS 4.8400281e-05
7,533 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7134753e-05
7,573 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7034681e-05
8,108 NetCube: A Scalable Tool for Fast Data Mining and Compression 2001 VLDB 4.5808537e-05
9,059 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 4.3997447e-05
9,340 Context-sensitive Ranking for Document Retrieval 2011 SIGMOD 4.351469e-05
9,345 SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data 2005 SIGMOD 4.351469e-05
9,525 Detecting Attribute Dependencies from Query Feedback 2007 VLDB 4.326879e-05
9,946 Distributed Wavelet Thresholding for Maximum Error Metrics 2016 SIGMOD 4.240067e-05
10,647 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1905499e-05
10,906 The Moments Method for Approximate Data Cube Queries 2024 PODS 4.1905499e-05
11,543 FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data 2021 VLDB 4.1905499e-05
11,759 Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure 2018 VLDB 4.1905499e-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.0040465394
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.0011695087
14 Online Aggregation 1997 SIGMOD 0.0010813443
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
247 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00030923842
368 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.00025508459
523 Recovering Information from Summary Data 1997 VLDB 0.00021101376
1,363 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00012380611
3,896 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6526869e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,621 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9022467e-05
5,794 Extended Wavelets for Multiple Measures 2003 SIGMOD 5.323907e-05
247 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00030923842
3,162 High-Dimensional OLAP: A Minimal Cubing Approach 2004 VLDB 7.4622284e-05
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
368 An Array-Based Algorithm for Simultaneous Multidimensional Aggregates 1997 SIGMOD 0.00025508459
3,292 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2598265e-05
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
4,958 Aggregation Algorithms for Very Large Compressed Data Warehouses 1999 VLDB 5.8004036e-05
416 Approximate Query Processing Using Wavelets 2000 VLDB 0.00023773968