Slow DBSCAN runtimes

[srinivass99]

Hey guys , hope this is the right place to ask about this :

I am working on a data pipeline which handles sales data of stores and display some analytics which includes clustering order totals (1D) . I've implemented K-means using scholar and it is working great! i wanted to try other algorithms as well and picked DBSCAN. However it is very slow to the point that a dataset with ~600 ish orders is taking forever to complete.

Working on a mac, using EXLA as backend, slow execution happens in both livebook and brew install of elixir

This is my code for timing it with slices of the original data :

 for it <- [10,50,100,200,300,400,500,600] do
  {time, _result} =
  :timer.tc(fn ->
    x = order_values["discounted_amount"] |> Nx.to_tensor()

    y =
      x
      |> Nx.slice([0], [it])
      |> Nx.reshape({:auto, 1})

    Scholar.Cluster.DBSCAN.fit(y, eps: 100, min_samples: 2)
  end)

IO.puts("time: #{time / 1000000} seconds")
end 

Output

time: 0.010366 seconds
time: 0.026122 seconds
time: 0.421917 seconds
time: 18.469798 seconds
time: 195.325409 seconds
time: 2069.163107 seconds

i aborted it when number of records reached 400. K-means is running much faster on much bigger datasets. Any help is appreciated! and apologise if i've missed any relevant details

[josevalim]

Hi @srinivass99, are you using the EXLA compiler as well? Can you share your EXLA configuration?

In case you are, then it may be an issue with the implementation. :)

[srinivass99]

require Explorer.DataFrame
require Explorer.Series
alias Explorer.DataFrame, as: DF
alias Explorer.Series, as: S
alias VegaLite, as: VL
alias Statistics, as: ST
alias Scholar.Cluster.KMeans


Nx.global_default_backend(EXLA.Backend)
Nx.Defn.global_default_options(compiler: EXLA)
key = Nx.Random.key(42)

i followed this part from the K-means example in the docs, running it on the first cell after setup

[josevalim]

Right, so I think it is an algorithm issue rather than something you are doing wrong!

[srinivass99]

Thank you for responding so quick! and appreciate your work :)
Is there any other info i can provide to help identify the issue ?

[josevalim]

You could provide a minimal code snippet that reproduces the issue. Perhaps a random tensor of the same shape as above will be enough. But the best way to guarantee it is fixed would be by submitting a PR. :)

[srinivass99]

Nx.global_default_backend(EXLA.Backend)
Nx.Defn.global_default_options(compiler: EXLA)

for it <- [10, 50, 100, 200, 300, 400, 500, 600] do
  {time, _result} =
    :timer.tc(fn ->
      tensor = Nx.linspace(0.1, 62.3, n: 623)
      x = tensor
      |> Nx.slice([0], [it])
      |> Nx.reshape({:auto, 1})
      
      Scholar.Cluster.DBSCAN.fit(x, eps: 10, min_samples: 2)
    end)
  
  IO.puts("time: #{time / 1000000} seconds")
end  

just changed it to a random tensor, and was able to reproduce the issue

tensor = Nx.tensor(Enum.to_list(1..623), type: :s64)

tensor with integers rather than floating points like in my original dataset, also have the same issue

[jonatanklosko]

@srinivass99 please give #325 a try :)

[srinivass99]

@jonatanklosko thanks for working on this :)

i gave #325 a try and it is faster now, but still slow for bigger datasets. my results do match your before and after for the tensor with 600 records , but when i tried it with a dataset which has around ~29k records, it takes way too long.
I ran timers on slices again to benchmark

Nx.global_default_backend(EXLA.Backend)
Nx.Defn.global_default_options(compiler: EXLA)

for it <- [2000, 4000, 6000, 8000, 10000, 12000, 14000, 16000, 18000, 20000] do
  {time, _result} =
    :timer.tc(fn ->
      tensor = Nx.tensor(Nx.linspace(0.1,2900,n: 29000))

      x = tensor
      |> Nx.slice([0], [it])
      |> Nx.reshape({:auto, 1})
      
      Scholar.Cluster.DBSCAN.fit(x, eps: 10, min_samples: 2)
    end)
  
  IO.puts("time: #{time / 1000000} seconds")
end 

Output
time = 2.595474 seconds
time = 17.541271 seconds
time = 63.662616 seconds
time = 132.888495 seconds
time = 281.319276 seconds

aborted here, the run time went into 1000s+

[krstopro]

@jonatanklosko thanks for working on this :)

i gave #325 a try and it is faster now, but still slow for bigger datasets. my results do match your before and after for the tensor with 600 records , but when i tried it with a dataset which has around ~29k records, it takes way too long. I ran timers on slices again to benchmark

Nx.global_default_backend(EXLA.Backend)
Nx.Defn.global_default_options(compiler: EXLA)

for it <- [2000, 4000, 6000, 8000, 10000, 12000, 14000, 16000, 18000, 20000] do
  {time, _result} =
    :timer.tc(fn ->
      tensor = Nx.tensor(Nx.linspace(0.1,2900,n: 29000))

      x = tensor
      |> Nx.slice([0], [it])
      |> Nx.reshape({:auto, 1})
      
      Scholar.Cluster.DBSCAN.fit(x, eps: 10, min_samples: 2)
    end)
  
  IO.puts("time: #{time / 1000000} seconds")
end 

Output time = 2.595474 seconds time = 17.541271 seconds time = 63.662616 seconds time = 132.888495 seconds time = 281.319276 seconds

aborted here, the run time went into 1000s+

Hi @srinivass99! I think this is reasonable as DBSCAN cannot run in parallel the same way k-means can. Therefore, for bigger datasets I would suggest using k-means. Not sure if it is possible to improve the existing DBSCAN implementation.

[jonatanklosko]

@srinivass99 please try #326 :)

[srinivass99]

@jonatanklosko thank you! the run times are much more quicker now!