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: 6348
Venue: SIGMOD
Year: 2022
Pagerank: 6.2019677e-05
Overall Rank: 5,483 | 62.39%
DOI: 10.1145/3514221.3517833

Incoming Non-self Citations Over Time

Authors

1. Bogyeong Kim (Seoul National University)
2. Kyoseung Koo (Seoul National University)
3. Undraa Enkhbat (Seoul National University)
4. Bongki Moon (Seoul National University)

BibTeX Citation

@inproceedings{kim_sigmod22,
        title = {{DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows}},
        author = {Kim, Bogyeong and Koo, Kyoseung and Enkhbat, Undraa and Moon, Bongki},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517833},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517833},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,911	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	7.0240227e-05
8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.3377754e-05
10,266	Maintaining Biconnected Components in Streaming Graphs	2026	SIGMOD	5.093636e-05
11,396	Prerequisite-driven Fair Clustering on Heterogeneous Information Networks	2023	SIGMOD	5.093636e-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.0020210012
962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012936472
1,907	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	9.501636e-05
2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4162172e-05
3,020	Dynamic Density Based Clustering	2017	SIGMOD	7.8445412e-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
5,335	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	6.2618226e-05
6,179	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.9496108e-05
8,881	Summarization and Matching of Density-Based Clusters in Streaming Environments	2012	VLDB	5.3520513e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,465	Scalable Kernel Density Classification via Threshold-Based Pruning	2017	SIGMOD
2	5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD
3	2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
4	5,335	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB
5	11,675	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
6	10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
7	3,020	Dynamic Density Based Clustering	2017	SIGMOD
8	11,387	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD
9	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD
10	1,907	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB