frontpage.
newsnewestaskshowjobs

Open Source @Github

fp.

Open in hackernews

Show HN: HNSW index for vector embeddings in approx 500 LOC

https://github.com/dicroce/hnsw
73•dicroce•1y ago

Comments

oersted•1y ago
I particularly appreciated the concise and plain explanation of the data-structure, it really demystifies it.

> 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.

> 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.

imurray•1y ago
Looks neat. It would be useful to compare to other implementations: https://ann-benchmarks.com/ -- potentially not just speed, but implementation details that might change recall.
swyx•1y ago
i think with small codebases like this is less about speed and more about education of essentials - i actually often encourage juniors to do small clones like this, feel proud, and then study the diffs with the at-scale repros and either feel humbled or feel like they have a contribution to make.
oersted•1y ago
I see they are still using GloVe word embeddings for the first benchmark. Ah good ol' days! Nothing wrong with it, should still yield a realistic distribution of vectors. Just brings a lot of memories :)
antirez•1y ago
Yes, HSNWs are not so 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:

https://github.com/redis/redis/blob/unstable/modules/vector-...

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.

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)

EDIT: Ok after carefully inspection this makes more sense :D

1. Yes, C++ helps, the vector class, the priority queue, ...

2. I forgot to say that I implemented serialization other than quantization, and this also includes quite some code.

3. Support for threads is another complexity / code-size price to pay.

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.

mertleee•1y ago
I guess I'm too simple to understand why this is useful? Just because it's been implemented in so few lines or?
cluckindan•1y ago
It makes it possible to approximate k-nearest neighbor vector search without having to calculate cosine similarity, dot product or euclidean distance for all stored vectors on the fly.
jasonjmcghee•1y ago
Implementations like these are incredibly useful for understanding how something like HNSW works, and being able to make derivative work.

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).

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.

https://github.com/jasonjmcghee/portable-hnsw

kamranjon•1y ago
This is incredibly cool, I’m surprised more people haven’t contributed to this - it seems like it’s only a few optimizations away from being performant enough for a pretty broad set of use cases.
jasonjmcghee•1y ago
Appreciate the kind words! Obviously feel free to hack on it.

When I first built it, I spent some time trying to tackle the issue of needing to update the entire file (and create an invalidation) if you want to update the database, which might be fine, but closes a lot of doors. I kind of hit a wall on finding a convincing approach to solving it, given the constraints of the setup.

aboardRat4•1y ago
I almost read it as NSFW.
vismit2000•1y ago
A very nice intro to HNSW that previously appeared on HN[1]: https://github.com/brtholomy/hnsw/blob/master/README.md

[1] https://news.ycombinator.com/item?id=41694631

Show HN: Shoptimist – Amazon but Curated

https://shoptimist.co/
2•MisterJoe•12m ago•0 comments

Show HN: Pulsar – cross-harness agent to agent communication and messaging

https://github.com/yocontra/pulsar
18•contrahax•9h ago•2 comments

Show HN: Sutra-OS – A self-hosted ontology platform

https://github.com/0nelight/sutra-os
60•0nelight•13h ago•27 comments

Show HN: Zigzag, a native Mac browser for people leaving Arc

https://github.com/ZigaoWang/zigzag
83•ZigaoWang•2d ago•52 comments

Show HN: MeshLive – Offline Video calls and livestreams over Bluetooth mesh

https://meshlive.github.io/
2•gptgautam1•3h ago•0 comments

Show HN: Open-source, real-time object tracking for live video feeds

https://github.com/aryamandarda/tamserve
29•aryaman_darda•15h ago•2 comments

Show HN: Fakemetrics.com – "build in public" like a superstar

https://fakemetrics.com/
47•tigranbs•18h ago•21 comments

Show HN: Free weekly backups for Supabase Free projects (pg_dump to R2)

https://github.com/liulewis/supabase-free-backup-lite
10•agricalc•11h ago•0 comments

Show HN: ThingStudio, Node-RED style programming for microcontrollers

https://thingstudio.net/
38•mkarliner•6d ago•7 comments

Show HN: Toolbelt – Free developer utilities that run in the browser

https://gettoolbelt.dev/
3•gprakasha234•9h ago•0 comments

Show HN: NOS x86-64 hypervisor, written in Rust

https://nos-os.tech/en/demo
4•irqlevel•14h ago•0 comments

Show HN: Birds as Code

https://erl-j.github.io/fun-zone/birds.html
12•abdljasser2•18h ago•8 comments

Show HN: Coding agents with native environments, identity and access

https://kosem.ai/blog/coding-agents-workstation-moment
4•yevpats•10h ago•0 comments

Show HN: Astrum – a terminal multiplexer with integrated AI assistant

https://robert-mcdermott.github.io/astrum/
4•mcdermott•10h ago•1 comments

Show HN: A terminal-native idle factory game, written in Rust with ratatui

https://gitlab.com/snipedbywifi/terminactory
171•snipedbywifi•2d ago•44 comments

Show HN: Deslop skill based on corpus-linguistics and psycholinguistics research

https://github.com/etodanik/deslop
13•dannypovolotski•1d ago•4 comments

Show HN: Omnistew – 3D multiplayer RTS written in Rust, playable in a browser

https://omnistew.io/
3•omnistew•11h ago•1 comments

Show HN: The Last Complication, a Zachtronics-style watchmaking puzzle game

https://lastcomplication.com/
86•tdeangelis•1d ago•18 comments

Show HN: Fundlark-open source tool help early-career researcher find funding

https://github.com/dryang21/Fundlark
4•dryang21•11h ago•0 comments

Show HN: Carton Clock – A working pendulum clock made from empty drink cartons

https://www.niklasroy.com/carton-clock/
87•r0r0•4d ago•2 comments

Show HN: I made an audio-to-MIDI model 60x more efficient

https://kobi.music/research/dettato
4•hidude562•11h ago•0 comments

Show HN: db-branch – database branches in seconds for AI agents and CI, via ZFS

https://github.com/db-branch/db-branch
45•nu_nu11•1d ago•16 comments

Show HN: Hotline Computer – Rootless Linux desktop container with Nix for agents

https://computer.hotline.dev/
3•1broseidon•12h ago•1 comments

Show HN: My $300 embroidery machine needed a subscription, so I built my own app

https://github.com/simpsoka/zigzag
742•simpsoka•4d ago•258 comments

Show HN: A custom font based on the Jamaican flag alphabet

https://bobbiec.github.io/jamaican-font.html
56•bobbiechen•2d ago•9 comments

Show HN: Fursoy – Out-of-order RV64IMAFDV core in SystemVerilog (Linux 6.6)

https://github.com/FURSOY/fursoy-cpu
86•fursoy•2d ago•39 comments

Show HN: DeepSeek V3 in ~200 lines of pure Jax

https://github.com/Vaibhaav-Tiwari/deepseek-v3-jax
276•VaibhaavTiwari•2d ago•30 comments

Show HN: Nobody blocks a keyboard – Rooted Android as a physical USB Deck

https://github.com/mr-anjaneyam/Emittr
4•mr-anjaneyam•22h ago•2 comments

Show HN: Agweb – a browser for agents that stays out of your way

https://github.com/paul-nameless/agweb
109•paul_nameless•2d ago•37 comments

Show HN: A geography game where you aim a compass at cities on a real globe

https://compasspost.nodewires.com/
3•wedontneed•16h ago•1 comments