Loser story

В последнее время я занимаюсь векторным поиском, поэтому захотелось написать про одну интересную и новую статью об этом.

https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann

Статья хорошо написана, но наверное будет сложно понять если не знать некоторых деталей:

Проблема:
Хочется быстро выдавать из n векторов top k ближайших по некоторой функции расстояния (max inner product, cosine, l2 distance, etc) к вектору q, dimensions которого d

Решения:
1. Последовательный перебор, работает за O(n * k * d), это ускоряется с помощью simd и thread параллелизма или даже gpu, но работает все равно не быстро (банально много нужно прочитать с диска).

2. Можно строить структуры данных подобные kd-tree/r-tree (разница в том, что первое про разбиение пространства, а второе про создание баундов).
К сожалению они плохо работают на больших размерностях (> 3):
2.1 kd потому что разбиение на каждом уровне происходит по одному из dimensions, а это мало что говорит о расстоянии для больших dimensions
2.2 r потому что баунд боксы почти всегда оверлапятся

В итоге используются разные приблизительные методы, которые будут работать с recall < 1
recall = (count of approximate top k in exact top k) / k

Тут можно разделить на три подхода: quantization (уменьшение размера или размерности исходных данных), структуры данных для исходных данных, и комбинация этих двух подходов.

1. Как уменьшить объем исходных данных:
1.1. scalar quantization -- обычно исходные вектора имеют координаты float32 => можно их преобразовать в int8, или даже более маленькие множества, это может дать ускорение в несколько раз (< 32).
1.2 product quantization -- разобьём исходный вектор размера d на m частей, для каждой части сделаем k(256) кластеров (например с помощью kmeans). Затем для каждого вектора из датасета каждый из m кусочков заменим на индекс соответствующего ему кластера.
В итоге вместо вектора из d float32, получим вектор из m uint8 (типичные значения m d/(4 ~ 16), соответственно типичное сжатие в 16-64 раза, с довольно хорошим качеством)

2.1 Какие структура данных используются?
1.1 hnsw, не буду описывать подробно, просто это вариант когда мы поверх исходного датасета строим примерный граф. Он наиболее популярный, так как имплементации достаточно простые (in memory как правило) и работают быстро на поиске. Из недостатков требует много памяти и медленный на построении. Есть интересные версии, DiskANN, с некоторыми заимствованиями из других подходов.
1.2 ivf -- разобьём исходные датасет на кластера каким то способом (например kmeans (scann -- google alloydb) или 2-means + randomize (annoy -- spotify)) и запишем к каждому из них список id исходных векторов
1.3 Предыдущий подход в чистом виде редко используется, ivf (kmeans) tree, аналогичен, только вместо того чтобы иметь огромные кластера, строится дерево из кластеров.

Ну и собственно интересный момент, в случае ivf подобных методов, чтобы вектора были более похожими (для более точной компрессии с помощью PQ), можно вместо исходных векторов компрессить cluster vector - cluster center, обозначим за r.

А теперь подходим к статье:

Когда вы используете ivf-like метод основное засчет чего вы теряете либо recall, либо rps это те вектора которые близки к границам кластеров.

Первая мысль которая приходит как это исправить: давайте id исходного вектора класть не в ближайший кластер, а в два ближайших.

На практике это даст незначительное улучшение.

В статье же рассказывается, что для inner product подобных расстояний, можно при выборе второго кластер хотеть чтобы r_1 и r_2 были почти ортогональны (если точнее, то угол влияет на выбор).

Это даёт качественное улучшение recall.


Все, можете идти открывать свой стартап про векторный поиск :)
А если серьезно, то специализированные базы данных векторного поиска это история только про хайп, там качественно ничего интересного не сделано к сожалению.

Почти все хорошее в этой области от пары рисерчей и google, ms, fb (и немного от нормальных баз данных, timescale pgvector например)

👍29

www.tgoop.com/reverse13/736

3.9K viewsedited  Jun 29, 2024 at 10:15

В последнее время я занимаюсь векторным поиском, поэтому захотелось написать про одну интересную и новую статью об этом.

https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann

Статья хорошо написана, но наверное будет сложно понять если не знать некоторых деталей:

Проблема:
Хочется быстро выдавать из n векторов top k ближайших по некоторой функции расстояния (max inner product, cosine, l2 distance, etc) к вектору q, dimensions которого d

Решения:
1. Последовательный перебор, работает за O(n * k * d), это ускоряется с помощью simd и thread параллелизма или даже gpu, но работает все равно не быстро (банально много нужно прочитать с диска).

2. Можно строить структуры данных подобные kd-tree/r-tree (разница в том, что первое про разбиение пространства, а второе про создание баундов).
К сожалению они плохо работают на больших размерностях (> 3):
2.1 kd потому что разбиение на каждом уровне происходит по одному из dimensions, а это мало что говорит о расстоянии для больших dimensions
2.2 r потому что баунд боксы почти всегда оверлапятся

В итоге используются разные приблизительные методы, которые будут работать с recall < 1
recall = (count of approximate top k in exact top k) / k

Тут можно разделить на три подхода: quantization (уменьшение размера или размерности исходных данных), структуры данных для исходных данных, и комбинация этих двух подходов.

1. Как уменьшить объем исходных данных:
1.1. scalar quantization -- обычно исходные вектора имеют координаты float32 => можно их преобразовать в int8, или даже более маленькие множества, это может дать ускорение в несколько раз (< 32).
1.2 product quantization -- разобьём исходный вектор размера d на m частей, для каждой части сделаем k(256) кластеров (например с помощью kmeans). Затем для каждого вектора из датасета каждый из m кусочков заменим на индекс соответствующего ему кластера.
В итоге вместо вектора из d float32, получим вектор из m uint8 (типичные значения m d/(4 ~ 16), соответственно типичное сжатие в 16-64 раза, с довольно хорошим качеством)

2.1 Какие структура данных используются?
1.1 hnsw, не буду описывать подробно, просто это вариант когда мы поверх исходного датасета строим примерный граф. Он наиболее популярный, так как имплементации достаточно простые (in memory как правило) и работают быстро на поиске. Из недостатков требует много памяти и медленный на построении. Есть интересные версии, DiskANN, с некоторыми заимствованиями из других подходов.
1.2 ivf -- разобьём исходные датасет на кластера каким то способом (например kmeans (scann -- google alloydb) или 2-means + randomize (annoy -- spotify)) и запишем к каждому из них список id исходных векторов
1.3 Предыдущий подход в чистом виде редко используется, ivf (kmeans) tree, аналогичен, только вместо того чтобы иметь огромные кластера, строится дерево из кластеров.

Ну и собственно интересный момент, в случае ivf подобных методов, чтобы вектора были более похожими (для более точной компрессии с помощью PQ), можно вместо исходных векторов компрессить cluster vector - cluster center, обозначим за r.

А теперь подходим к статье:

Когда вы используете ivf-like метод основное засчет чего вы теряете либо recall, либо rps это те вектора которые близки к границам кластеров.

Первая мысль которая приходит как это исправить: давайте id исходного вектора класть не в ближайший кластер, а в два ближайших.

На практике это даст незначительное улучшение.

В статье же рассказывается, что для inner product подобных расстояний, можно при выборе второго кластер хотеть чтобы r_1 и r_2 были почти ортогональны (если точнее, то угол влияет на выбор).

Это даёт качественное улучшение recall.


Все, можете идти открывать свой стартап про векторный поиск :)
А если серьезно, то специализированные базы данных векторного поиска это история только про хайп, там качественно ничего интересного не сделано к сожалению.

Почти все хорошее в этой области от пары рисерчей и google, ms, fb (и немного от нормальных баз данных, timescale pgvector например)

BY Loser story