近似最近邻搜索简介

精确的最近邻搜索（k近邻或KNN）在高维空间中成本极高，因为在2D或3D空间中有效的空间划分方法，如四叉树或k-d树，在高维情况下会退化为线性扫描。这正是所谓的“维度灾难”的一个方面。

对于大规模数据集而言，在对数时间内得到一个近似答案，往往比在线性时间内得到精确答案更有用。这种搜索方式简称为ANN（近似最近邻）搜索。

ANN索引主要分为两大类：

• 基于分区的索引，例如LSH或IVF以及SCANN
• 基于图的索引，例如HNSW和DiskANN

基于图的索引通常实现更简单、速度更快，更重要的是，它们可以增量构建和更新。这使得它们比仅适用于预先完全指定的静态数据集的分区方法更适合通用索引。因此，所有主流的商业向量索引都采用基于图的方法。

JVector是一种结合了DiskANN和HNSW两种技术的图索引。它从HNSW中借鉴了层次结构，并在每一层内部使用Vamana算法（即DiskANN所采用的算法）。

JVector架构

JVector是一种基于图的索引，它在HNSW和DiskANN的设计基础上进行了可组合的扩展。

JVector实现了一个多层图结构，并采用了无阻塞并发控制机制，从而使得构建过程能够随着核心数量线性扩展：

层次结构的上层由每个节点的内存中邻接表表示，这样可以在无需I/O操作的情况下快速导航。而图的底层则由每个节点的磁盘邻接表表示。JVector利用内联存储的额外数据支持两阶段搜索：第一阶段使用保存在内存中的向量有损压缩表示进行检索，第二阶段则使用从磁盘读取的更精确表示。第一阶段可以采用以下方式：

• 乘积量化（PQ），可选配各向异性加权
• 二值量化（BQ）
• 融合PQ，即将PQ码本直接写入图的邻接表中

第二阶段则可以使用：

• 全精度float32向量
• NVQ，它采用非均匀量化技术来对向量进行高精度量化

这种两阶段设计能够在保持精度的同时降低内存占用并缩短延迟时间。（参考：Why Vector Size Matters）。此外，JVector的独特之处在于它还支持使用两阶段搜索来构建索引本身，从而允许构建超出内存容量的大规模索引：

这一点非常重要，因为它使您能够在单个索引中享受对数级搜索的优势，而不必再将结果合并到多个索引中，从而避免线性时间的合并操作。

JVector入门

JVector的入门教程可在docs/tutorials目录下找到。您可以从基础教程开始，或者查看VectorIntro.java，以获取一个简单的JVector使用示例。

旧版的JV分步指南可以在这里找到：[docs/legacy/jvector-step-by-step.md]。新用户应优先阅读上述教程，但分步指南对于高级用户仍具有参考价值。

算法背后的研究

• 基础性工作：HNSW和DiskANN论文，以及一篇更高层次的解释文章Hierarchical Navigable Small Worlds
• 各向异性PQ论文
• 更快的ADC论文
• NVQ论文

开发与测试

本项目采用 多模块 Maven 构建 的方式组织。其目标是生成一个适用于作为任何 Java 11 代码依赖的多发行版 JAR 文件。当在启用了向量模块的 Java 20 及更高版本 JVM 上运行时，将使用优化的向量提供程序。总体而言，该项目的设计支持使用 JDK 20 及更高版本进行构建，但当 JAVA_HOME 设置为 Java 11 到 Java 19 版本时，某些构建功能仍然可用。

基础代码位于 jvector-base，将针对 Java 11 发行版进行构建，并相应地限制语言特性及 API 的使用。jvector-twenty 中的代码则会编译为 Java 20 的语言特性及 API，并包含在最终面向受支持 JVM 的多发行版 JAR 中。jvector-multirelease 将 jvector-base 和 jvector-twenty 打包成一个多发行版 JAR 用于发布。jvector-examples 是一个额外的同级模块，它利用 jvector-base/jvector-twenty 的反应堆表示来运行示例代码。jvector-tests 包含项目的测试用例，既可以在 Java 11 上运行，也可以在 Java 20 及更高版本的 JVM 上运行。

要运行测试，请使用 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 的一个小问题：当子模块的测试集为空时，Surefire 仍会执行 test 目标；但一旦您提供了过滤条件，它就会要求每个子模块中至少有一个匹配项。）

您可以直接运行 SiftSmall 和 Bench，以了解当前的工作内容。Bench 会自动将所需的数据集下载到 dataset_cache 目录下。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"

若要在没有 JVM 向量模块的情况下运行 Sift 或 Bench，可以使用以下命令：

mvn -Pjdk11 compile exec:exec@bench

mvn -Pjdk11 compile exec:exec@sift

带有 ... -Pjdk11 的命令同样适用于 JAVA_HOME 指向 Java 11 安装的情况。

有关运行基准测试的更多信息，请参阅 docs/benchmarking.md。

要发布，请配置 ~/.m2/settings.xml 以指向 OSSRH，并运行 mvn -Prelease clean deploy。

---

JVector 快速上手指南

JVector 是一个高性能的图基于近似最近邻（ANN）搜索索引库，融合了 HNSW 的层级结构与 DiskANN (Vamana) 算法。它支持非阻塞并发构建、两阶段搜索（内存压缩 + 磁盘高精度）以及超大索引的构建，适用于需要低延迟和高吞吐量的向量检索场景。

环境准备

系统要求

• JDK 版本：
  • 基础运行：Java 11 或更高版本。
  • 性能优化：推荐使用 Java 20+。在 Java 20+ 环境下并启用 Vector 模块时，JVector 会自动使用优化的向量提供者以获得最佳性能。
• 构建工具：Apache Maven 3.6+。
• 操作系统：Linux, macOS, Windows (支持多核线性扩展)。

前置依赖

本项目采用多模块 Maven 构建。无需额外安装第三方向量数据库，JVector 作为库直接嵌入您的 Java 应用中。

安装步骤

将 JVector 添加为您的 Maven 项目依赖。请在 pom.xml 的 <dependencies> 部分添加以下内容（请替换为最新的版本号）：

<dependency>
    <groupId>io.github.jbellis</groupId>
    <artifactId>jvector-multirelease</artifactId>
    <version>0.5.0</version> <!-- 请检查 Maven Central 获取最新版本 -->
</dependency>

提示：该构件是一个多发布 Jar (Multi-Release Jar)，会自动根据您运行的 JDK 版本加载对应的优化代码（Java 11 基础版或 Java 20+ 优化版）。

基本使用

以下是最简单的入门示例，演示如何创建索引、添加向量并执行搜索。

1. 代码示例

您可以参考项目中的 VectorIntro.java 逻辑，以下是一个简化的核心用法演示：

import io.github.jbellis.jvector.graph.GraphIndex;
import io.github.jbellis.jvector.graph.GraphIndexBuilder;
import io.github.jbellis.jvector.vector.VectorSimilarityFunction;
import io.github.jbellis.jvector.vector.VectorizationProvider;
import org.apache.lucene.util.RamUsageEstimator;

import java.util.Random;

public class QuickStart {
    public static void main(String[] args) {
        // 1. 初始化向量化提供者 (自动检测是否启用 Java 20+ Vector 模块)
        VectorizationProvider provider = VectorizationProvider.getInstance();

        // 2. 配置参数
        int dimension = 128;
        int maxConnections = 16;
        int beamWidth = 64;
        
        // 3. 创建索引构建器
        // 使用余弦相似度 (COSINE)，也可选择 DOT_PRODUCT 或 EUCLIDEAN
        GraphIndexBuilder builder = new GraphIndexBuilder(
            maxConnections, 
            beamWidth, 
            VectorSimilarityFunction.COSINE
        );

        // 4. 模拟数据并添加到索引
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            float[] vector = new float[dimension];
            for (int j = 0; j < dimension; j++) {
                vector[j] = random.nextFloat();
            }
            // addVector 返回内部 ID，通常从 0 开始递增
            builder.addVector(i, vector);
        }

        // 5. 构建完成，获取只读索引实例
        GraphIndex index = builder.build();

        // 6. 执行搜索 (K=10)
        float[] queryVector = new float[dimension];
        for (int j = 0; j < dimension; j++) {
            queryVector[j] = random.nextFloat();
        }

        // search 返回结果节点 ID 列表和对应的距离
        var results = index.search(queryVector, 10);

        System.out.println("Top 10 neighbors found:");
        for (int i = 0; i < results.size(); i++) {
            System.out.printf("Node ID: %d, Distance: %f%n", 
                results.getNodeId(i), results.getDistance(i));
        }
        
        // 7. 释放资源 (如果不再需要)
        index.close();
    }
}

2. 运行官方示例与基准测试

如果您想直接运行项目自带的教程或基准测试，可以使用以下 Maven 命令：

运行基础教程示例 (SiftSmall):

mvn compile exec:exec@sift

运行基准测试 (Bench): 此命令会自动下载数据集到 dataset_cache 目录。

mvn compile exec:exec@bench

指定数据集运行基准测试: 仅运行 glove 和 nytimes 数据集的测试：

mvn compile exec:exec@bench -DbenchArgs="glove nytimes"

在 Java 11 环境下运行 (不使用 Vector 模块优化):

mvn -Pjdk11 compile exec:exec@bench

3. 进阶学习

• 详细教程：查看 docs/tutorials/1-intro-tutorial.md。
• 完整代码示例：参考 jvector-examples/src/main/java/io/github/jbellis/jvector/example/tutorial/VectorIntro.java。
• 架构细节：JVector 支持两阶段搜索（内存中使用 PQ/BQ 压缩向量进行初筛，磁盘读取 Float32/NVQ 高精度向量进行重排序），适合处理超出内存容量的大规模索引。