Слияние кода завершено, страница обновится автоматически
Точный поиск ближайшего соседа (k-ближайших соседей или KNN) становится невероятно дорогим по затратам на вычисления при высокой размерности пространства, поскольку подходы к сегментации пространства поиска, такие как quadtree или k-d tree, эффективные в OnClickListener 2D или 3D, превращаются в линейные сканирования при более высоких размерностях. Это одна из аспектов, известная как "проклятие высокой размерности".
С увеличением объема данных почти всегда полезнее получить приближенный ответ за время, логарифмически зависящее от размера входных данных, чем точный ответ за линейное время. Этот метод сокращенно называется ANN (приближенный поиск ближайшего соседа).
Существует две основные категории индексов ANN:
JVector использует иерархическую структуру, заимствованную из HNSW, и применяет алгоритм Vamana (алгоритм, лежащий в основе DiskANN) внутри каждого уровня.
JVector представляет собой графовый индекс, который строится на основе дизайнов HNSW и DiskANN с использованием модульных расширений.JVector реализует многоместный граф с управлением конкурентным доступом без блокировки, позволяющим масштабировать построение линейно с количеством ядер процессора:
Верхние уровни иерархии представлены в виде ин-мемори списка смежных узлов для каждого узла. Это позволяет быстро навигировать без операций ввода-вывода.
Нижний уровень графа представлен в виде на-диск списка смежных узлов для каждого узла. JVector использует дополнительные данные, хранящиеся встроенно, чтобы поддерживать двухпроходные поиски, с первым проходом, который работает на основе потери качества сжатия представлений векторов, хранящихся в памяти, а второй — на основе более точного представления, считываемого с диска. Первый проход может выполняться с использованием
Кроме того, JVector уникален тем, что предлагает возможность самостоятельно создавать индекс с помощью двухэтапных поисков, что позволяет строить индексы, превышающие объем оперативной памяти:
Это важно, так как позволяет использовать логарифмический поиск внутри одного индекса вместо переноса на линейное время объединения результатов из нескольких индексов.
Все примеры кода взяты из SiftSmall в репозитории исходного кода JVector, который также включает набор данных siftsmall. Просто импортируйте проект в вашу среду разработки и нажмите кнопку "Run", чтобы попробовать его!#### Шаг 1: Создание и запрос индекса в оперативной памяти
Первый код:
public static void siftInMemory(ArrayList<VectorFloat<?>> baseVectors) throws IOException {
// определяем размерность из первого вектора
int originalDimension = baseVectors.get(0).length();
// оборачиваем сырые векторы в RandomAccessVectorValues
RandomAccessVectorValues ravv = new ListRandomAccessVectorValues(baseVectors, originalDimension);
// создаем провайдера оценок с использованием сырых, встроенных в память векторов
BuildScoreProvider bsp = BuildScoreProvider.randomAccessScoreProvider(ravv, VectorSimilarityFunction.EUCLIDEAN);
try (GraphIndexBuilder builder = new GraphIndexBuilder(bsp,
ravv.dimension(),
16, // степень графа
100, // глубина поиска при построении
1.2f, // допустимое превышение степени графа во время построения этим коэффициентом
1.2f, // снижение требований к разнообразию соседей этим коэффициентом (альфа)
true)) // использование иерархического индекса
{
// строим индекс (в памяти)
OnHeapGraphIndex index = builder.build(ravv);
// поиск случайного вектора
VectorFloat<?> q = randomVector(оригинальная_размерность);
SearchResult sr = GraphSearcher.search(q,
10, // количество результатов
ravv, // векторы, которые мы ищем, используются для оценки
``````java
VectorSimilarityFunction.EUCLIDEAN, // как оценивать схожесть
индекс,
Bits.ALL); // допустимые ordinal'ы для рассмотрения
for (SearchResult.NodeScore ns : sr.getNodes()) {
System.out.println(ns);
}
Комментарий:
getVector и getVectorInto. Обратите внимание на метод isValueShared() в многопоточной среде; как правило, в памяти RAVV не использует общие значения, а для RAVV с диска это используется как оптимизация для избежания выделения нового вектора на куче для каждого вызова.#### Шаг 2: более детальный контроль над GraphSearcherОставив Builder неизменным, обновленный код поиска выглядит следующим образом: // поиск случайного вектора с помощью GraphSearcher и SearchScoreProvider
VectorFloat<?> q = randomVector(originalDimension);
try (GraphSearcher searcher = new GraphSearcher(index)) {
SearchScoreProvider ssp = SearchScoreProvider.exact(q, VectorSimilarityFunction.EUCLIDEAN, ravv);
SearchResult sr = searcher.search(ssp, 10, Bits.ALL);
for (SearchResult.NodeScore ns : sr.getNodes()) {
System.out.println(ns);
}
}
Комментарий:
Function<VectorFloat<?>, SearchScoreProvider> sspFactory = q -> SearchScoreProvider.exact(q, VectorSimilarityFunction.EUCLIDEAN, ravv);
testRecall(index, queryVectors, groundTruth, sspFactory);
Если вы запустите код, вы заметите небольшие различия в recall каждый раз (выведенные методом testRecall):
(OnHeapGraphIndex) Recall: 0.9898
...
(OnHeapGraphIndex) Recall: 0.9890
Это ожидаемо, учитывая приближенный характер создаваемого индекса и возмущения, вносимые многопоточной конкуренцией вызова build.#### Шаг 4: запись и загрузка индекса на диск и обратно
Код:
Path indexPath = Files.createTempFile("siftsmall", ".inline");
try (GraphIndexBuilder builder = new GraphIndexBuilder(bsp, ravv.dimension(), 16, 100, 1.2f, 1.2f, true)) {
// создаем индекс в памяти
OnHeapGraphIndex index = builder.build(ravv);
// записываем индекс на диск с использованием стандартных опций
OnDiskGraphIndex.write(index, ravv, indexPath);
}
// индексы на диске требуют ReaderSupplier, так как нам потребуется открыть дополнительные читатели для поиска
ReaderSupplier rs = ReaderSupplierFactor.open(indexPath);
OnDiskGraphIndex index = OnDiskGraphIndex.load(rs);
// измеряем наш recall относительно точно вычисленной ground truth
Function<VectorFloat<?>, SearchScoreProvider> sspFactory = q -> SearchScoreProvider.exact(q, VectorSimilarityFunction.EUCLIDEAN, index.getView());
testRecall(index, queryVectors, groundTruth, sspFactory);
```Комментарий:
* Мы можем записывать индексы, созданные в памяти, на диск с помощью одного вызова метода.
* Загрузка и поиск по индексам на диске требуют ReaderSupplier, который поставляет объекты RandomAccessReader. Интерфейс RandomAccessReader предназначен для расширения проектом-потребителем. Например, [DataStax Astra](https://www.datastax.com/products/datastax-astra) реализует RandomAccessReader, используя кэш-чанков Cassandra. JVector предоставляет две реализации из коробки.
* SimpleMappedReader: реализован с использованием FileChannel.map, что означает, что он совместим со всеми версиями Java, способными запустить JVector, но также ограничивается размером файла до 2 ГБ. SimpleMappedReader主要用于示例代码。
* MemorySegmentReader: реализован с использованием нового API MemorySegment, без ограничений по размеру файла, но ограничен версией Java 22+. (Фактический код MemorySegmentReader совместим с Java 20+, но [мы оставили его в модуле 22+ для удобства](https://github.com/jbellis/jvector/pull/296). Внедренный читатель может переработать сборку для улучшения этого.) Если у вас нет специальных требований, MemorySegmentReader рекомендован для использования в производстве.
---
Комментарий:
* Мы можем записывать индексы, созданные в памяти, на диск с помощью одного вызова метода.
* Загрузка и поиск по индексам на диске требуют ReaderSupplier, который поставляет объекты RandomAccessReader. Интерфейс RandomAccessReader предназначен для расширения проектом-потребителем. Например, [DataStax Astra](https://www.datastax.com/products/datastax-astra) реализует RandomAccessReader, используя кэш-чанков Cassandra. JVector предоставляет два реализации из коробки.
* SimpleMappedReader: реализован с использованием FileChannel.map, что означает, что он совместим со всеми версиями Java, способными запустить JVector, но также ограничивается размером файла до 2 ГБ. SimpleMappedReader主要用于示例代码。
* MemorySegmentReader: реализован с использованием нового API MemorySegment, без ограничений по размеру файла, но ограничен версией Java 22+. (Фактический код MemorySegmentReader совместим с Java 20+, но [мы оставили его в модуле 22+ для удобства](https://github.com/jbellis/jvector/pull/296). Внедренный читатель может переработать сборку для улучшения этого.) Если у вас нет специальных требований, MemorySegmentReader рекомендован для использования в производстве.#### Шаг 5: использовать сжатые векторы в поиске
Сжатие векторов с помощью продукт-квантизации выполняется следующим образом:
```java
// вычисление и запись сжатых векторов на диск
Path pqPath = Files.createTempFile("siftsmall", ".pq");
try (DataOutputStream out = new DataOutputStream(new BufferedOutputStream(Files.newOutputStream(pqPath)))) {
// Сжатие исходных векторов с помощью PQ. Это представляет собой коэффициент сжатия 128 * 4 / 16 = 32x
ProductQuantization pq = ProductQuantization.compute(ravv,
16, // количество подпространств
256, // количество центроидов на подпространство
true); // центрирование набора данных
// Примечание: до версии jvector 3.1.0, метод encodeAll возвращал массив объектов ByteSequence.
PQVectors pqv = pq.encodeAll(ravv);
// запись сжатых векторов на диск
pqv.write(out);
}
ReaderSupplier rs = ReaderSupplierFactory.open(indexPath);
OnDiskGraphIndex index = OnDiskGraphIndex.load(rs);
// загрузка PQVectors, которые мы только что записали на диск
try (ReaderSupplier pqSupplier = ReaderSupplierFactory.open(pqPath);
RandomAccessReader in = pqSupplier.get())
{
PQVectors pqv = PQVectors.load(in);
``````markdown
// SearchScoreProvider, который выполняет первый проход с использованием загруженных в память PQVectors,
// затем переоценку с помощью точных векторов, хранящихся на диске в индексе
Function<VectorFloat<?>, SearchScoreProvider> sspFactory = q -> {
ApproximateScoreFunction asf = pqv.precomputedScoreFunctionFor(q, VectorSimilarityFunction.EUCLIDEAN);
Reranker reranker = index.getView().rerankerFor(q, VectorSimilarityFunction.EUCLIDEAN);
return new SearchScoreProvider(asf, reranker);
};
// измерение нашего recall против точно вычисленной ground truth
testRecall(index, queryVectors, groundTruth, sspFactory);
}
JVector также может применять сжатие PQ для индексации набора данных, превышающего объем памяти: в памяти хранятся только сжатые векторы.
Сначала нам нужно настроить экземпляр PQVectors, который можно использовать для добавления новых векторов, а также BuildScoreProvider с его использованием:
```java
// вычисляем кодбук, но пока не кодируем никаких векторов
ProductQuantization pq = ProductQuantization.compute(ravv, 16, 256, true);
// при построении индекса мы будем сжимать новые векторы и добавлять их в этот список, который поддерживает PQVectors;
// это используется для оценки поиска при построении
List<ByteSequence<?>> incrementallyCompressedVectors = new ArrayList<>();
PQVectors pqv = new PQVectors(pq, incrementallyCompressedVectors);
BuildScoreProvider bsp = BuildScoreProvider.pqBuildScoreProvider(VectorSimilarityFunction.EUCLIDEAN, pqv);
```Затем нам нужно настроить OnDiskGraphIndexWriter с полным контролем над процессом построения.
```java
Path indexPath = Files.createTempFile("siftsmall", ".inline");
Path pqPath = Files.createTempFile("siftsmall", ".pq");
// Создание билдера выглядит почти одинаково
try (GraphIndexBuilder builder = new GraphIndexBuilder(bsp, ravv.dimension(), 16, 100, 1.2f, 1.2f, true);
// явный Writer впервые, это то, что стоит за OnDiskGraphIndex.write
OnDiskGraphIndexWriter writer = new OnDiskGraphIndexWriter.Builder(builder.getGraph(), indexPath)
.with(new InlineVectors(ravv.dimension()))
.withMapper(new OnDiskGraphIndexWriter.IdentityMapper())
.build();
// выход для сжатых векторов
DataOutputStream pqOut = new DataOutputStream(new BufferedOutputStream(Files.newOutputStream(pqPath))))
После выполнения этого, мы можем индексировать векторы по одному:
// создаем индекс вектор по одному (на диске)
for (VectorFloat<?> v : baseVectors) {
// сжимаем новый вектор и добавляем его в PQVectors (через incrementallyCompressedVectors)
int ordinal = incrementallyCompressedVectors.size();
incrementallyCompressedVectors.add(pq.encode(v));
// записываем полный вектор на диск
writer.writeInline(ordinal, Feature.singleState(FeatureId.INLINE_VECTORS, new InlineVectors.State(v)));
// теперь добавляем его в граф -- предыдущие шаги должны быть завершены первыми, так как PQVectors
// и InlineVectorValues используются во время поиска, который выполняется как часть addGraphNode
builder.addGraphNode(ordinal, v);
}
Наконец, нам нужно запустить cleanup() и записать индекс и PQVectors на диск:
``` // cleanup выполняет окончательное ограничение maxDegree и обрабатывает другие сценарии, такие как удаленные узлы,
// которые здесь нам не нужно беспокоиться
builder.cleanup();
Комментарий:
* Объекты типа ThreadLocal в JDK могут быть использованы только из потока, который их создал. Это сложная конструкция, в которую сложно вписать кэширование объектов типа Closeable, таких как GraphSearcher. Библиотека JVector предоставляет класс ExplicitThreadLocal для решения этой проблемы.
* Объединённый ADC совместим только с Product Quantization, а не с Binary Quantization. Это не является значительной потерей, так как [очень мало моделей генерируют эмбеддинги, которые лучше всего подходят для BQ](https://thenewstack.io/why-vector-size-matters/). Тем не менее, BQ продолжает поддерживаться с помощью неподключенных индексов.
```* Библиотека JVector широко использует API Panama Vector (SIMD) для индексации и поиска ANN. Мы видели случаи, когда пропускная способность памяти достигает своего предела во время индексации и продукт-квантизации, что может замедлить процесс. Чтобы избежать этого, методы сборки индекса и PQ используют [PhysicalCoreExecutor](https://javadoc.io/doc/io.github.jbellis/jvector/latest/io/github/jbellis/jvector/util/PhysicalCoreExecutor.html) для ограничения количества операций до количества физических ядер. По умолчанию значение равно половине количества процессоров, которое видит Java. Это может не быть правильным во всех конфигурациях (например, отсутствие гиперпотоков или гибридные архитектуры), поэтому, если вы хотите переопределить значение по умолчанию, используйте свойство `-Djvector.physical_core_count`, или передайте свой собственный экземпляр ForkJoinPool.### Расширенные возможности* Объединённый ADC представлен как Функционал, который поддерживается при построении инкрементного индекса, как InlineVectors выше. [Пример кода в классе Grid](https://github.com/jbellis/jvector/blob/main/jvector-examples/src/main/java/io/github/jbellis/jvector/example/Grid.java).
* Анизотропическое PQ встроено в класс ProductQuantization и может улучшить recall, но никто не знает, как его настраивать (с параметром T/threshold), кроме экспериментального подхода на уровне каждого отдельного модели, и неправильная настройка может ухудшить ситуацию. По графику 3 в статье:
* JVector поддерживает удаление узлов на месте через метод GraphIndexBuilder::markNodeDeleted. Удалённые узлы удаляются и соединения заменяются во время GraphIndexBuilder::cleanup, с временем выполнения пропорциональным количеству удалённых узлов.
* Чтобы сделать снимок графа и перезагрузить его для продолжения редактирования, используйте методы OnHeapGraphIndex::save и GraphIndexBuilder::load.
## Исследования за алгоритмами
* Основные работы: [HNSW](https://ieeexplore.ieee.org/abstract/document/8594636) и [DiskANN](https://suhasjs.github.io/files/diskann_neurips19.pdf) статьи, и [высокоуровневое объяснение](https://www.datastax.com/guides/hierarchical-navigable-small-worlds)
* [Статья об анизотропическом PQ](https://arxiv.org/abs/1908.10396)
* [Статья о более быстром ADC](https://arxiv.org/abs/1812.09162)## Разработка и тестирование
Проект организован как [мультимодульное сборочное дерево Maven](https://maven.apache.org/guides/mini/guide-multiple-modules.html). Цель состоит в том, чтобы создать многоверсионный jar, подходящий для использования как зависимость из любого Java 11 кода. При запуске на JVM Java 20+ с включенным модулем Vector будут использоваться оптимизированные провайдеры векторов. В общем, проект структурирован так, чтобы можно было собирать его с JDK 20+, но когда переменная окружения `JAVA_HOME` установлена на Java 11 -> Java 19, некоторые функции сборки всё ещё доступны. Основной код находится в [jvector-base](./jvector-base) и будет собран для выпусков Java 11, ограничивая языковые возможности и API соответственно. Код в [jvector-twenty](./jvector-twenty) будет скомпилирован с использованием языковых возможностей и API Java 20 и включен в окончательный многоверсионный JAR, предназначенный для поддерживаемых JVM. [jvector-multirelease](./jvector-multirelease) упаковывает [jvector-base](./jvector-base) и [jvector-twenty](./jvector-twenty) как многоверсионный JAR для выпуска. [jvector-examples](./jvector-examples) — это дополнительный модуль-брат, использующий реакторное представление jvector-base/jvector-twenty для запуска примеров кода. [jvector-tests](./jvector-tests) содержит тесты для проекта, способные выполняться как на JVM Java 11, так и на JVM Java 20+. Чтобы запустить тесты, используйте `mvn test`. Чтобы запустить тесты с использованием Java 20+ версий, используйте `mvn test`.Чтобы запустить тесты с использованием Java 11, используйте `mvn -Pjdk11 test`.Чтобы запустить отдельный тестовый класс, используйте возможность фильтрации тестов Maven Surefire, например,
`mvn -Dsurefire.failIfNoSpecifiedTests=false -Dtest=TestNeighborArray test`.
Вы также можете использовать методы уровня фильтрации и шаблонов, например,
`mvn -Dsurefire.failIfNoSpecifiedTests=false -Dtest=TestNeighborArray#testRetain* test`.
(Параметр `failIfNoSpecifiedTests` работает вокруг особенности surefire: он счастлив запускать `test` с подмодулями с пустыми наборами тестов,
но как только вы предоставляете фильтр, он хочет хотя бы одного совпадения в каждом подмодуле.)
Вы можете запустить `SiftSmall` и `Bench` напрямую, чтобы получить представление о том, что происходит здесь. `Bench` автоматически скачивает необходимые наборы данных в директорию `fvec` и `hdf5`.
Файлы, используемые `SiftSmall`, можно найти в директории [siftsmall](./siftsmall) в корне проекта.
Чтобы запустить любой из этих классов, вы можете использовать плагин Maven exec через следующие команды:
> `mvn compile exec:exec@bench`
или для Sift:
> `mvn compile exec:exec@sift`
`Bench` принимает необязательный аргумент `benchArgs`, который можно установить в список пробелами-разделенных регулярных выражений. Если любое из предоставленных регулярных выражений совпадает с названием набора данных, этот набор данных будет включен в бенчмарк. Например, чтобы запустить только наборы данных glove и nytimes, вы могли бы использовать:> `mvn compile exec:exec@bench -DbenchArgs="glove nytimes"`
Чтобы запустить Sift/Bench без доступного модуля векторов JVM, вы можете использовать следующие команды:
> `mvn -Pjdk11 compile exec:exec@bench`
> `mvn -Pjdk11 compile exec:exec@sift`
Команды `... -Pjdk11` также будут работать, если `JAVA_HOME` указывает на установку Java 11.
Чтобы выполнить релиз, настройте `~/.m2/settings.xml` для указания на OSSRH и запустите `mvn -Prelease clean deploy`.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Комментарии ( 0 )