Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure

Summary: Progressive approximate aggregates in multi-dimensional data via a Multi-Resolution Aggregate (MRA) tree; selective traversal yields 100% confidence intervals for SUM, COUNT, MIN, MAX, AVG. Iterative refinement until error or time bound; exact answers also produced by the same data structure with practical speed. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h53f83c1bd8a96389
Venue: SIGMOD
Year: 2001
Pagerank: 0.00014995058
Overall Rank: 664 | 95.54%
DOI: 10.1145/375663.375718

Incoming Non-self Citations Over Time

Authors

1. Iosif Lazaridis (University of California Irvine)
2. Sharad Mehrotra (University of California Irvine)

BibTeX Citation

@inproceedings{lazaridis_sigmod01,
        title = {{Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure}},
        author = {Lazaridis, Iosif and Mehrotra, Sharad},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375718},
        url = {https://dl.acm.org/doi/10.1145/375663.375718},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010017067
2,224	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.80823e-05
2,893	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	7.9019071e-05
3,085	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.6629324e-05
3,279	Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data	2015	VLDB	7.4620555e-05
3,613	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.162283e-05
3,781	Approximate MaxRS in Spatial Databases	2013	VLDB	7.0249074e-05
4,474	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5838686e-05
4,865	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.3763323e-05
6,042	Remembrance of Streams Past: Overload-Sensitive Management of Archived Streams	2004	VLDB	5.9060937e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-05
6,232	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.84313e-05
6,295	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.8202752e-05
6,682	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.7093663e-05
7,723	Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges	2017	SIGMOD	5.4675199e-05
7,742	Towards Best Region Search for Data Exploration	2016	SIGMOD	5.4614459e-05
8,040	Scaling Games to Epic Proportions	2007	SIGMOD	5.4015435e-05
8,282	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.3629192e-05
8,903	Finding Attribute-aware Similar Regions for Data Analysis	2019	VLDB	5.2559789e-05
9,399	Interactive Search and Exploration of Waveform Data with Searchlight	2016	SIGMOD	5.1848154e-05
11,947	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.9793485e-05
13,126	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.9793485e-05
13,127	Efficient Integration and Aggregation of Historical Information	2002	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
2	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
4	5,594	Efficient Computation of Temporal Aggregates with Range Predicates	2001	PODS
5	5,269	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
6	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
7	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
8	2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
9	6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
10	10,544	Approximate Query Processing under Updates	2026	SIGMOD