Вот, например, Milvius(DiskANN) рассчитан на вектора размерности до 32 768, но это приближенный поиск. Но как насчёт поиска точного?

В данной статье рассматривается работоспособность 1024 мерного индекса, хранилищем которого служит обычное B‑дерево (насколько вообще может быть обычным такое дерево). Используемый диск — вполне себе «железный» старый добрый WD Purple, оперативная память сознательно ограничена 8 Гб. Можно ли что‑то из этого выжать на рядовом десктопе за приемлемое время?

Данная работа опирается на ранее описанный алгоритм:

1. Презентация алгоритма

2. 3D и очевидные оптимизации

3. 8D и перспективы в OLAP

4. 3D на сфере

5. Как насчет индексации неточечных объектов?

6. А что с кривой Гильберта?

7. Заметающие кривые

8. Логический (одноразрядный) многомерный индекс

9. Исходники

Задача

Удачно выбранный пример — половина успеха.

• индексируем 1024-мерные точки. Этого довольно (с точки зрения автора) чтобы прикоснуться к прелестям многомерных пространств. Но недостаточно много, чтобы вся затея превратилась в сплошное занудство. Принципиальное ограничение — на одной странице дерева должно помещаться два и более элемента, иначе, какое же это дерево. Так что, требуется больше размерность — увеличиваем размер страницы.

• точка устроена так: (sin(x), sin(2*x),...,sin(1024*x)) где x принимает значения от 0 до 2? с шагом 0.000002?, всего миллион значений. Миллиона довольно, чтобы почувствовать как устроена задача, но недостаточно …

• значения 8-разрядные, сдвинуты вверх так, чтобы заметать диапазон [0…255]. Автор экспериментировал и с 16-разрядными значениями, принципиально ничего не меняется, разница лишь в том, сколько элементов помещается на странице

• используется кодирование Z‑Order

• после кодирования точка превращается в 8192-разрядное целое число

• в индексе это число выглядит как ключ из 128 беззнаковых 64 разрядных целых чисел

• экспериментируем с размерами страниц от 8 до 64K

• при индексировании применяется сжатие, но для такого рода данных оно мало что даёт

Образец данных в текстовом виде: сначала номер строки, затем 1024 значения

Индексация

При построении индекса каждая точка превращается в 8192 разрядное число, которое заносится в индекс самым обычным образом. Многомерный поиск заключен именно в поиске а не в индексации.

Что касается реализации B‑дерева, в ней нет ничего необычного, вполне заурядное проприетарное дерево. Нет ничего проще, чем написать своё B‑дерево, я сам это делал неоднократно.

• Время индексации (8к страницы): 12«6»«, для остальных страниц примерно то же»

• Пиковое потребление памяти: ~2 Гб, управляется выделенным пулом страниц

• Размер индекса: ~1.25Гб, для всех типов страниц, оно и понятно, объем информации не меняется

• или ~ 156 000 страниц по 8К 

• в среднем число элементов на такой странице: 6.4 
  то есть сжатия практически нет.

Глянем одним глазком что насоздавали

Совместное представление значений в разных размерностях показано ниже.

Поиск в окрестности

Проверим работоспособность индекса, во первых, при поиске на точное совпадение, во вторых, в окрестности искомой точки.

Будем брать произвольные вектора (3 штуки — с номерами 590383, 117806, 711480) из исходных данных, делать поиск вокруг них в расширяющейся окрестности по каждой размерности. Если размер окрестности нулевой, это точное совпадение.

Результатом будет количество прочитанных страниц из холодного состояния и число полученных результатов. Холодное состояние подразумевает отсутствие страниц в кэше и их распаковку при чтении. Но диск всё равно «разогретый» так что собственно физическое чтение не учитывается, для «охлаждения» диска потребуется индекс потолще, размером побольше дискового кэша ОС.

Три точки, конечно не слишком представительная выборка, тем не менее этого достаточно, чтобы получить общее представление о задаче, не впадая в уныние от необходимости миллион раз перезапускать сервер.

Таб.1 Число прочитанных страниц и найденных результатов в расширяющейся окрестности выбранных точек.

Вызывает недоумение, что поиск с радиусом в 128 (то есть во всю область значений) находит всего лишь несколько сотен значений из миллиона. Это одна из особенностей высоких размерностей. Например, если окрестность строится от значения 100, то она получится [0…228], то есть некоторая фильтрация всё‑таки произойдёт. А поскольку размерностей много, в результате отсеется почти всё. На самом деле, удивительно, что вообще хоть что‑то нашлось.

Дело в данных. Младшая часть гармоник изменяется очень медленно. Старшие гармоники меняются примерно со скоростью расширения окрестности. Если размер окрестности равен 3, в ней окажутся сама центральная точка и две её соседки.
Это не специально, так получилось.

Поиск по частично неизвестным данным

Будем использовать те же модельные данные и те же три вектора (590383, 117806, 711480) для поиска в ситуации, когда часть координат(размерностей) не заполнена. В случае когда какая‑та из координат считается неизвестной, для неё подставляется максимально возможный диапазон — в данном случае [0…255].
Неизвестными будем считать значения с начала вектора.
Поиск идёт на точное совпадение известной части вектора.

Таб.2 количество прочитанных страниц в зависимости от известной части точки (вектора)

Кажется совершенно невероятным, что при всего 6 известных координатах точки (и 1018 неизвестных) в индексе нашелся единственный результат. Никакого чуда нет. Старшие координаты соответствуют самым высокочастотным гармоникам и комбинация из нескольких последних координат фактически является случайным числом с равномерным распределением. Поскольку в индексе всего миллион векторов (20 разрядов), а в одном значении — 8, часть вектора, делающая его уникальным должна быть длиннее 3.

В догонку совместное распределение числа прочитанных страниц и времени поиска 

Время поиска состоит (в нашем случае) из двух факторов — распаковка страниц, стоимость которой примерно одинакова для всех страниц и обработка внутренних подзапросов, сложность которой зависит от того, насколько «удачно» искомая точка легла в индекс.

Итого

Мы познакомились с 1024-х мерным поиском, но основной вопрос пока остаётся без ответа. Действительно, насколько он может быть многомерным?

Всё зависит от размера страниц. 8К страницы допускают с некоторым запасом 1024 размерности. Но мы потренировались и на 64К страницах, значит ли это, что можно говорить о 8192 размерном индексе?

Да, вполне. Более того, не запрещено использовать и страницы большего размера. Наоборот, мы видели, что чем большие страницы используются, тем быстрее идёт поиск.
Но есть же какие‑то ограничения?

Разумеется. Во первых, чем больше страницы, тем дороже становятся изменения такого индекса. Одно дело перекомпоновать 8К страницу и совсем другое, когда в ней 256К. Дороже станет и создание индекса, ведь оно подразумевает (кроме тех случаев, когда всё можно отсортировать в памяти) сортировку и произвольную вставку в дерево.

Выше обращалось внимание на то, что значительная часть времени при поиске тратится на генерацию и обработку подзапросов. Этот процесс останавливается, когда текущий подзапрос целиком оказывается на одной листовой странице B‑дерева. В этом случае данная страница просто просматривается целиком. Т.е. чем больше страницы, тем меньше будет порождено подзапросов.

Но есть и другая сторона. Если страница большая, а запросы не очень, значительная часть данных загружается, просматривается и отфильтровывается впустую. Так что это самобалансирующийся процесс. Мы видим, что время поиска в 32 и 64К страницах очень близко. 

На данный момент автор рассматривает 64К страницы как оптимальные (для конкретно этой задачи). Так что вот ответ — 8К — вот число размерностей для векторов, с которым можно будет работать относительно комфортно. Хотя, технически допустимо сделать и намного больше.

PS: спасибо Олегу Бартунову (@zen), сподвигшему меня заняться всем этим.

PPS: титульная картинка взята из к.ф. «Интерстеллар»