HNSW: как устроен графовый индекс для векторного поиска One million years later, я наконец добралась до прикручивания в проект семантического поиска. Тащить ради этого отдельную векторную бд максимально не хотелось, поэтому решила пойти классическим путем - попробовать встроить индекс HNSW прямо в движок наравне с остальными индексами. Если кратко, HNSW - это графовый индекс для approximate nearest neighbor поиска по векторам. Вместо того чтобы сравнивать запрос со всеми векторами в индексе, он заранее связывает близкие векторы в многоуровневый граф, а во время поиска двигается по этим связям в сторону все более похожих кандидатов. Как обычно, решила разобраться, как HNSW вообще работает: 1. зачем графу несколько уровней; 2. как выбирается entry point; 3. почему сверху greedy поиск, который расширяется на ниженем уровне; 4. что делают параметры M, efSearch и efConstruction; 5. почему при построении нельзя просто соединить ноду с M ближайшими; 6. и как работают reverse links и pruning. В итоге текста получилось на статью :") Пока без реализации и бенчмарков, а просто разбор внутрянки индекса. Читать тут: https://gist.github.com/dariasmyr/d492c3388feaf0f779571a635a3b493e