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: hac234990aeeb8c3e
Venue: SIGMOD
Year: 2022
Pagerank: 6.0683695e-05
Overall Rank: 5,612 | 62.27%
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,890	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	6.9442248e-05
9,150	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.21801e-05
10,479	Maintaining Biconnected Components in Streaming Graphs	2026	SIGMOD	4.9793485e-05
11,711	Prerequisite-driven Fair Clustering on Heterogeneous Information Networks	2023	SIGMOD	4.9793485e-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.001992968
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
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
3,300	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.443826e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.138409e-05
5,440	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	6.1276555e-05
6,313	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.8165778e-05
9,041	Summarization and Matching of Density-Based Clusters in Streaming Environments	2012	VLDB	5.2321972e-05

Semantically Similar Papers

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