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: 3348
Venue: SIGMOD
Year: 2001
Pagerank: 0.00015324657
Overall Rank: 648 | 95.56%
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
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.957715e-05
2,827	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.0831263e-05
3,024	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.8388143e-05
3,214	Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data	2015	VLDB	7.6325181e-05
3,595	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.2736195e-05
3,700	Approximate MaxRS in Spatial Databases	2013	VLDB	7.1861452e-05
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05
4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.5226838e-05
5,924	Remembrance of Streams Past: Overload-Sensitive Management of Archived Streams	2004	VLDB	6.0409904e-05
6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.9581422e-05
6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.9538639e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,556	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.8404094e-05
7,576	Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges	2017	SIGMOD	5.593012e-05
7,600	Towards Best Region Search for Data Exploration	2016	SIGMOD	5.5867987e-05
7,877	Scaling Games to Epic Proportions	2007	SIGMOD	5.5248563e-05
8,105	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.4860105e-05
8,740	Finding Attribute-aware Similar Regions for Data Analysis	2019	VLDB	5.3766157e-05
9,223	Interactive Search and Exploration of Waveform Data with Searchlight	2016	SIGMOD	5.3038189e-05
11,640	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	5.093636e-05
12,836	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	5.093636e-05
12,837	Efficient Integration and Aggregation of Historical Information	2002	SIGMOD	5.093636e-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	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
2	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
4	5,164	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB
5	5,501	Efficient Computation of Temporal Aggregates with Range Predicates	2001	PODS
6	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
7	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
8	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
9	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
10	10,342	Approximate Query Processing under Updates	2026	SIGMOD