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