# What is slowing down classic DBSCAN algorithm

How to apply CSR Matrix on DBSCAN algorithm in python without using any libraries?

Update: Matrix size (8580, 126356)

I have given a shot and implemented the algorithm. It runs rather slow. I guess its because regionQuery function calculates the euclidean distance between a chosen point and every other point in the dataset.

Is there any way this problem can be solved?

• I guess it's better to use prewritten libraries. They usually use optimization techniques that are so useful for accelerating operations. Apr 21 '18 at 14:46
• It is CSR means sparse matrix ?
– KyBe
Apr 22 '18 at 0:27

1. Write the DBSCAN code yourself.
2. Run the code.
3. Observe that your code likely will be a lot slower than the libraries code.
• totally agree with 3. +1 ;-)
– MaxU
Apr 21 '18 at 13:25
• Yes. I gave it a shot and implemented the algorithm. I concur that my implementation takes a while to compute. Apr 21 '18 at 15:09
• For DBSCAN to be fast, you also need to implement a fast region query, using an index structure. Apr 21 '18 at 19:40

As @Anony-Mousse pointed it, on DBSCAN index structures are often used in order to decrease execution times. K-d-trees are one example but this one works well just in small dimensions.

You had right intuition about what slowing down, the computation of every distance from all point to one is O(n) time complexity but applied to every points it becomes O(n2) which is something we desire to avoid on important set of points.

Moreover you may reconsider your clustering approach because DBSCAN is known to works well with small dimensional datasets due to hyperball volume fast decrease with higher dimensions.

Keep trying implementing algorithms by yourself it is best way to learn even if existing mature library do often a better job but are also more difficult to understand, one step after another you will be able to write better algorithms and contribute to open source libraries.

It also depends on the data spread. When I had data between 0-1 it worked well. When I tried to threshold some data inside so I had many samples with very small values. It started to work slowly.