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?

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

3 Answers 3

  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.
  • $\begingroup$ totally agree with 3. +1 ;-) $\endgroup$ Apr 21, 2018 at 13:25
  • $\begingroup$ Yes. I gave it a shot and implemented the algorithm. I concur that my implementation takes a while to compute. $\endgroup$
    – saranyavsr
    Apr 21, 2018 at 15:09
  • $\begingroup$ For DBSCAN to be fast, you also need to implement a fast region query, using an index structure. $\endgroup$ Apr 21, 2018 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.