USearch: Smaller and faster single-file vector search engine

Depends... I have a beef with all methods based on "trained quantization". It introduces too much noise in your distribution, suffers from drifts, and makes the method mostly inapplicable for other forms of "Similarity Search" that don't strictly fall into the "Vector Search" category.

Many disagree. Pick whatever rocks your boat, there is a FOSS library for almost everything these days :)

Yeah, SPANN has better f1+queries per second on some benchmarks, but that's a little like comparing sorting algorithms, they're both fast and good.

The database software behind the ANN algo is probably a little more important in practice than the ANN algo itself, unless you're operating at such scale and speed that its an actual issue (e.g. you're google).

Differences between algorithms are a little more interesting when they let you do something totally different, like, for example, minimize the speed hit from doing searches on disk (SPTAG, DiskANN).

ScANN is not available in FAISS, it is Google's version of it.

This seems impractical, it's likely that the data is highly redundant and you'd probably do just as well by just picking a random projection to a much smaller subspace (or simply just perform a random subsampling of the dimensions, or sum dimensions together, stuff like that) rather than spending the compute to learn a projection via SVD or some such. Hubness might be a significant problem as well and lead to search results not matching your intent. Also, numeric problems (e.g., if you were accumulating distance in floating point) would become an issue as well with millions of dimensions unless the way that distances are summed get special treatment (like Kahan summation, or reduction trees to sum values of roughly equal expected magnitude, etc) too; x += dist[i] won't cut it.

Any kind of acceleration technique to limit the search to a subset of the database (such as cell-probe-ish methods like LSH or IVF, or graph-based methods, etc) would take a ton of time to compute. Simply storing all the data you need for search, even brute force, would rapidly explode, not to mention the compute required.

Most cases with such large vectors I've seen begin with highly sparse vectors. Certainly Faiss (I wrote the GPU side of Faiss), Annoy, or most any similarity search libraries out there are geared to dense vectors in the 20 - 2000ish dimension range (beyond the number of dimensions where exact methods such as BSP or k-D trees work well as in "high" dimensions your nearest neighbor is highly likely to lie on either side of a dividing hyperplane, but below cases where simply storing the data uncompressed / unquantized / etc is hard and the amount of compute is prohibitive as well).

How big is the data set (number of vectors) that you are searching among, and are you performing single queries or batch queries?

Train an autoencoder to reduce your vector dimensions down to something more workable. It’s unlikely you’ll be able to search against such enormous vectors in a reasonable amount of time anyways.

Another option is to shard your vectors into N pieces, where N*k is the length of your vector. Since cosine similarity doesn’t care about order, it will be fine. The only requirement is that the k-th vector can only be compared with other k-th vectors for similarity. The benefit of this approach is that it can be parallelized easily.

Reading the docs of this library it seems like I should try it, especially since it has built-in downcasting to save space on the indexes (which is rapidly turning into a big problem for me!)

> the size of a vector is over 2M

Do you mean the dimension of the vector or the number of vectors?

Yes, Annoy is probably not the best tool for the task. Are the vectors sparse?

Sure! You can pass exact=True to the search interface.

> Adding to index appears to be very slow.

Interesting. Can you please elaborate? We benchmark it on daily basis, but there is always a chance we forgot some corner case :)

PS: Thanks for considering us! USearch is already used in production by a few companies (small and very large), and we would be happy to assist with integration!

PS2: Argument name inconsistency is solved on the main-dev, and will be released with a bunch of major changes in 1.0 this week.

Oh, thank you! The library author here :)

We've just hosted one of our first community/contributor calls a few hours ago, discussing the plans for the upcoming 1.0 release, and integration with UCall, UStore, and UForm - our other FOSS libraries. Please don't hesitate to reach out for any questions or feature requests - now is the best time :)

sqlite-vss is an SQLite extension. Such things are often build on top libraries like FAISS or USearch. It is just a matter of - how many layers of abstractions do you want to pay for… performance wise.

If you already use some DBMS to store your data - extension can be a good place to start. Once you scale and want to tune… switch to using the underlying engine directly.

Not in the current public version, but you are thinking in the right direction. Sty tuned ;)

I was going to ask the same. That is a really important feature to have to replace traditional indexes and usually poorly implemented in vector search libraries.

For example, filtering by arbitrary time range.

Old-school Postgres extensions for GIS would be an example. They aren’t used much anymore, but I felt like they deserve a place in history :)

PS: Love your blog! I have worked on SFCs in the past. Did you?

We don't use BLAS. Why? BLAS helps with matrix-matrix multiplications, if you feel lazy and don't want to write the matrix tiling code manually.

They bring essentially nothing of value in vector-vector operations, as compilers can properly auto-vectorize simple dot products... Moreover, they generally only target single and double precision, while we often prefer half or quarter precision. All in all, meaningless dependency.

What do we use? I wrote a tiny package called SimSIMD. It's idea is to utilize less common SIMD instructions, especially in mixed-typed computations, that are hard for compilers to optimize. It was also a fun exercise to evaluate the performance of new SVE instruction on recent Arm CPUs, like the Graviton 3. You can find the code, the benchmarks, and the results in the repo: https://github.com/ashvardanian/simsimd

Still, even without SimSIMD, USearch seems to be one of the faster implementations of vector search. You can find the benchmarks in the first table here: https://github.com/unum-cloud/usearch#memory-efficiency-down...

Here you go :)

https://github.com/erikbern/ann-benchmarks/pull/451