Hnswlib - 快速近似最近邻搜索

仅头文件的 C++ HNSW 实现，带有 Python 绑定、插入和更新功能。

新闻：

版本 0.9.0

• 修复了带过滤器的暴力搜索结果不正确的问题 (#514)，由 @lukaszsmolinski 完成
• 修复了 BFIndex 中缺失的归一化检查 (#514)，由 @lukaszsmolinski 完成
• 当可用元素少于 k 个时抛出异常 (#514)，由 @lukaszsmolinski 完成
• 移除未使用的变量 (#531)，由 @lulyon 完成
• 将 README 中的余弦相似度改为距离，由 @yurymalkov 完成

版本 0.8.0

• 多向量文档搜索和 epsilon 搜索（目前仅在 C++ 中支持）
• 默认情况下不再进行统计聚合，这加快了多线程搜索的速度（似乎也确实很少有人使用：Issue #495）。
• 各种错误修复和改进
• get_items 现在增加了 return_type 参数，可选值为 'numpy' 或 'list'

完整变更列表：https://github.com/nmslib/hnswlib/pull/523

版本 0.7.0

• 增加了对过滤的支持 (#402, #430)，由 @kishorenc 完成
• 添加了用于过滤的 Python 接口（但请注意，其性能受限于 GIL）(#417)，由 @gtsoukas 完成
• 支持用新插入的元素替换已被标记为删除的元素，以控制索引大小 (#418)，由 @dyashuni 完成
• 修复了更新/插入操作中的数据竞争/死锁问题，并添加了多线程操作的压力测试 (#418)，由 @dyashuni 完成
• 文档、测试、异常处理、重构工作 (#375, #379, #380, #395, #396, #401, #406, #404, #409, #410, #416, #415, #431, #432, #433)，由 @jlmelville、@dyashuni、@kishorenc、@korzhenevski、@yoshoku、@jianshu93、@PLNech 等完成
• 全局链接 (#383)，由 @MasterAler 完成；MSVC 中使用 USE_SSE (#408)，由 @alxvth 完成

亮点：

1. 轻量级、仅头文件实现，除 C++11 外无其他依赖。
2. 提供 C++ 和 Python 接口，并对外支持 Java 和 R（https://github.com/jlmelville/rcpphnsw）。
3. 完全支持增量式索引构建和元素更新（感谢 Apoorv Sharma 的贡献）。同时支持元素删除操作（通过在索引中标记删除，后续可用其他元素替换）。Python 版本的索引可以被 pickle 序列化。
4. 可与用户自定义的距离函数一起使用（C++）。
5. 相较于当前 nmslib 的实现，内存占用显著降低，构建时间更快。

算法参数的说明请参阅 ALGO_PARAMS.md。

Python 绑定

支持的距离度量：

距离	参数	公式
平方 L2	'l2'	d = sum((Ai-Bi)^2)
内积	'ip'	d = 1.0 - sum(Ai*Bi)
余弦距离	'cosine'	d = 1.0 - sum(Ai*Bi) / sqrt(sum(Ai*Ai) * sum(Bi*Bi))

请注意，内积并不是一个真正的度量。某个元素可能比它自身更接近另一个元素。如果从索引中移除所有不与自身最近的元素，这可以带来一定的性能提升。

对于其他空间，请使用 nmslib 库：https://github.com/nmslib/nmslib。

API 描述

• hnswlib.Index(space, dim) 在空间 space 中创建一个未初始化的 HNSW 索引，维度为整数 dim。

hnswlib.Index 方法：

• init_index(max_elements, M = 16, ef_construction = 200, random_seed = 100, allow_replace_deleted = False) 初始化一个空的索引。

  • max_elements 定义了结构中可存储的最大元素数量（可以增加或减少）。
  • ef_construction 定义了构建时间与准确性之间的权衡（参见 ALGO_PARAMS.md）。
  • M 定义了图中每个节点的最大出边数（参见 ALGO_PARAMS.md）。
  • allow_replace_deleted 允许用新添加的元素替换已删除的元素。

• add_items(data, ids, num_threads = -1, replace_deleted = False) 将 data（形状为 N*dim 的向量 NumPy 数组）插入到结构中。

  • num_threads 设置使用的 CPU 线程数（-1 表示使用默认值）。
  • ids 是可选的 N 大小的整数标签 NumPy 数组，用于 data 中的所有元素。
    • 如果索引中已经存在具有相同标签的元素，其特征将被更新。请注意，更新操作比插入新元素慢，但更节省内存且查询效率更高。
  • replace_deleted 会替换已删除的元素。注意，这有助于节省内存。
    • 要使用此功能，必须在调用 init_index 时设置 allow_replace_deleted=True。
  • 该方法与其他 add_items 调用是线程安全的，但与 knn_query 不是。

• mark_deleted(label) 标记元素为已删除，使其不会出现在搜索结果中。如果元素已被标记为已删除，则会抛出异常。

• unmark_deleted(label) 取消标记已删除的元素，使其会出现在搜索结果中。

• resize_index(new_size) 更改索引的最大容量。与 add_items 和 knn_query 不是线程安全的。

• set_ef(ef) 设置查询时间、准确性和速度之间的权衡，由 ef 参数定义（ALGO_PARAMS.md）。请注意，该参数目前不会与索引一起保存，因此在加载后需要手动设置。

• knn_query(data, k = 1, num_threads = -1, filter = None) 对 data 中的每个元素进行批量查询，返回每个元素最接近的 k 个元素。

  • data（形状为 N*dim）。返回形状为 N*k 的 NumPy 数组。
  • num_threads 设置使用的 CPU 线程数（-1 表示使用默认值）。
  • filter 按标签过滤元素，只返回具有允许 ID 的元素。请注意，在多线程模式下，使用过滤器进行搜索的速度较慢。建议将 num_threads 设置为 1。
  • 该方法与其他 knn_query 调用是线程安全的，但与 add_items 不是。

• load_index(path_to_index, max_elements = 0, allow_replace_deleted = False) 从持久化存储中加载索引到未初始化的索引中。

  • max_elements（可选）重置结构中的最大元素数量。
  • allow_replace_deleted 指定正在加载的索引是否启用了替换已删除元素的功能。

• save_index(path_to_index) 将索引保存到持久化存储中。

• set_num_threads(num_threads) 设置数据插入/查询过程中默认使用的 CPU 线程数。

• get_items(ids, return_type = 'numpy') 返回形状为 N*dim 的向量 NumPy 数组，这些向量的整数标识符在 ids NumPy 向量中指定（形状为 N）。如果 return_type 为 list，则返回列表的列表。请注意，对于余弦相似度，当前返回的是归一化向量。

• get_ids_list() 返回所有元素的 ID 列表。

• get_max_elements() 返回索引的当前容量。

• get_current_count() 返回索引中当前存储的元素数量。

hnswlib.Index 类的只读属性：

• space - 空间名称（可以是 "l2"、"ip" 或 "cosine"）。

• dim - 空间的维数。

• M - 定义图中每个节点最大出边数的参数。

• ef_construction - 控制索引构建过程中速度与准确性之间权衡的参数。

• max_elements - 索引的当前容量。等同于 p.get_max_elements()。

• element_count - 索引中的项目数量。等同于 p.get_current_count()。

hnswlib.Index 支持读写的属性：

• ef - 控制查询时间与准确性之间权衡的参数。

• num_threads - 在 add_items 或 knn_query 中默认使用的线程数。请注意，调用 p.set_num_threads(3) 等同于 p.num_threads=3。

Python 绑定示例

在此处查看更多示例：

• 创建索引、插入元素、搜索、序列化/反序列化
• 使用布尔函数在搜索过程中进行过滤
• 删除元素并重新利用已删除元素的内存来存储新添加的元素

创建索引、插入元素、搜索和 pickle 序列化的示例：

import hnswlib
import numpy as np
import pickle

dim = 128
num_elements = 10000

# 生成示例数据
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)

# 声明索引
p = hnswlib.Index(space = 'l2', dim = dim) # 可能的选项是 l2、cosine 或 ip

# 初始化索引 - 必须事先知道最大元素数量
p.init_index(max_elements = num_elements, ef_construction = 200, M = 16)

# 插入元素（可以多次调用）：
p.add_items(data, ids)

# 通过设置 ef 来控制召回率：
p.set_ef(50) # ef 值应始终大于 k

# 查询数据集，k 表示最接近的元素数量（返回两个 NumPy 数组）
labels, distances = p.knn_query(data, k = 1)

# 索引对象支持 pickle 序列化
# 注意：使用 pickle.dumps(p) 或 p.__getstate__() 进行序列化与 p.add_items 方法不线程安全！
# 注意：ef 参数包含在序列化中；随机数生成器在加载索引时使用 random_seed 进行初始化
p_copy = pickle.loads(pickle.dumps(p)) # 使用 pickle 循环创建索引 p 的副本

### 索引参数作为类属性公开：
print(f"传递给构造函数的参数：space={p_copy.space}, dim={p_copy.dim}") 
print(f"索引构建：M={p_copy.M}, ef_construction={p_copy.ef_construction}")
print(f"索引大小为 {p_copy.element_count}，索引容量为 {p_copy.max_elements}")
print(f"搜索速度与质量的权衡参数：ef={p_copy.ef}")

序列化/反序列化后的更新示例：

import hnswlib
import numpy as np

dim = 16
num_elements = 10000

# 生成示例数据
data = np.float32(np.random.random((num_elements, dim)))

# 我们将数据分为两个批次：
data1 = data[:num_elements // 2]
data2 = data[num_elements // 2:]

# 声明索引
p = hnswlib.Index(space='l2', dim=dim)  # 可选值为 l2、cosine 或 ip

# 初始化索引
# max_elements - 最大元素数量（容量）。如果在插入元素时超出此限制，将会抛出异常。
# 容量可以通过保存/加载索引来增加，详见下文。
#
# ef_construction - 控制索引构建速度与查询速度之间的权衡。
#
# M - 与数据的内部维度紧密相关。强烈影响内存消耗（约与 M 成正比）。
# 较高的 M 值可在固定的 ef/efConstruction 下提高检索准确性和运行时间。

p.init_index(max_elements=num_elements//2, ef_construction=100, M=16)

# 通过设置 ef 来控制召回率：
# 较高的 ef 值可提高准确性，但会降低查询速度。
p.set_ef(10)

# 设置批量搜索/构建过程中使用的线程数
# 默认使用所有可用核心
p.set_num_threads(4)

print("添加第一批次 %d 个元素" % (len(data1)))
p.add_items(data1)

# 查询这些元素自身并测量召回率：
labels, distances = p.knn_query(data1, k=1)
print("第一批次的召回率：", np.mean(labels.reshape(-1) == np.arange(len(data1))), "\n")

# 序列化并删除索引：
index_path='first_half.bin'
print("将索引保存到 '%s'" % index_path)
p.save_index("first_half.bin")
del p

# 重新初始化并加载索引
p = hnswlib.Index(space='l2', dim=dim)  # 空间可以更改——这会保留数据，但改变距离函数。

print("\n从 'first_half.bin' 加载索引\n")

# 增加总容量（max_elements），以便容纳新数据
p.load_index("first_half.bin", max_elements = num_elements)

print("添加第二批次 %d 个元素" % (len(data2)))
p.add_items(data2)

# 查询这些元素自身并测量召回率：
labels, distances = p.knn_query(data, k=1)
print("两批次的召回率：", np.mean(labels.reshape(-1) == np.arange(len(data))), "\n")

C++ 示例

在此处查看示例：

• 创建索引、插入元素、搜索、序列化/反序列化
• 在搜索过程中使用布尔函数进行过滤
• 删除元素并将已删除元素的内存空间重新用于新插入的元素
• 多线程使用
• 多向量搜索
• ε 搜索

绑定库安装

您可以从源代码安装：

apt-get install -y python-setuptools python-pip
git clone https://github.com/nmslib/hnswlib.git
cd hnswlib
pip install .

或者您也可以通过 pip 安装： pip install hnswlib

针对开发者

我们非常欢迎贡献！

请针对 develop 分支提交拉取请求。

在进行更改时，请运行测试（如果有新功能，请在 tests/python 中添加测试）：

python -m unittest discover --start-directory tests/python --pattern "bindings_test*.py"

其他实现

• 非度量空间库（nmslib）——主库（Python、C++），支持多种特殊距离：https://github.com/nmslib/nmslib
• Facebook 的 Faiss 库，使用其自有的 HNSW 实现进行粗量化处理（Python、C++）： https://github.com/facebookresearch/faiss
• 论文“重访十亿级近似最近邻的倒排索引”中的代码 （目前压缩索引领域的最先进方法，C++）： https://github.com/dbaranchuk/ivf-hnsw
• Amazon PECOS https://github.com/amzn/pecos
• TOROS N2（Python、C++）：https://github.com/kakao/n2
• 在线 HNSW（C++）：https://github.com/andrusha97/online-hnsw)
• Go 实现：https://github.com/Bithack/go-hnsw
• Python 实现（作为 Matteo Dell'Amico 聚类代码的一部分）：https://github.com/matteodellamico/flexible-clustering
• Julia 实现 https://github.com/JuliaNeighbors/HNSW.jl
• Java 实现：https://github.com/jelmerk/hnswlib
• 使用 Java Native Access 的 Java 绑定：https://github.com/stepstone-tech/hnswlib-jna
• .Net 实现：https://github.com/curiosity-ai/hnsw-sharp
• CUDA 实现：https://github.com/js1010/cuhnsw
• Rust 实现 https://github.com/rust-cv/hnsw
• Rust 实现注重内存和线程安全，并提供一个 Trait 接口，允许用户实现自己的距离函数。该接口接受类型为 T 的切片，其中 T 需满足 Serialize+Clone+Send+Sync 的要求：https://github.com/jean-pierreBoth/hnswlib-rs

2 亿 SIFT 数据集复现

从根目录下载并解压 bigann 数据集：

python tests/cpp/download_bigann.py

编译步骤：

mkdir build
cd build
cmake ..
make all

运行 2 亿 SIFT 子集测试：

./main

BigANN 子集的大小（以百万为单位）由 sift_1b.cpp 文件中硬编码的变量 subset_size_millions 控制。

更新测试

从根目录生成测试数据：

cd tests/cpp
python update_gen_data.py

编译步骤（从根目录开始）：

mkdir build
cd build
cmake ..
make 

运行不包含更新的测试（从 build 目录）：

./test_updates

运行包含更新的测试（从 build 目录）：

./test_updates update

HNSW 示例演示

• 用于 100 万件亚马逊商品的视觉搜索引擎（MXNet + HNSW）：网站，代码，演示者：@ThomasDelteil

参考文献

HNSW 论文：

@article{malkov2018efficient,
  title={高效且鲁棒的近似最近邻搜索：基于分层可导航小世界图},
  author={Malkov, Yu A 和 Yashunin, Dmitry A},
  journal={IEEE 模式分析与机器智能汇刊},
  volume={42},
  number={4},
  pages={824--836},
  year={2018},
  publisher={IEEE}
}

本仓库支持的更新算法即将发表于“Apoorv Sharma、Abhishek Tayal 和 Yury Malkov 提交的 US Patent 15/929,802：HNSW 的动态更新，分层可导航小世界图”。

hnswlib 快速上手指南

hnswlib 是一个轻量级、仅头文件的 C++ HNSW（分层可导航小世界）算法实现，提供 Python 绑定。它支持增量索引构建、元素更新与删除，具有内存占用小、构建速度快、查询效率高等特点，适用于大规模向量近似最近邻搜索。

环境准备

• 操作系统：Linux / macOS / Windows
• Python 版本：Python 3.6+
• 依赖库：
  • numpy
  • C++11 兼容编译器（如 g++、clang++ 或 MSVC）
• 可选依赖：无额外第三方库依赖（header-only C++ 实现）

💡 提示：国内用户可使用清华或阿里云镜像加速 pip 安装。

安装步骤

方式一：通过 pip 安装（推荐）

pip install hnswlib

使用国内镜像加速（推荐）：

pip install hnswlib -i https://pypi.tuna.tsinghua.edu.cn/simple

或

pip install hnswlib -i https://mirrors.aliyun.com/pypi/simple/

方式二：从源码安装（适用于开发或自定义编译）

git clone https://github.com/nmslib/hnswlib.git
cd hnswlib/python_bindings
python setup.py install

基本使用

以下是最简单的使用示例，涵盖索引创建、数据插入、近邻搜索和序列化。

import hnswlib
import numpy as np
import pickle

# 设置参数
dim = 128
num_elements = 10000

# 生成随机向量数据
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)

# 创建索引（支持空间：'l2', 'ip', 'cosine'）
p = hnswlib.Index(space='l2', dim=dim)

# 初始化索引
p.init_index(max_elements=num_elements, ef_construction=200, M=16)

# 插入数据
p.add_items(data, ids)

# 设置查询精度参数（ef 应大于 k）
p.set_ef(50)

# 执行 KNN 查询（查找每个向量的 1 个最近邻）
labels, distances = p.knn_query(data, k=1)

# 验证召回率（可选）
print("Recall:", np.mean(labels.reshape(-1) == ids))

# 序列化索引（支持 pickle）
with open("index.pkl", "wb") as f:
    pickle.dump(p, f)

# 反序列化
with open("index.pkl", "rb") as f:
    p_loaded = pickle.load(f)

# 继续查询
labels_new, distances_new = p_loaded.knn_query(data[:5], k=1)
print("Top-1 labels for first 5 queries:", labels_new)

关键参数说明

• space: 距离度量方式，可选 'l2'（欧氏距离平方）、'ip'（内积）、'cosine'（余弦距离）
• dim: 向量维度
• max_elements: 索引最大容量（可后续扩容）
• M: 图中每个节点的最大连接数，影响内存与精度
• ef_construction: 构建时的搜索宽度，越大越准但越慢
• ef: 查询时的搜索宽度，需手动设置且应 > k

⚠️ 注意：ef 参数不会自动保存，加载索引后需重新设置。

此指南适用于快速集成 hnswlib 到项目中。更多高级功能（如过滤、删除、多线程）请参考官方示例与文档。