Hann: A Fast Approximate Nearest Neighbor Search Library for Go
Hann：Go 语言的快速近似最近邻搜索库
habedi / hann Public generated from habedi/template-go-project
一个为 Go 语言设计的快速近似最近邻搜索库。
License
A fast approximate nearest neighbor search library for Go
Hann 是一个高性能的 Go 语言近似最近邻搜索 (ANN) 库。它提供了一系列索引数据结构，用于在高维空间中进行高效的相似性搜索。目前，支持的索引包括 Hierarchical Navigable Small World (HNSW)、Product Quantization Inverted File (PQIVF) 和 Random Projection Tree (RPT)。
Hann 可以看作是向量数据库（例如 Milvus、Pinecone、Weaviate、Qdrant 等）的核心组件。它可用于为您的 Go 应用程序添加快速的内存相似性搜索功能。
特性
- 不同索引的统一接口 (参见 core/index.go)
- 支持对任意维度的向量进行索引和搜索
- 使用 SIMD (AVX) 指令进行快速距离计算 (参见 core/simd_distance.c)
- 支持向量的批量插入、删除和更新
- 支持将索引保存到磁盘并重新加载
索引
| 索引名称 | 空间复杂度 | 构建复杂度 | 搜索复杂度 | |---|---|---|---| | HNSW | $O(nd + nM)$ | $O(n\log n)$ | $O(\log n)$ 平均情况, $O(n)$ 最坏情况 | | PQIVF | $O(nk + kd)$ | $O(nki)$ | $O(\frac{n}{k})$ | | RPT | $O(nd)$ | $O(n\log n)$ | $O(\log n)$ 平均情况, $O(n)$ 最坏情况 |
- $n$: 向量数量
- $d$: 维度数量（向量长度）
- $M$: 每个节点的链接数 (HNSW)
- $k$: 聚类数量 (PQIVF)
- $i$: 聚类迭代次数 (PQIVF)
支持的距离计算方式
HNSW 索引支持使用 Euclidean 距离、平方 Euclidean 距离、Manhattan 距离和余弦距离。如果使用余弦距离，则向量在读取时会被归一化（在索引中使用或搜索之前）。请注意，平方 Euclidean 距离的计算速度略快于 Euclidean 距离，并且给出与 Euclidean 距离相同的最近向量顺序。如果只需要查询向量的最近向量顺序，而不需要实际距离，则可以使用它来代替 Euclidean 距离。
PQIVF 和 RPT 索引仅支持 Euclidean 距离。
安装
可以使用以下命令将 Hann 作为典型的 Go module 安装：
go get github.com/habedi/hann@main
Hann 需要 Go 1.21 或更高版本，一个 C (或 C++) 编译器，以及一个支持 AVX 指令的 CPU。
示例
| 示例文件 | 描述 | |---|---| | simple_hnsw.go | 创建和使用带有 inline 数据的 HNSW 索引 | | hnsw.go | 创建和使用 HNSW 索引 | | hnsw_large.go | 创建和使用 HNSW 索引 (使用大型数据集) | | pqivf.go | 创建和使用 PQIVF 索引 | | pqivf_large.go | 创建和使用 PQIVF 索引 (使用大型数据集) | | rpt.go | 创建和使用 RPT 索引 | | rpt_large.go | 创建和使用 RPT 索引 (使用大型数据集) | | load_data.go | 用于加载示例数据集的 Helper 函数 | | utils.go | 示例的额外 Helper 函数 | | run_datasets.go | 用于创建不同索引并在不同数据集上尝试的代码 |
数据集
使用以下命令下载示例中使用的数据集：
make download-data
# 仅在运行使用大型数据集的示例时需要
make download-data-large
请注意，要运行使用大型数据集的示例，可能需要一台具有大量内存的机器，例如 32 GB 或更多。
查看 data 目录，了解有关数据集的信息。
文档
有关 Hann 包的详细文档，请访问 pkg.go.dev。
HNSW 索引
hnsw 包（hnsw）提供了由 Malkov 和 Yashunin (2016) 提出的 HNSW 图索引的实现。HNSW 将数据组织成临近图的多个层，从而可以通过从上到下贪婪地遍历图来实现快速的近似最近邻搜索。
该索引具有以下参数：
- M：控制每个节点的最大邻居连接数。较高的值可提高准确性，但会增加内存和索引时间（典型范围：5–48）。
- Ef：定义插入和搜索期间的搜索范围。较高的值可提高准确性，但会增加计算成本（典型范围：10–200）。
PQIVF 索引
pqivf 包（pqivf）提供了由 Jegou et al. (2011) 提出的 PQIVF 索引的实现。PQIVF 首先将数据聚类成粗略的组（倒排列表），然后使用 product quantization 压缩每个集群中的向量。这允许通过将查询限制到相关集群并有效比较压缩向量来快速进行近似最近邻搜索，从而减少搜索时间和存储需求。
该索引具有以下参数：
- coarseK：控制初始量化的粗略聚类数量。较高的值可提高搜索性能，但会增加索引时间（典型范围：50–4096）。
- numSubquantizers：确定 product quantization 的子空间数量。更多的子量化器可以提高压缩率和准确性，但会增加索引时间（典型范围：4–16）。
- pqK：设置每个子量化器的码字数量。较高的值会增加准确性和存储使用量（典型值：256）。
- kMeansIters：用于训练 product quantization 代码本的迭代次数（建议值：25）。
RPT 索引
rpt 包（rpt）提供了由 Dasgupta 和 Freund (2008) 提出的 RPT 索引的实现。RPT 使用随机生成的超平面递归地对数据进行分区以构建树结构，从而可以通过树遍历过程实现高效的近似最近邻搜索。
该索引具有以下参数：
- leafCapacity：控制每个叶节点中存储的最大向量数。较低的值会增加树的深度，从而提高搜索速度，但会略微增加索引时间（典型范围：5–50）。
- candidateProjections：在每个树分割处考虑的随机投影数。较高的值会提高分割质量，但会增加索引时间（典型范围：1–10）。
- parallelThreshold：触发并行构建的子树中的最小向量数。较高的值可以在索引期间实现更好的并发性，但会使用更多内存（典型值：100）。
- probeMargin：用于确定搜索期间探测的其他分支的边距。较高的值会提高召回率，但会因额外的距离计算而增加搜索开销（典型范围：0.1–0.5）。
日志
可以使用 HANN_LOG 环境变量控制 Hann 产生的日志的详细程度。可能的值包括：
0、false或off：完全禁用日志记录；full或all：启用完整日志记录（DEBUG级别）；- 使用任何其他值（包括不设置
HANN_LOG环境变量）：启用基本日志记录（INFO级别；默认行为）。
随机种子
为了在不同运行中获得更一致的索引和搜索结果，请将 HANN_SEED 环境变量设置为一个整数。这将初始化随机数生成器，但某些变化仍然可能发生（例如，由于多线程）。
贡献
有关如何做出贡献的详细信息，请参阅 CONTRIBUTING.md。
Logo
该 logo 名为 "Hiking Gopher"，由 Egon Elbre 创建。
License
Hann 在 MIT 许可证下发布 (LICENSE)。
关于
一个为 Go 语言设计的快速近似最近邻搜索库
主题
go golang nearest-neighbor-search approximate-nearest-neighbor-search search-algorithms similarity-search vector-search indexing-algorithms