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: 3161
Venue: SIGMOD
Year: 1999
Pagerank: 0.00024723025
Overall Rank: 213 | 98.55%
DOI: 10.1145/304182.304199

Incoming Non-self Citations Over Time

Authors

1. Jeffrey Scott Vitter (Duke University)
2. Min Wang (Duke University)

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.00052982574
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022454217
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
977	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012864017
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,156	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011929041
1,166	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011850439
1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8358116e-05
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
2,121	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.1402718e-05
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05
2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.347674e-05
2,799	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1125988e-05
3,034	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.8302786e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.7256156e-05
3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.6057671e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,521	Promotion Analysis in Multi-Dimensional Space	2009	VLDB	7.3501396e-05
4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.8448865e-05
4,204	MDL Summarization with Holes	2005	VLDB	6.834169e-05
4,285	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.7812351e-05
4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.7605683e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.200262e-05
5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD	6.1337629e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.8131331e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,551	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.6006414e-05
8,121	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.4834308e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,484	Context-sensitive Ranking for Document Retrieval	2011	SIGMOD	5.2634238e-05
9,489	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	5.2634238e-05
9,671	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.238674e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,124	The Moments Method for Approximate Data Cube Queries	2024	PODS	5.093636e-05
11,736	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	5.093636e-05
11,957	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	5.093636e-05

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.0024089429
9	Online Aggregation	1997	SIGMOD	0.00077458002
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071822821
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
207	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00025088003
324	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.00021200835
952	Recovering Information from Summary Data	1997	VLDB	0.00013010681
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	7.04191e-05

Semantically Similar Papers

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