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.0454405e-05
Overall Rank: 5,625 | 62.30%
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,902	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	6.9179865e-05
9,184	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.1982941e-05
10,556	Maintaining Biconnected Components in Streaming Graphs	2026	SIGMOD	4.9605343e-05
11,763	Prerequisite-driven Fair Clustering on Heterogeneous Information Networks	2023	SIGMOD	4.9605343e-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.0019892478
992	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012621584
1,948	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	9.30382e-05
2,623	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.196568e-05
3,070	Dynamic Density Based Clustering	2017	SIGMOD	7.6675081e-05
3,314	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.4156999e-05
5,438	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.1152153e-05
5,461	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	6.1045744e-05
6,316	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.7968726e-05
9,069	Summarization and Matching of Density-Based Clusters in Streaming Environments	2012	VLDB	5.2124276e-05

Semantically Similar Papers

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