Implement DBSCAN Using R Trees

Question

I am trying to implement DBSCAN using an R tree. We can store data in the form of an R tree. So my question is, how can I store real-time data in R trees and how should I implement a region query to find neighborhoods with it?

Answer 1

Run R-trees first, then DBSCAN.

In real time, you'll probably want to learn specialized clustering algorithms for data streams.

Answer 2

I'm not sure what you mean by real-time data. In case you are referring to a change in data or data streams, you can simply delete things that are deprecated from the R-tree. If you mean that your data also has a size of time, than simply increasing the number of coefficients controlled by the R-tree (x, y, t), I assume that you are using a simple version with two options.

If you want to implement DBSCAN, you will need to execute range queries in order to calculate the densities of the spherical regions around the points. Therefore, your queries in the region should handle spherical query regions (in this case, I also suggest that you check out SR-Tree by Shinichi Satoh, which might be useful). Again, if according to real-time data, you mean that your data has a temporal feature, you may want to use query areas that are ellipsoidal (allow separate scaling of spatial and temporal characteristics).

Hope this helps:]