Online HDBSCAN
Online Hierarchical Density-Based Spatial Clustering of Applications with Noise · Also known as: incremental HDBSCAN, streaming HDBSCAN, online hierarchical density clustering, dynamic HDBSCAN
Online HDBSCAN extends the HDBSCAN hierarchical density-based clustering algorithm to incrementally process streaming or sequentially arriving data. Rather than rebuilding the full hierarchy from scratch with each new observation, it maintains and locally updates the mutual reachability graph, minimum spanning tree, condensed cluster tree, and stability-based cluster extraction, enabling continuous density-based clustering without full-dataset reprocessing.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use Online HDBSCAN when continuous or high-frequency data arrives incrementally and full reprocessing of HDBSCAN on the growing dataset is computationally infeasible. It suits applications with unknown cluster count, heterogeneous cluster densities, and meaningful noise — properties that make batch HDBSCAN preferable over k-means or DBSCAN — but where the data volume or arrival rate prevents batch retraining. Avoid it when the full dataset comfortably fits in memory and batch HDBSCAN can be re-run periodically without latency concerns — the batch version produces exact stability-based solutions without approximation overhead. Also avoid it when concept drift (distribution shift) is severe and accumulated historical points mislead current cluster structure; in that case a windowed or forgetting variant is needed.
Strengths & limitations
- Maintains the key advantages of HDBSCAN — arbitrary cluster shape, varying density, noise labelling — in a streaming setting.
- Avoids full reprocessing by updating only the affected portions of the MST, condensed tree, and stability scores.
- Memory footprint grows linearly with the number of retained points but can be bounded with a sliding window or micro-cluster summarisation.
- Produces cluster membership probabilities and noise labels continuously as new data arrives.
- No need to pre-specify the number of clusters; the minimum cluster size remains the only principal parameter.
- Incremental MST and condensed-tree repair adds implementation complexity far exceeding batch HDBSCAN.
- Core distances of earlier points can become stale when neighbourhood structures shift substantially with new arrivals, introducing approximation error.
- Without a forgetting or windowing mechanism, old points accumulate indefinitely, eventually making the method equivalent to batch HDBSCAN at high cost.
- Theoretical guarantees on the quality of the incremental approximation relative to the exact batch solution are limited compared to well-studied online ensemble methods.
Frequently asked
How does Online HDBSCAN differ from batch HDBSCAN?
Batch HDBSCAN builds the full mutual reachability graph, minimum spanning tree, and condensed cluster tree from all data at once. Online HDBSCAN maintains these structures incrementally, updating only the affected portions when a new point arrives. The result approximates what batch HDBSCAN would produce on the accumulated data, at a fraction of the computational cost.
How should I handle concept drift in Online HDBSCAN?
Online HDBSCAN in its basic form accumulates all historical points, which can cause stale structure to dominate current clusters when the distribution shifts. To address drift, use a sliding window (discarding old points) or micro-cluster summarisation so that recent data is weighted more heavily than distant history.
What minimum cluster size should I use in a streaming context?
Start with the same domain-knowledge-driven choice as for batch HDBSCAN. Monitor cluster count and noise fraction over time: if noise increases steadily or small clusters proliferate, consider increasing the minimum cluster size. Automated tuning via internal streaming cluster quality indices (such as the DBCV measure adapted for streams) can guide parameter updates.
Is Online HDBSCAN available in standard libraries?
Incremental and streaming density-based clustering components are available in the River library (Python), which supports hierarchical density-based methods for streaming data. The hdbscan Python library focuses on the batch variant; full online HDBSCAN may require custom incremental MST update logic built on top of existing components.
When should I prefer Online DBSCAN over Online HDBSCAN?
If your clusters have roughly uniform density and you are comfortable specifying an epsilon radius and min-samples threshold upfront, Online DBSCAN is simpler and faster. Online HDBSCAN is preferable when densities vary across clusters, the number of clusters is unknown, or you need stability-based noise labelling and cluster membership probabilities.
Sources
- Hassani, M., Seidl, T. (2017). Using internal evaluation measures to validate the quality of diverse stream clustering algorithms. Vietnam Journal of Computer Science, 4(3), 171–183. DOI: 10.1007/s40595-016-0086-9 ↗
- Campello, R. J. G. B., Moulavi, D., Zimek, A., & Sander, J. (2015). Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection. ACM Transactions on Knowledge Discovery from Data, 10(1), Article 5. DOI: 10.1145/2733381 ↗
How to cite this page
ScholarGate. (2026, June 3). Online Hierarchical Density-Based Spatial Clustering of Applications with Noise. ScholarGate. https://scholargate.app/en/machine-learning/online-hdbscan
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- Ensemble HDBSCANMachine learning↔ compare
- HDBSCANMachine learning↔ compare
- Online LearningMachine learning↔ compare
- Robust HDBSCANMachine learning↔ compare
- Spectral ClusteringMachine learning↔ compare