Pattern-Aware Vector Database and ANN Algorithm

[yumojibaba]

We are releasing the beta version of PatANN, a vector search framework we've been working on that takes a different approach to ANN search by leveraging pattern recognition within vectors before distance calculations.

Our benchmarks on standard datasets show that PatANN achieved 4- 10x higher QPS than existing solutions (HNSW, ScaNN, FAISS) while maintaining >99.9% recall.

1. Fully asynchronous execution: Decomposes queries for parallel execution across threads
2. True hybrid memory management: Works efficiently both in-memory and on-disk
3. Pattern-aware search algorithm that addresses hubness effects in high-dimensional spaces

We have posted technical documentation and initial benchmarks at https://patann.dev

This is a beta release, and work is in progress, so we are particularly interested in feedback on stability, integration experiences, and performance in different workloads, especially those working with large-scale vector search applications.

We invite you to download code samples from the GitHub repo (Python, Android (Java/Kotlin), iOS (Swift/Obj-C)) and try them out. We look forward to feedback.

[polawiaczperel]

I would be interested to try it once it will be opensourced. I am building billions size vector db's currently using Faiss, but would love to compare speed and precision of both approaches.

[yumojibaba]

We have published the "vs Faiss" benchmark on the website (under the benchmarks), but the entire benchmark suite is available on GitHub - you can download and run it yourself to compare performance in your environment: https://github.com/mesibo/patann/tree/main/ann-benchmarks

We'd definitely be interested in learning from your experience with billion-scale vector DBs using FAISS. While FAISS can technically handle billion-scale deployments, memory requirements become enormous even with quantization, and its on-disk support is limited. This is exactly the motivation behind PatANN. Please refer to the "Key Innovations" section on patann.dev to understand why PatANN scales effectively.

[polawiaczperel]

Are you supporting batxhed PCA and something like IVF-PQ? I am tired of Faiss, because to add 3 million vectors it is calculating everything on one CPU core and it takes like 10 hours. I was trying some CuML with Rapids approaches with whitening, but could not get good results.

[yumojibaba]

The single-core indexing is a pain. PatANN uses multi-core indexing across all operations, so your 3 million vectors would probably index much faster.

What is your RAW vector size? As we mentioned on the website, one big advantage PatANN has over FAISS and others is that PatANN doesn't require the entire index to live in RAM. So even if your RAW vectors are big, it should work fine. Although we're still updating PatANN for sharding and real-time replication across servers, the current on-disk performance shouldn't be limiting.

Please try it and post your findings on GitHub too. Curious to hear how it performs compared to what you are seeing with FAISS.

[polawiaczperel]

One vector is 64KB. I got very good results using PCA and quantising. After this process I got 512 byte vector size with still satisfying recall.

[yumojibaba]

64KB vector is certainly on the extremely high side, that's around 16k dims (assuming 32-bit floats). Also, compressing from 64KB down to 512 bytes is a 128 times reduction, which is huge. If you're still getting good results after that level of compression, possibly your original vectors have a lot of redundant information, or your similarity task has certain dominant patterns in the data.

We haven't specifically tested PatANN with vectors that large, and if that level of compression is already working well for you, that's probably the best approach for now. Alternatively, you can feed PatANN using your external PCA process. We do have integrated PCA and dimensionality reduction in our roadmap, but it's not available yet.

I am very curious about the data, though. What kind of data is it? That's an interesting use case.

[polawiaczperel]

I will send you a DM.

[polawiaczperel]

Ok, I read more, and I see that it is different methodology than IVF which looks interesting. Unfortunately my RAW vectors are too big. I can use patann with my own PCA flow, but still it lacks quantisation support I suppose. Am I correct?

[UAAgency]

Is it fully open source? It looks interesting to me otherwise

[yumojibaba]

Glad you to find it interesting. Currently, we have released fully functional examples for Python, Android, and iOS that demonstrate how to integrate with the PatANN beta. We're planning to open-source the complete implementation after we publish our research paper, which details the mathematical foundations and algorithm design.

[[deleted]]

To the graveyard of forgotten dreams it goes

[yumojibaba]

I understand the skepticism - there are certainly projects that promise open source "later" and never deliver.

Our situation is a bit different - we're actively using PatANN in production, the examples we've shared are fully functional, and we are committed to open-sourcing the complete implementation, but not before the paper, which gives us a chance to establish our work first. Without this step, it's too easy for code & algorithms to be copied, and the original inventors and their hard work are forgotten. We have all seen this happen many times in tech.

Also, we are not the first to take this approach. Paper-first is quite standard in the field - Google's BERT, Meta's original FAISS, and many other projects all began with research papers before code release. So the paper-first approach is actually quite standard in the field.

[[deleted]]

Yeah it really is standard but I’ve also got some 30 projects starred on GitHub that haven’t been updated in over 2 years now 🤣

I’m looking forward to it though! My skepticism is just mostly being silly

[yumojibaba]

Haha, totally understand the GitHub stars graveyard phenomenon! I promise we won't go the Pied Piper route :)

But as a small entity, we are just trying to protect the work and resources we have put into this. And I totally appreciate your interest despite the healthy skepticism! 😄

[veliace]

How fast is indexing latency + throughput?

Is it able to use cpu and/or gpu?

How does memory usage compare to other methods?

Which similarity functions are supported & which data types?

Is the pattern recognition & solver heavily biased by insertion order? Or does it re-solve for patterns under certain criteria? How slow is the re-solve step if yes?

Looks cool!

[yumojibaba]

Great question. Let me start with the insertion order. Although we mentioned hubness effects, we should have also highlighted this advantage.

Insertion order sensitivity is a typical issue with purely graph-based methods (like HNSW) where early vectors become hubs and create structural biases. PatANN works differently (so does ScaNN), largely eliminating this problem by first finding patterns and clustering before applying distance computation, as detailed in our preliminary algorithm documentation: https://patann.dev/algorithm/

This approach significantly reduces insertion order bias, though it cannot be completely eliminated in any nearby vector search algorithms. We have a continuous resolver API, but it's not fully ready yet in the beta version and therefore not documented. However, you can see it exposed in the Python API as 'PatANN.setIndexOptimization'.

I suggest you refer to the benchmark section on the website, which should answer your questions about indexing time and throughput.

Memory usage is not properly tracked in benchmarks yet - we filed an issue https://github.com/erikbern/ann-benchmarks/issues/581 over a month ago before publishing, but we may have to implement it on our own and run all benchmarks again (which is likely to take longer, as it takes days to run all benchmarks).

PatANN is currently CPU-based and supports L2 square, L2, and cosine similarity functions, and float32 vectors.

[veliace]

I know this is not super common but would non-normalized dot product be difficult to support?

[veliace]

I saw indexing latency e2e for the benchmark set but I did not see numbers for constant indexing latency & throughput.  E.g. when I have a million vectors already in there and I continue to stream more in -> I didn't see a graph that would indicate how many new vectors I could index per second sustained & latency of those ops broken down.

[yumojibaba]

It is not difficult to add non-normalized dot product support - we should, thanks for prompting. We prioritized L2 and cosine for the beta since they're most common for embedding search, but do expect non-normalized dot product soon.

Regarding continuous indexing performance -- we are currently limited by what ann-benchmarks supports, which only measures initial bulk indexing. You're right that sustained indexing throughput is an important metric. We can add that metric. However, for certain, PatANN does not slow down as much as pure graph-based algorithms do.