I think parallelization could potentially be applied in the _kneighbors method, but, as shown in the image below, it actually worsens execution time. This is likely because the task itself is too lightweight or quick to benefit from parallel processing. So, I’d say it’s safe to conclude that parallelization isn’t really useful here

As for the warning, I’m not entirely sure what you mean, but maybe we can just remove the n_jobs parameter and turn off multithreading?

Testing on data:

Thanks for the benchmarking job ! Could you try switching the joblib backend to threading and see if it makes a difference ? As the distance function are njit numba function we shouldn't need to use loky backend. Otherwise, defining the kneighbors function as a numba function with parallel=True might work better.
Additionally, using more computing intensive functions like dtw instead of euclidean might change results

@baraline @Ramana-Raja How about parallelizing the loop in _predict in addition to what @Ramana-Raja has already done, it doesn't seem to have any looping dependencies. So could try?

It can work aswell yes, but then you need to balance number of threads (for kneighbor) per process (for sample or group of sample to predict) to find the right balance

Maybe we can limit the number of threads per process with max cpu count divided by njobs?

@baraline @Ramana-Raja How about parallelizing the loop in _predict in addition to what @Ramana-Raja has already done, it doesn't seem to have any looping dependencies. So could try?

This approach also doesn’t seem to work as intended if the data is small. It actually ends up making the execution time worse, as you can see below


testing done with dtw:

But if the data is large it performs better:


testing done on data:

@Ramana-Raja That behavior is expected. It occurs because the time required for process creation and context switching exceeds the compute time. To address this, analyze how the problem scales and plot a graph comparing execution times with and without parallelization. The intersection point will indicate the optimal input size where parallelism becomes beneficial. Ideally, this function should allow for dynamically switching between single-threaded and multithreaded execution.

@Ramana-Raja That behavior is expected. It occurs because the time required for process creation and context switching exceeds the compute time. To address this, analyze how the problem scales and plot a graph comparing execution times with and without parallelization. The intersection point will indicate the optimal input size where parallelism becomes beneficial. Ideally, this function should allow for dynamically switching between single-threaded and multithreaded execution.

This seems to depend on the CPU, right? The optimal data size might vary for different users with different CPU's. I think the best approach is to leave it configurable as a hyperparameter

Makes sense, @baraline wdyt?

I think the simplest would be to offload such hasssle to the numba compiler. We could use the existing functions of the distance module (e.g. euclidean_pairwise_distance) to compute the distance matrix in parallel, by adding a n_jobs=1 optional parameter, using the set_num_threads numba function and making _euclidean_pairwise_distance and _euclidean_from_multiple_to_multiple_distance use parallel=True with prange on both loops. This would not change default behaviour but would allow us to make use of n_jobs without much work.

This would necessitate a change in such function for all distances though, @chrisholder what do you think ?

I've tried two changes to KNeighborsTimeSeriesClassifier and profiled both:

1. Use n_jobs in _predict
2. Use dtaidistance instead of Aeon's dtw_distance

Left and middle screen show parallelization and dtaidistance integration into class. Right screen shows profiling code. These are the results of profiling on my 11th Gen Intel Core i7-1165G7 @ 2.80GHz × 4 CPU:

Conclusion: dtaidistance helps more than parallelization, but parallelization certainly helps on larger data sets.
dtaidistance is implemented in C, but its performance gains are almost only due to it allowing an upper bound. I've parallelized in _predict instead of _kneighbors because the upper bound means _kneighbors is not embarrassingly parallel anymore, while _predict still is.

For the issue at hand, I'd put the parallelization in _predict and open a new issue to either include dtaidistance as a (soft) dependency or implement max_dist in dtw_distance and possibly others. Let me know what you think!

Sounds good generally. There is some discussion to be had on how exactly to implement the soft dependency distance and if we want to go that route to begin with, but can leave that to its own issue.

There is a PR to parallelise the aeon distances in #2545. This is only being held up due to notebook issue, so it may be worth testing that also.