DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows

Summary: DenForest enables fast incremental density-based clustering over sliding windows by representing clusters as spanning trees rather than graphs. It offers logarithmic-time split decisions on deletions and, empirically, outperforms prior incremental methods while matching DBSCAN's clustering quality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6286
Venue: SIGMOD
Year: 2022
Pagerank: 5.1987868e-05
Overall Rank: 6,125 | 57.40%
DOI: 10.1145/3514221.3517833

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,481	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	6.1485442e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
11,193	Prerequisite-driven Fair Clustering on Heterogeneous Information Networks	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.0032169493
961	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00015001792
1,816	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.0001045313
2,635	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4045788e-05
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05
3,295	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.2598552e-05
5,324	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	5.5691645e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
6,570	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.0065377e-05
8,779	Summarization and Matching of Density-Based Clusters in Streaming Environments	2012	VLDB	4.4539178e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
4,584	Scalable Kernel Density Classification via Threshold-Based Pruning	2017	SIGMOD	6.0668364e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
2,635	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4045788e-05
5,324	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	5.5691645e-05
11,477	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD	4.1945683e-05
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05
11,181	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD	4.1945683e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
1,816	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.0001045313