Scalable Kernel Density Classification via Threshold-Based Pruning

Summary: Threshold-based pruning for KDE density classification (tKDC): iteratively compute density bounds and short-circuit KDE when bounds cross the target threshold. Maintains accuracy guarantees while delivering asymptotic speedups (up to 1000x) across diverse datasets and dimensions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5473
Venue: SIGMOD
Year: 2017
Pagerank: 6.6850249e-05
Overall Rank: 4,465 | 69.37%
DOI: 10.1145/3035918.3064035

Incoming Non-self Citations Over Time

Authors

1. Edward Gan (Stanford University)
2. Peter Bailis (Stanford University)

BibTeX Citation

@inproceedings{gan_sigmod17,
        title = {{Scalable Kernel Density Classification via Threshold-Based Pruning}},
        author = {Gan, Edward and Bailis, Peter},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064035},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064035},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
142	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.0002962566
578	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00016221871
640	Materialization Optimizations for Feature Selection Workloads	2014	SIGMOD	0.00015409494
1,792	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.7436856e-05
2,638	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	8.3130624e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
2	8,124	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD
3	11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
4	3,224	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD
5	11,755	QUAD: Quadratic-Bound-based Kernel Density Visualization	2020	SIGMOD
6	2,203	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB
7	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD
8	1,503	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD
9	10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
10	2,638	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD