Try resampling vectors to speed up L2LshModel #663
alexklibisz
started this conversation in
Ideas
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
From my comment here: #526 (comment)
In LSH models, we're currently building L * k distinct model vectors, and then computing the dot product of each one against the query/index vector. What if we just had k distinct vectors, but arranged them in L different ways, and then re-used the computed dot products but in varying arrangements.
There are some limits to this, e.g., we can only arrange 3 vectors 6 different ways, so L = 7, k = 3 would not be a valid combination.
For the fashion-mnist benchmark, we're using L = 100, k = 4. So to get 100 distinct arrangements we are computing 400 dot products. What's the minimum number of vectors we need in order to have 100 distinct arrangements of 4 vectors? I think 5: 5 * 4 * 3 * 2 * 1 = 120. So maybe we could get roughly the same effect by just computing 5 dot products instead of 400, so 80x faster.
Intuitively it seems unlikely, but maybe there's some point in the middle, e.g., do 40 dot products and sample from them? Maybe this can be introduced as a new parameter, essentially describing the amount of "resampling". Could be interesting to try.
Beta Was this translation helpful? Give feedback.
All reactions