4 ms·

Nice work! How does it compare against FAISS?

eigenvalue 3y ago
It's really quite different in goals to FAISS. FAISS is for if you have millions of stored vectors and want to do quick semantic similarity for retrieval. It manages to do this with some very clever approximations to narrow the search space. My library is very different: it's for when you don't have quite so many vectors, or when simpler measures like Cosine similarity aren't quite cutting it for whatever reason and you want to use more powerful techniques. I have another project that does robust near duplicate image detection (that is robust to all sorts of transformations), and it uses a similar approach of turning the images into high dimensional vectors. Using cosine similarity with FAISS is great for narrowing the field, but once you have done that, I find that you can get much higher quality results by augmenting the analysis with measures like Hoeffding's D. But until now, there were no high performance libraries for computing that in Python, and my library using Rust is orders of magnitude faster than using Numpy like this: import numpy as np import scipy def hoeffd_inner_loop_func(i, R, S): # See slow_exact_hoeffdings_d_func for definition of R, S Q_i = 1 + sum(np.logical_and(R<R[i], S<S[i])) Q_i = Q_i + (1/4)*(sum(np.logical_and(R==R[i], S==S[i])) - 1) Q_i = Q_i + (1/2)*sum(np.logical_and(R==R[i], S<S[i])) Q_i = Q_i + (1/2)*sum(np.logical_and(R<R[i], S==S[i])) return Q_i def slow_exact_hoeffdings_d_func(x, y): #Based on code from here: https://stackoverflow.com/a/9322657/1006379 #For background see: https://projecteuclid.org/download/pdf_1/euclid.aoms/1177730150 x = np.array(x) y = np.array(y) N = x.shape[0] R = scipy.stats.rankdata(x, method='average') S = scipy.stats.rankdata(y, method='average') print('Computing Q with list comprehension...') with MyTimer(): Q = [hoeffd_inner_loop_func(i, R, S) for i in range(N)] Q = np.array(Q) D1 = sum(((Q-1)*(Q-2))) D2 = sum((R-1)*(R-2)*(S-1)*(S-2)) D3 = sum((R-2)*(S-2)*(Q-1)) D = 30*((N-2)*(N-3)*D1 + D2 - 2*(N-2)*D3) / (N*(N-1)*(N-2)*(N-3)*(N-4)) print('Exact Hoeffding D: '+ str(round(D,8))) return D
spullara 3y ago
It sounds like it is brute force comparison so I imagine any approximate solution will be a lot faster. I have a similar brute force search library in Rust. Though I didn't find Rayon to be great (at the time).
- eigenvalue 3y ago
  It seems to really depend how you use Rayon, and the size of the data. The overhead of setting up the parallelism can't exceed the savings basically. Wherever it's possible to use ndarray broadcasting (vectorization), I do that instead. But I do think Rayon and the Rust compiler have gotten better about being smart, and I'm super impressed with the speed.

It's really quite different in goals to FAISS. FAISS is for if you have millions of stored vectors and want to do quick semantic similarity for retrieval. It manages to do this with some very clever approximations to narrow the search space. My library is very different: it's for when you don't have quite so many vectors, or when simpler measures like Cosine similarity aren't quite cutting it for whatever reason and you want to use more powerful techniques. I have another project that does robust near duplicate image detection (that is robust to all sorts of transformations), and it uses a similar approach of turning the images into high dimensional vectors. Using cosine similarity with FAISS is great for narrowing the field, but once you have done that, I find that you can get much higher quality results by augmenting the analysis with measures like Hoeffding's D. But until now, there were no high performance libraries for computing that in Python, and my library using Rust is orders of magnitude faster than using Numpy like this: import numpy as np import scipy def hoeffd_inner_loop_func(i, R, S): # See slow_exact_hoeffdings_d_func for definition of R, S Q_i = 1 + sum(np.logical_and(R<R[i], S<S[i])) Q_i = Q_i + (1/4)*(sum(np.logical_and(R==R[i], S==S[i])) - 1) Q_i = Q_i + (1/2)*sum(np.logical_and(R==R[i], S<S[i])) Q_i = Q_i + (1/2)*sum(np.logical_and(R<R[i], S==S[i])) return Q_i def slow_exact_hoeffdings_d_func(x, y): #Based on code from here: https://stackoverflow.com/a/9322657/1006379 #For background see: https://projecteuclid.org/download/pdf_1/euclid.aoms/1177730150 x = np.array(x) y = np.array(y) N = x.shape[0] R = scipy.stats.rankdata(x, method='average') S = scipy.stats.rankdata(y, method='average') print('Computing Q with list comprehension...') with MyTimer(): Q = [hoeffd_inner_loop_func(i, R, S) for i in range(N)] Q = np.array(Q) D1 = sum(((Q-1)*(Q-2))) D2 = sum((R-1)*(R-2)*(S-1)*(S-2)) D3 = sum((R-2)*(S-2)*(Q-1)) D = 30*((N-2)*(N-3)*D1 + D2 - 2*(N-2)*D3) / (N*(N-1)*(N-2)*(N-3)*(N-4)) print('Exact Hoeffding D: '+ str(round(D,8))) return D

spullara 3y ago

It sounds like it is brute force comparison so I imagine any approximate solution will be a lot faster. I have a similar brute force search library in Rust. Though I didn't find Rayon to be great (at the time).

eigenvalue 3y ago
It seems to really depend how you use Rayon, and the size of the data. The overhead of setting up the parallelism can't exceed the savings basically. Wherever it's possible to use ndarray broadcasting (vectorization), I do that instead. But I do think Rayon and the Rust compiler have gotten better about being smart, and I'm super impressed with the speed.