Vector search
A vector search index built from scratch in Python and Numba. Points sit in layers: a few joined by long links on top, all of them at the bottom. A search starts at the top, hops to whichever neighbour is closer to the query, and drops a layer when it cannot get closer.
At the bottom it keeps a short list of the best candidates, and ef is the size of that list. Try a small ef: the search looks at fewer points but can miss a true neighbour.
On 1 million SIFT vectors it reaches 0.979 recall at 3,034 queries per second, 34 times faster than exact search in NumPy. Against FAISS at the same recall, on one thread:
Speed compared with FAISS. Above 1 means mine is faster.
| Data | Ratio |
| SIFT, 100k vectors | 1.05 to 1.19 |
| SIFT, 1M vectors | 0.98 to 1.09 |
| GloVe, 1.2M, recall 0.9 to 0.97 | 1.1 to 1.6 |
| SIFT 100k, four threads | 0.79 to 0.96 |
Interpolated from my benchmark logs, not re-measured.
The README says where it loses, so I will too:
- With four threads FAISS is ahead.
- My memory figure counts only the links in use. The arrays reserve more, about 117 MB at 100,000 vectors against 65.6 MB for FAISS.
- I never varied M or efConstruction. Every run uses M = 16 and efConstruction = 100.
- Timings come from one shared 4-core server and vary by 20 to 30 percent between runs.