Dynamic Density Based Clustering

Summary: Dynamic clustering for density-based DBSCAN under insertions/deletions; rho-approximate DBSCAN shares the same fully dynamic hardness. A small relaxation (the sandwich guarantee) yields near-constant updates and two orders of magnitude speedups over prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h78e4c9691a8cd325
Venue: SIGMOD
Year: 2017
Pagerank: 7.6965352e-05
Overall Rank: 3,057 | 79.45%
DOI: 10.1145/3035918.3064050

Incoming Non-self Citations Over Time

Authors

1. Junhao Gan (University of Queensland)
2. Yufei Tao (University of Queensland)

BibTeX Citation

@inproceedings{gan_sigmod17,
        title = {{Dynamic Density Based Clustering}},
        author = {Gan, Junhao and Tao, Yufei},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064050},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064050},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,907	Real-Time Distance-Based Outlier Detection in Data Streams	2021	VLDB	7.8769563e-05
3,300	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.443826e-05
4,527	Dynamic Structural Clustering on Graphs	2021	SIGMOD	6.5602226e-05
5,440	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	6.1276555e-05
5,612	DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows	2022	SIGMOD	6.0683695e-05
5,990	Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space	2018	SIGMOD	5.9253259e-05
10,749	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	4.9793485e-05
11,455	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	4.9793485e-05
11,971	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
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
1,945	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	9.3257256e-05
7,433	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD	5.529101e-05

Semantically Similar Papers

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