How does it compare against FAISS?
How does it compare against FAISS?
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