News for hackers. Stuff that matters.
Re:Haystack DB – 10x faster than FAISS with binary embedding... by fbdab103 on Sunday April 28, 2024 @11:58PM (#40194254)
Is this ready to go? Would love to see a Quickstart usage example somewhere.

I have a task which would potentially hugely benefit from this. I have 10 million, 500-element vectors I need to find their nearest pair (could settle for an approximate match). One time job, can crank away for weeks if required. The SQLite options seem like they will not be able to handle the load, so I was going to explore the Postgres vector extensions.

Doing napkin math says this would require just a stupid huge number of comparisons, but there is so much buzz about vector databases, I wanted to see if the indexes had some magic which could make this feasible without having terabytes of RAM.

Re:Haystack DB – 10x faster than FAISS with binary embedding... by carsonpoole on Monday April 29, 2024 @12:03AM (#40194282)
It works right now, but I'm actively adding a lot of additional things that might make your life easier. The roadmap on the readme shows what I'm working on adding. Feel free to shoot me an email at carson at poole.ai and I'd be happy to give some guidance, but a quickstart is definitely at the top of my priorities also. :)
Re:Haystack DB – 10x faster than FAISS with binary embedding... by gcr on Monday April 29, 2024 @12:54AM (#40194595)
This is really cool! Thanks for writing it!
Re:Haystack DB – 10x faster than FAISS with binary embedding... by carsonpoole on Monday April 29, 2024 @01:04AM (#40194656)
thank you for the kind words!
Re:Haystack DB – 10x faster than FAISS with binary embedding... by refibrillator on Monday April 29, 2024 @12:38AM (#40194494)
You don’t need a DB, I would avoid that for a one time job (I’ve used pgvector a lot).

Since your data fits in memory (18 GB @ FP32), I would start with a simple python script that does naive exhaustive search, which is O(n^2).

You can do approximate search which will sacrifice some accuracy, but you’ll have to build an index first.

HNSW index is state of the art right now and will give you accurate and fast approximate vector search, O(logᵏn). But the tradeoff is it can take a significant amount of time to build the graph data structure, which may not be favorable given the one off nature of your situation.

I would be sure to use a vectorized (SIMD) similarity search implementation, and multithreading to split the work among all CPU cores on a beefy machine.

Also, this falls into the category of “embarrassingly parallel” problems - it should be straightforward to divide the work across multiple machines if really necessary, eg see Ray and the surrounding python ecosystem.

Re:Haystack DB – 10x faster than FAISS with binary embedding... by gcr on Monday April 29, 2024 @12:47AM (#40194548)
Agree in principle but why use fp32? These are binary vectors, so OP just needs a fast Hamming distance
Re:Haystack DB – 10x faster than FAISS with binary embedding... by gcr on Monday April 29, 2024 @12:46AM (#40194540)
Do your vectors change a lot?

What have you tried so far? As a strong baseline, storing 10e6 512-bit vectors in memory should take about 640MiB of RAM. A binary Hamming distance between a query and a gallery is [popcnt(query xor elt) for elt in gallery], which should be plenty fast implemented in vectorized SSE instructions. I’d be shocked if this took more than 10ms per query per thread on modern hardware.

Re:Haystack DB – 10x faster than FAISS with binary embedding... by Loic on Monday April 29, 2024 @03:55AM (#40195710)
You are spot on, 10ms internal time for 100000 molecules, 60ms with the "stack on top": https://www.chemeo.com/similar?smiles=CCCCO It is using a manually coded, most likely not that efficient, with popcnt.
Re:Haystack DB – 10x faster than FAISS with binary embedding... by fbdab103 on Monday April 29, 2024 @08:12PM (#40205820)
These are not bit vectors, but float64. I could probably convert to float32 to cut down the ram. This is a one time job, so no changes.

My initial attempt has been using the scikit-learn cosine similarity function[0] which lets you take a query matrix against a target one. The actual calculation is pretty fast and seems quite optimized (at least, I can see all of my cores max out when it does the calculation). Then I iterate across the results matrix, sorting for best matches, and record best seen to date.

[0] https://scikit-learn.org/stable/modules/generated/sklearn.me...

Re:Haystack DB – 10x faster than FAISS with binary embedding... by social_quotient on Monday April 29, 2024 @06:30AM (#40196626)
Super curious what data this is, can you share a bit more of your use case for this much vector data?
Re:Haystack DB – 10x faster than FAISS with binary embedding... by matharmin on Monday April 29, 2024 @08:12AM (#40197293)
This sounds like the "Closest pair of points problem", which should have fast solutions - O(n log(n)) comparisons instead of O(n^2), which makes a huge difference when you have 10 million vectors. You might not find an off-the-shelf solution, but there are some good explanations of the approach at least.