Show HN: 约 500 行代码实现的向量嵌入 HNSW 索引
文章介绍了一个用大约 500 行 C++ 代码实现的向量嵌入 HNSW 索引。HNSW 是一种分层图结构，用于快速最近邻搜索。该实现为单头文件，使用 Eigen 进行 SIMD 加速，速度较快。文章解释了 HNSW 的工作原理：从顶层开始搜索，逐层下降，最终找到最接近的 K 个节点。提供了代码示例，展示了如何构建索引和搜索最近邻。编译方法也已给出。
Navigation Menu
dicroce/hnsw
Heirarchical Navigable Small Worlds
License
BSD-2-Clause license 29 stars 1 fork
HNSW - Hierarchical Navigable Small Worlds
向量嵌入的最近邻搜索
- 单头文件，现代 C++。
- 大约 500 行代码。
- 速度快（使用 Eigen 对距离计算进行 SIMD 加速）。
什么是 HNSW？
// Level 2 * * * *
// Level 1 * * * * * * ** * *
// Level 0 * ** * * * * * ** * * * * ** ** ** ** * * * * * * *
HNSW 是一种图结构，由多层组成，顶部层较为稀疏，底部层较为密集。同一层内的节点与其他在同一层上接近的节点相连。当插入一个节点时，会随机选择一个层级，并将该节点插入到该层级以及该层级之下的所有层级，直到第 0 层。
当搜索到达时，它从顶层开始，并在该层级中搜索（沿着连接），直到找到顶层中最接近的节点。然后，搜索下降并继续搜索附近的节点。随着搜索的进行，代码会跟踪它所见过的 K 个最近的节点。最终，它要么找到该值，要么在第 0 层找到最接近的值，并返回所见过的 K 个最近的节点。
示例
#include "hnsw/hsnw.h"
int main(int argc, char* argv[])
{
// 为 128 维向量创建索引
dicroce::hnsw<float> index(128);
const size_t num_vectors = 10000;
std::vector<std::vector<float>> vectors(num_vectors) = generate_random_vv(num_vectors, 128);
// 构建索引
for (size_t i = 0; i < vectors.size(); ++i)
index.add_item(vectors[i]);
// 搜索最近邻
std::vector<float> query(128) = generate_random_v(128);
const size_t k = 10;
auto results = index.search(query, k);
for (const auto& result : results)
printf("ID: %lu, Distance: %f\n", result.first, result.second);
}
编译
mkdir build && pushd build && cmake .. && make && popd
关于
Heirarchical Navigable Small Worlds