KNN
Введение
Одним из частных случаев векторного поиска является задача k-NN, где требуется найти k
ближайших точек к точке запроса. Это может быть полезно в различных приложениях, таких как классификация изображений, рекомендательные системы и многое другое.
Решения задачи k-NN разбивается на два крупных подкласса методов: точные и приближенные.
Точный метод
В основе точного метода лежит вычисление расстояния от вектора запроса до всех векторов в наборе данных. Этот алгоритм, также известный как наивный подход или метод грубой силы, имеет время выполнения O(dn)
, где n
— количество векторов в наборе данных, а d
— их размерность.
Точный векторный поиск лучше использовать, если полный перебор искомых векторов происходит за приемлемое время. В том числе, когда их можно предварительно отфильтровать по некоторому условию, например, по идентификатору пользователя. В таких случаях точный метод может работать быстрее, чем текущая реализация векторных индексов.
Основные преимущества:
- отсутствие необходимости в дополнительных структурах данных, таких как специализированные векторные индексы;
- полная поддержка транзакций, в том числе в режиме строгой согласованности;
- мгновенное применение операций модификации данных: вставка, обновление, удаление.
Приближенные методы
Приближенные методы не осуществляют полный перебор исходных данных. Это позволяет значительно ускорить процесс поиска, хотя и может привести к некоторому снижению качества результатов.
Скалярное квантование — это метод уменьшения размерности векторов, при котором множество координат отображается в пространство меньшей размерности.
YDB поддерживает векторный поиск по векторам типов Float
, Int8
, Uint8
, Bit
. Следовательно, возможно применение скалярного квантования для преобразования данных из Float
в любой из этих типов.
Скалярное квантование сокращает время, необходимое для чтения и записи данных, за счёт уменьшения числа байт. Например, при квантовании из Float
в Bit
каждый вектор сокращается в 32 раза.
Приближенный векторный поиск без индекса использует очень простую дополнительную структуру данных - множество векторов с другими квантованием. Это позволяет использовать простой алгоритм поиска: сначала грубый предварительный поиск по сжатым векторам, а затем уточнять результаты по исходным векторам.
Основные преимущества:
- полная поддержка транзакций, в том числе в режиме строгой согласованности;
- мгновенное применение операций модификации данных: вставка, обновление, удаление.
Примечание
Рекомендуется проводить замеры, обеспечивает ли такое преобразование достаточную точность/полноту.
Типы данных
В математике для хранения точек используется вектор вещественных или целых чисел.
В этом модуле вектора представлены типом данных String
, который является бинарным сериализованным представлением вектора.
Функции
Функции работы с векторами реализовываются в виде пользовательских функций (UDF) в модуле Knn
.
Функции преобразования вектора в бинарное представление
Функции преобразования нужны для сериализации векторов во внутреннее бинарное представление и обратно.
Все функции сериализации упаковывают возвращаемые данные типа String
в Tagged тип.
Бинарное представление вектора можно сохранить в YDB колонку.
Примечание
В настоящий момент YDB не поддерживает хранение Tagged
типов и поэтому перед сохранением бинарного представления векторов нужно извлечь String
с помощью функции Untag.
Примечание
В настоящий момент YDB не поддерживает построение векторных индексов для бинарных векторов BitVector
.
Сигнатуры функций
Knn::ToBinaryStringFloat(List<Float>{Flags:AutoMap})->Tagged<String, "FloatVector">
Knn::ToBinaryStringUint8(List<Uint8>{Flags:AutoMap})->Tagged<String, "Uint8Vector">
Knn::ToBinaryStringInt8(List<Int8>{Flags:AutoMap})->Tagged<String, "Int8Vector">
Knn::ToBinaryStringBit(List<Double>{Flags:AutoMap})->Tagged<String, "BitVector">
Knn::ToBinaryStringBit(List<Float>{Flags:AutoMap})->Tagged<String, "BitVector">
Knn::ToBinaryStringBit(List<Uint8>{Flags:AutoMap})->Tagged<String, "BitVector">
Knn::ToBinaryStringBit(List<Int8>{Flags:AutoMap})->Tagged<String, "BitVector">
Knn::FloatFromBinaryString(String{Flags:AutoMap})->List<Float>?
Детали имплементации
ToBinaryStringBit
преобразует в 1
все координаты которые больше 0
, остальные координаты преобразуются в 0
.
Функции расстояния и сходства
Функции расстояния и сходства принимают на вход два вектора и возвращают расстояние/сходство между ними.
Примечание
Функции расстояния возвращают малое значение для близких векторов, функции сходства возвращают большие значения для близких векторов. Это следует учитывать в порядке сортировки.
Функции сходства:
- скалярное произведение
InnerProductSimilarity
(сумма произведений координат) - косинусное сходство
CosineSimilarity
(скалярное произведение разделенное на произведение длин векторов)
Функции расстояния:
- косинусное расстояние
CosineDistance
(1 - косинусное сходство) - манхэттенское расстояние
ManhattanDistance
, также известно какL1 distance
(сумма модулей покоординатной разности) - Евклидово расстояние
EuclideanDistance
, также известно какL2 distance
(корень суммы квадратов покоординатной разности)
Сигнатуры функций
Knn::InnerProductSimilarity(String{Flags:AutoMap}, String{Flags:AutoMap})->Float?
Knn::CosineSimilarity(String{Flags:AutoMap}, String{Flags:AutoMap})->Float?
Knn::CosineDistance(String{Flags:AutoMap}, String{Flags:AutoMap})->Float?
Knn::ManhattanDistance(String{Flags:AutoMap}, String{Flags:AutoMap})->Float?
Knn::EuclideanDistance(String{Flags:AutoMap}, String{Flags:AutoMap})->Float?
В случае отличающихся длины или формата, эти функции возвращают NULL
.
Примечание
Все функции расстояния и сходства поддерживают перегрузки с аргументами одного из типов Tagged<String, "FloatVector">
, Tagged<String, "Uint8Vector">
, Tagged<String, "Int8Vector">
, Tagged<String, "BitVector">
.
Если оба аргумента Tagged
, то значение тега должно совпадать, иначе запрос завершится с ошибкой.
Пример:
Error: Failed to find UDF function: Knn.CosineDistance, reason: Error: Module: Knn, function: CosineDistance, error: Arguments should have same tags, but 'FloatVector' is not equal to 'Uint8Vector'
Примеры точного поиска
Создание таблицы
CREATE TABLE Facts (
id Uint64, -- Id of fact
user Utf8, -- User name
fact Utf8, -- Human-readable description of a user fact
embedding String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringFloat)
PRIMARY KEY (id)
);
Добавление векторов
$vector = [1.f, 2.f, 3.f, 4.f];
UPSERT INTO Facts (id, user, fact, embedding)
VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryStringFloat($vector), "FloatVector"));
Точный поиск K ближайших векторов
$K = 10;
$TargetEmbedding = Knn::ToBinaryStringFloat([1.2f, 2.3f, 3.4f, 4.5f]);
SELECT * FROM Facts
WHERE user="Williams"
ORDER BY Knn::CosineDistance(embedding, $TargetEmbedding)
LIMIT $K;
Точный поиск векторов, находящихся в радиусе R
$R = 0.1f;
$TargetEmbedding = Knn::ToBinaryStringFloat([1.2f, 2.3f, 3.4f, 4.5f]);
SELECT * FROM Facts
WHERE Knn::CosineDistance(embedding, $TargetEmbedding) < $R;
Примеры приближенного поиска
Данный пример отличается от примера с точным поиском использованием битового квантования.
Это позволяет сначала делать грубый предварительный поиск по колонке embedding_bit
, а затем уточнять результаты по основной колонке с векторами embedding
.
Создание таблицы
CREATE TABLE Facts (
id Uint64, -- Id of fact
user Utf8, -- User name
fact Utf8, -- Human-readable description of a user fact
embedding String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringFloat)
embedding_bit String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringBit)
PRIMARY KEY (id)
);
Добавление векторов
$vector = [1.f, 2.f, 3.f, 4.f];
UPSERT INTO Facts (id, user, fact, embedding, embedding_bit)
VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryStringFloat($vector), "FloatVector"), Untag(Knn::ToBinaryStringBit($vector), "BitVector"));
Скалярное квантование
ML модель может выполнять квантование или это можно сделать вручную с помощью YQL.
Ниже приведен пример квантования в YQL.
Float -> Int8
$MapInt8 = ($x) -> {
$min = -5.0f;
$max = 5.0f;
$range = $max - $min;
RETURN CAST(Math::Round(IF($x < $min, -127, IF($x > $max, 127, ($x / $range) * 255))) As Int8)
};
$FloatList = [-1.2f, 2.3f, 3.4f, -4.7f];
SELECT ListMap($FloatList, $MapInt8);
Приближенный поиск K ближайших векторов: битовое квантование
Алгоритм приближенного поиска:
- производится приближенный поиск с использованием битового квантования;
- получается приближенный список векторов;
- в этом списке производим поиск без использования квантования.
$K = 10;
$Target = [1.2f, 2.3f, 3.4f, 4.5f];
$TargetEmbeddingBit = Knn::ToBinaryStringBit($Target);
$TargetEmbeddingFloat = Knn::ToBinaryStringFloat($Target);
$Ids = SELECT id FROM Facts
ORDER BY Knn::CosineDistance(embedding_bit, $TargetEmbeddingBit)
LIMIT $K * 10;
SELECT * FROM Facts
WHERE id IN $Ids
ORDER BY Knn::CosineDistance(embedding, $TargetEmbeddingFloat)
LIMIT $K;