Approximate Nearest Neighbors Oh Yeah (Annoy)

Annoy 是由 Spotify 开源的一种用于高效近似最近邻搜索的树结构索引算法，特别适用于中低维向量的大规模场景。其特点是快速构建、多线程查询和只读内存映射，常用于推荐系统中的相似项查找。

📌 原理简介

Annoy 的核心思想是构建多棵随机二叉树（称为 Annoy Trees）：

每棵树使用随机的两个向量，计算它们的差向量作为划分超平面；
所有数据点根据该超平面对称划分到左右子树；
重复递归直到叶子节点包含的数据点数小于设定阈值；
构建多棵独立的树以提升检索覆盖率和准确率。

Note

Annoy 每棵树的划分是随机的，通过增加树的数量（n_trees）可以提升查准率，但也会增加索引大小和构建时间。

✏️ 查询过程

Annoy 查询采用多树回溯策略：

给定查询向量，从每棵树的根节点向下查找；
收集候选点（通常使用最大访问节点数 search_k 控制）；
对候选点进行精确距离计算并返回最近邻。

🆚 Tradeoffs

Annoy 的两个核心参数决定了检索的效果与性能权衡：

n_trees（构建时设定）
表示构建索引时生成的树的数量，影响 构建时间 和 索引大小。树越多，覆盖空间越全面，命中率更高，但占用内存和磁盘也更大。
search_k（查询时设定）
表示在所有树中最多遍历的节点数。数值越大，查准率更高，但 查询速度越慢。可以视作“近似程度”的控制参数。

Tip

如果未显式设置 search_k，默认值为：

\[ \text{search_k} = n \times \text{n_trees} \]

其中 \( n \) 是返回的近似最近邻数量。在实际使用中，n_trees 和 search_k 是相互独立的：只要 search_k 固定，增大 n_trees 对查询时间几乎无影响，反之亦然。

🧠 prefault 参数（延迟加载优化）

Annoy 默认会在加载索引文件时，将整个 mmap 文件预读（prefault）进内存，以加快首次查询速度。但你可以关闭此功能：

t.load('index.ann', prefault=False)

关闭 prefault 会让索引页面按需加载，适用于：

可用内存较小；
查询量较少；
查询只涉及局部向量区域。

⚠️ 注意：关闭后首次查询延迟可能显著增加，但内存占用明显下降，适合大索引 + 低并发场景。

Note

实际调优建议如下：

内存资源充足时：尽可能设置较大的 n_trees，以提高召回率；
对延迟敏感时：设置合适的 search_k，在准确率和响应时间之间做权衡；
可接受前几次查询略慢时，可将 prefault=False，以降低加载时间和内存占用。

✅ 优点

支持大规模数据（百万级）；
内存映射支持只读加载（可部署到磁盘）；
构建快速，适合预计算场景；
支持多种距离度量（如 Angular、Euclidean、Manhattan、Hamming、Dot Product）；
Python 使用简单，支持多线程查询。

⚠️ 局限性

只支持离线构建，不适合频繁更新；
不保证最优结果（近似搜索）；
查询效率受 n_trees 和 search_k 影响较大，需调参平衡速度与准确性。

🧪 示例（使用 `annoy` 包）

from annoy import AnnoyIndex

f = 40  # 向量维度
t = AnnoyIndex(f, metric='angular')  # 也可以用 'euclidean', 'manhattan', 'dot'

# 添加向量（id 必须是 int）
for i in range(1000):
    vec = [random.gauss(0, 1) for _ in range(f)]
    t.add_item(i, vec)

t.build(n_trees=10)  # 构建索引
t.save('test.ann')

# 查询
t.load('test.ann')  # 可从磁盘加载
idx = t.get_nns_by_vector(vec, 10, search_k=100)
print("Top 10 相似向量 ID:", idx)