Quality and Efficiency in Kernel Density Estimates for Large Data

Summary: Randomized and deterministic KDE algorithms with quality guarantees for huge data; no kernel or bandwidth knowledge required. Highly parallelizable, MapReduce-friendly; orders-of-magnitude efficiency gains with strong empirical validation on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4788
Venue: SIGMOD
Year: 2013
Pagerank: 8.3130624e-05
Overall Rank: 2,638 | 81.91%
DOI: 10.1145/2463676.2465319

Incoming Non-self Citations Over Time

Authors

1. Yan Zheng (University of Utah)
2. Jeffrey Jestes (University of Utah)
3. Jeff M. Phillips (University of Utah)
4. Feifei Li (University of Utah)

BibTeX Citation

@inproceedings{zheng_sigmod13,
        title = {{Quality and Efficiency in Kernel Density Estimates for Large Data}},
        author = {Zheng, Yan and Jestes, Jeffrey and Phillips, Jeff M. and Li, Feifei},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465319},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465319},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,465	Scalable Kernel Density Classification via Threshold-Based Pruning	2017	SIGMOD	6.6850249e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
9,632	Fast Network K-function-based Spatial Analysis	2022	VLDB	5.2434488e-05
10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD	5.093636e-05
11,213	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	5.093636e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-05
11,533	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	5.093636e-05
11,615	SAFE: A Share-and-Aggregate Bandwidth Exploration Framework for Kernel Density Visualization	2022	VLDB	5.093636e-05
11,619	SWS: A Complexity-Optimized Solution for Spatial-Temporal Kernel Density Visualization	2022	VLDB	5.093636e-05
11,697	Fast Augmentation Algorithms for Network Kernel Density Visualization	2021	VLDB	5.093636e-05
11,755	QUAD: Quadratic-Bound-based Kernel Density Visualization	2020	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071822821
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013619394
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.2946291e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,184	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD
2	10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
3	4,222	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD
4	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
5	2,203	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB
6	1,503	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD
7	3,224	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD
8	5,998	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD
9	11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
10	4,465	Scalable Kernel Density Classification via Threshold-Based Pruning	2017	SIGMOD