Fast Density-Based Clustering: Geometric Approach

Summary: GAP-DBC leverages geometric relations to beat DBSCAN’s O(n^2) bottleneck via a partition-based prestructure built from a limited set of range queries. Iterative refinement with spatial pruning reduces distance calculations, backed by theoretical guarantees and competitive empirical results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6623
Venue: SIGMOD
Year: 2023
Pagerank: 5.093636e-05
Overall Rank: 11,387 | 21.88%
DOI: 10.1145/3588912

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xiaogang Huang (Southwestern University of Finance and Economics)
2. Tiefeng Ma (Southwestern University of Finance and Economics)

BibTeX Citation

@inproceedings{huang_sigmod23,
        title = {{Fast Density-Based Clustering: Geometric Approach}},
        author = {Huang, Xiaogang and Ma, Tiefeng},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588912},
        url = {https://dl.acm.org/doi/10.1145/3588912},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012936472
2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4162172e-05
3,234	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.6144184e-05
5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.2790627e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,675	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
2	3,234	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD
3	7,500	Approximate DBSCAN under Differential Privacy	2025	SIGMOD
4	11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
5	962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD
6	2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
7	10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
8	3,020	Dynamic Density Based Clustering	2017	SIGMOD
9	5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD
10	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD