RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning

Summary: RP-DBSCAN uses pseudo random, cell-based partitioning to balance load in parallel DBSCAN on skewed data. Compact two-level cell dictionary enables local clustering with light cross-partition merge on Spark, yielding up to 180x speedup. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h510a5b1f1c80e2aa
Venue: SIGMOD
Year: 2018
Pagerank: 7.443826e-05
Overall Rank: 3,300 | 77.82%
DOI: 10.1145/3183713.3196887

Incoming Non-self Citations Over Time

Authors

1. Hwanjun Song (Korea Advanced Institute of Science and Technology)
2. Jae-Gil Lee (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{song_sigmod18,
        title = {{RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning}},
        author = {Song, Hwanjun and Lee, Jae-Gil},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196887},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196887},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.138409e-05
5,612	DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows	2022	SIGMOD	6.0683695e-05
8,240	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	5.370583e-05
11,702	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD	4.9793485e-05
11,839	The Gibbs–Rand Model	2022	PODS	4.9793485e-05
11,971	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.9793485e-05
11,982	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.9793485e-05

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
300	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00021810545
986	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012668888
2,610	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.2276558e-05
3,057	Dynamic Density Based Clustering	2017	SIGMOD	7.6965352e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,411	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
2	986	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD
3	3,057	Dynamic Density Based Clustering	2017	SIGMOD
4	11,982	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
5	2,610	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
6	11,971	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
7	8,240	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD
8	7,642	Approximate DBSCAN under Differential Privacy	2025	SIGMOD
9	11,702	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD
10	5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD