Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes

Summary: Proposes a variable-size, overlapping-bucket histogram that adapts to local density to approximate multi-dimensional real-valued data distributions more compactly and accurately. Generalizes kernel density estimation for efficient approximation of aggregate range queries and compares favorably with existing methods on real and synthetic datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3207
Venue: SIGMOD
Year: 2000
Pagerank: 0.00014741524
Overall Rank: 996 | 93.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
790	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001663283
842	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016031973
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
1,386	A Privacy-Preserving Index for Range Queries	2004	VLDB	0.00012261809
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
2,165	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	9.389622e-05
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
2,629	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4160309e-05
2,762	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1585394e-05
3,313	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.2381634e-05
3,651	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8768678e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6271553e-05
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
4,698	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9887317e-05
5,065	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.7247716e-05
5,401	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5285035e-05
6,444	Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines	2018	SIGMOD	5.059132e-05
6,491	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0429323e-05
7,135	Anytime Measures for Top-k Algorithms	2007	VLDB	4.8221884e-05
7,136	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8220711e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05
9,507	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3341665e-05
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
10,590	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.1945683e-05
10,619	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1945683e-05
12,060	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.1945683e-05
12,643	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,434	Data-Independent Space Partitionings for Summaries	2021	PODS	4.1945683e-05
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
5,879	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.2908101e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
5,082	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	5.711623e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749