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: 3208
Venue: SIGMOD
Year: 2000
Pagerank: 0.00014745185
Overall Rank: 995 | 93.09%
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.00027398081
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
838	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016024923
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
1,383	A Privacy-Preserving Index for Range Queries	2004	VLDB	0.00012262651
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
2,167	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	9.3879598e-05
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
2,635	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4081184e-05
2,769	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1512848e-05
3,220	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.3590708e-05
3,656	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8712579e-05
3,924	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	6.6227223e-05
3,992	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5519369e-05
4,696	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9843254e-05
5,061	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.717245e-05
5,405	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5243727e-05
6,448	Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines	2018	SIGMOD	5.0532741e-05
6,485	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0386161e-05
7,133	Anytime Measures for Top-k Algorithms	2007	VLDB	4.8175888e-05
7,134	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8174665e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
8,602	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4822166e-05
9,508	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3300131e-05
9,877	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2615675e-05
10,598	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.1905499e-05
10,627	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1905499e-05
12,068	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.1905499e-05
12,652	How to Evaluate Multiple Range-Sum Queries Progressively	2002	PODS	4.1905499e-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
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
527	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020862475
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,437	Data-Independent Space Partitionings for Summaries	2021	PODS	4.1905499e-05
2,813	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0816314e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
5,066	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	5.7157182e-05
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
360	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025768448