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.00024136952
Overall Rank: 222 | 98.52%
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.00051942573
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
287	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022060616
311	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021315058
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
481	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017567157
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016251304
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013498392
1,006	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012551491
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,174	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001165008
1,186	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011581468
1,795	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.6147575e-05
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
2,154	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9382906e-05
2,335	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6050778e-05
2,378	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.5315761e-05
2,661	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.1414177e-05
2,863	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	7.9091713e-05
3,106	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.6276487e-05
3,168	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5583423e-05
3,195	Structure and Value Synopses for XML Data Graphs	2002	VLDB	7.530952e-05
3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4165176e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
3,569	Promotion Analysis in Multi-Dimensional Space	2009	VLDB	7.1808992e-05
4,290	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.6675308e-05
4,298	MDL Summarization with Holes	2005	VLDB	6.6640493e-05
4,401	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.6051378e-05
4,438	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.5840202e-05
4,480	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.566036e-05
5,636	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0385837e-05
5,800	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9735022e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05
6,800	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.662589e-05
6,964	Querying Big Data by Accessing Small Data	2015	PODS	5.617412e-05
7,512	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.490671e-05
7,720	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	5.4542911e-05
8,315	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.341013e-05
9,422	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1672232e-05
9,506	Context-sensitive Ranking for Document Retrieval	2011	SIGMOD	5.1523285e-05
9,705	SHIFT-SPLIT: I/O Efficient Maintenance of Wavelet-Transformed Multidimensional Data	2005	SIGMOD	5.1258854e-05
9,888	Detecting Attribute Dependencies from Query Feedback	2007	VLDB	5.1020175e-05
10,346	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0197268e-05
11,353	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9605343e-05
11,530	The Moments Method for Approximate Data Cube Queries	2024	PODS	4.9605343e-05
12,089	FlashP: An Analytical Pipeline for Real-time Forecasting of Time-Series Relational Data	2021	VLDB	4.9605343e-05
12,304	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	4.9605343e-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.0023948467
9	Online Aggregation	1997	SIGMOD	0.00076079812
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00070860346
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
214	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00024576033
324	An Array-Based Algorithm for Simultaneous Multidimensional Aggregates	1997	SIGMOD	0.00020934349
971	Recovering Information from Summary Data	1997	VLDB	0.00012748313
1,110	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00011949109
3,977	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8707656e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,031	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
2	5,800	Extended Wavelets for Multiple Measures	2003	SIGMOD
3	214	On the Computation of Multidimensional Aggregates	1996	VLDB
4	3,850	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB
5	316	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,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
8	171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
9	311	Approximate Query Processing Using Wavelets	2000	VLDB
10	4,820	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB