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.00014941252
Overall Rank: 667 | 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
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
870	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001332034
1,641	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	9.9814769e-05
2,231	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.7882698e-05
2,904	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	7.8723013e-05
3,099	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.6339784e-05
3,292	Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data	2015	VLDB	7.4344621e-05
3,611	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.1443694e-05
3,790	Approximate MaxRS in Spatial Databases	2013	VLDB	6.9983642e-05
4,498	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5590284e-05
4,888	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.3522397e-05
6,057	Remembrance of Streams Past: Overload-Sensitive Management of Archived Streams	2004	VLDB	5.8838023e-05
6,198	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8362492e-05
6,245	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.8210521e-05
6,311	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.7982836e-05
6,700	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.6877938e-05
7,742	Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges	2017	SIGMOD	5.4468611e-05
7,761	Towards Best Region Search for Data Exploration	2016	SIGMOD	5.4408101e-05
8,065	Scaling Games to Epic Proportions	2007	SIGMOD	5.3811604e-05
8,306	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.3426557e-05
8,931	Finding Attribute-aware Similar Regions for Data Analysis	2019	VLDB	5.2361195e-05
9,433	Interactive Search and Exploration of Waveform Data with Searchlight	2016	SIGMOD	5.1652249e-05
11,997	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.9605343e-05
13,173	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.9605343e-05
13,174	Efficient Integration and Aggregation of Historical Information	2002	SIGMOD	4.9605343e-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	844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
2	3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	9,205	Efficient Approximations of Conjunctive Queries	2012	PODS
4	5,285	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
5	5,609	Efficient Computation of Temporal Aggregates with Range Predicates	2001	PODS
6	2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
7	450	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
8	2,661	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
9	6,198	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
10	10,620	Approximate Query Processing under Updates	2026	SIGMOD