Yes, HSNWs are not <i>so</i> complex, and they work great. I wrote an implementation myself, it's 2500 lines of code (5x the one of dicroce!), but inside there is binary and int8 quantization and many advanced features (include true deletions), and I commented it as much as possible. I hope you may find it useful to read alongside the one proposed by OP:<p><a href="https://github.com/redis/redis/blob/unstable/modules/vector-sets/hnsw.c">https://github.com/redis/redis/blob/unstable/modules/vector-...</a><p>Still, to be honest, I'm reading the 500 lines of code with great interest because I didn't thought it was possible to go so small, maybe part of the trick is that's in C++ and not in C, as for instance you don't have the queue code.<p>Also the strategy used by my implementation in order to re-link the orphaned nodes upon deletion adds complexity, too. (btw any feedback on that part is especially appreciated)<p>EDIT: Ok after carefully inspection this makes more sense :D<p>1. Yes, C++ helps, the vector class, the priority queue, ...<p>2. I forgot to say that I implemented serialization other than quantization, and this also includes quite some code.<p>3. Support for threads is another complexity / code-size price to pay.<p>And so forth. Ok, now it makes a lot of sense. Probably the 500 LOC implementation is a better first-exposure experience for newcomers. After accumulating all the "but how to..." questions, maybe my C implementation is a useful read.
I particularly appreciated the concise and plain explanation of the data-structure, it really demystifies it.<p>> HNSW is a graph structure that consists of levels that are more sparsely populated at the top and more densely populated at the bottom. Nodes within a layer have connections to other nodes that are near them on the same level. When a node is inserted a random level is picked and the node is inserted there. It is also inserted into all levels beneath that level down to 0.<p>> When searches arrive they start at the top and search that level (following connections) until they find the closest node in the top level. The search then descends and keeps searching nearby nodes. As the search progresses the code keeps track of the K nearest nodes it has seen. Eventually it either finds the value OR it finds the closest value on level 0 and the K nearest nodes seen are returned.
Implementations like these are incredibly useful for understanding how something like HNSW works, and being able to make derivative work.<p>I put together a tiny little implementation a while ago, the key thing being, it writes the index as a few parquet files, so you can host the index on a CDN and read from it via http range requests (e.g. via duckdb wasm).<p>Definitely isn't beating any benchmarks, but free (or wildly cheap) to host, as you serve it directly from a CDN and processing is done locally.<p><a href="https://github.com/jasonjmcghee/portable-hnsw">https://github.com/jasonjmcghee/portable-hnsw</a>
A very nice intro to HNSW that previously appeared on HN[1]: <a href="https://github.com/brtholomy/hnsw/blob/master/README.md">https://github.com/brtholomy/hnsw/blob/master/README.md</a><p>[1] <a href="https://news.ycombinator.com/item?id=41694631">https://news.ycombinator.com/item?id=41694631</a>
Looks neat. It would be useful to compare to other implementations: <a href="https://ann-benchmarks.com/" rel="nofollow">https://ann-benchmarks.com/</a> -- potentially not just speed, but implementation details that might change recall.