This pull request provides optmisitaion and significant performance uplift for the spatial DBSCAN implementation.
On my computer (R5 5600H) the uplift is going from the initial 800ms (1.2Hz) / callback to 100ms (10Hz) / callback.
Key changes
KD-tree Implementation
A KD-tree is introduced to optimize the neighbor search, replacing the previous brute-force method.
KD-tree construction and the neighbor search process are parallelized using TBB for efficient performance.
Limited neighbor searching to the number that is required to mark a point core. (Previously it went indefinitely[wasted around 100ms])
Improved clustering
Instead of brute forcing ten times to potentially find all points in a cluster, a queue based method is introduced.
In this function, the distance measurement is replaced by a bounding box measurement. While in theory it somewhat reduces accuracy, it leads to a measurable performance improvement.
Added benchmarking
New class is introduced to easily handle benchmarking during development.
From what I can see, this is as fast as it gets for this algorithm.
Currently, the neighbor finding is limited to only look for enough neighbors to determine if a point is a core point.
Another option would be to find all neighbors within a certain radius, and later only use those neighbors to expand the cluster,
but in that case, we would spend more time on finding the neighbors than what we save by not expanding the cluster from all points.
Spatial DBSCAN optimisation
Overview
This pull request provides optmisitaion and significant performance uplift for the spatial DBSCAN implementation. On my computer (R5 5600H) the uplift is going from the initial 800ms (1.2Hz) / callback to 100ms (10Hz) / callback.
Key changes
KD-tree Implementation
Improved clustering
Added benchmarking
From what I can see, this is as fast as it gets for this algorithm. Currently, the neighbor finding is limited to only look for enough neighbors to determine if a point is a core point. Another option would be to find all neighbors within a certain radius, and later only use those neighbors to expand the cluster, but in that case, we would spend more time on finding the neighbors than what we save by not expanding the cluster from all points.
Additionally, fixed a typo in the README.