Reference Issues/PRs

Towards #22587.
Follow up of #24556.

What does this implement/fix? Explain your changes.

The CSR-dense and the dense-CSR cases were chosen not to be supported for the Euclidean specialization of all PairwiseDistancesReductions (for more context see #23585 (comment)).

This PR implements SparseDenseMiddleTermComputer allows computing the middle term of the distance matrix decomposition for the Euclidean specializations, covering those two missing cases.

Hence this completes all the combinations for the Euclidean specialisations (:tada:).

Any other comments?

Different designs have been explored in other Pull Requests to factor some logic altogether or rethink DatasetsPairs w.r.t. MiddleTermComputer for the Euclidean specialisations.

In overall, this PR seems to have the best tradeoff regarding performance and duplication of code.

Benchmarks

This makes using PairwiseDistancesReductions on the CSR-dense and the dense-CSR for euclidean competitive w.r.t to the previous implementation relying on joblib.

One can get up to ×2 on a laptop.

In [1]: from sklearn.neighbors import NearestNeighbors
   ...: from sklearn.datasets import make_classification
   ...: from scipy.sparse import csr_matrix
   ...: 
   ...: import sklearn

In [2]: X_train, _ = make_classification(n_samples=100_000, n_features=100)
   ...: X_test, _ = make_classification(n_samples=256, n_features=100)
   ...: 
   ...: X_test = csr_matrix(X_test)

In [3]: nn = NearestNeighbors().fit(X_train)

In [4]: %%timeit
   ...: nn.kneighbors(X_test)
   ...: 
   ...: 
899 ms ± 13.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [5]: %%timeit
   ...: with sklearn.config_context(enable_cython_pairwise_dist=False):
   ...:     nn.kneighbors(X_test)
   ...: 
2.24 s ± 13.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [6]: X_train, _ = make_classification(n_samples=256, n_features=100)
   ...: X_test, _ = make_classification(n_samples=100_000, n_features=100)
   ...: 
   ...: X_test = csr_matrix(X_test)

In [7]: nn = NearestNeighbors().fit(X_train)

In [8]: %%timeit
   ...: nn.kneighbors(X_test)
   ...: 
   ...: 
760 ms ± 21.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [9]: %%timeit
   ...: with sklearn.config_context(enable_cython_pairwise_dist=False):
   ...:     nn.kneighbors(X_test)
   ...: 
1.22 s ± 14.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

TODO:

• Refactor the logic to:
  • Remove the cast on the entire dense array and data array and only upcast chunks using dedicated buffers (as done for DenseDenseMiddleTermComputer64
  • Redesign DatasetsPair w.r.t the new MiddleTermComputer to remove the duplicated logic and to clarify responsabilities (esp. squared euclidean norm computations)
    • Comment: the redesign was tried in ENH Euclidean specialization of DatasetsPair instead of ArgKmin and RadiusNeighbors #25170, works, but suffers from a lot of method dispatches overhead
• Add more tests?