基于annoy的随机投影森林构建与检索优化实战

1次阅读

共计 2144 个字符，预计需要花费 6 分钟才能阅读完成。

在处理大规模高维数据（如推荐系统、图像检索）时，传统的精确搜索方法（如暴力搜索 /brute-force search）需要计算查询向量与所有候选向量的距离，导致：

时间复杂度高 ：O(Nd) 复杂度（N 为数据量，d 为维度），百万级数据响应延迟可达秒级
内存压力大：需预加载全部向量到内存，10 亿条 512 维浮点向量约占 2TB 内存

近似最近邻搜索（Approximate Nearest Neighbors, ANN）通过牺牲少量精度换取效率提升，其中 annoy（Approximate Nearest Neighbors Oh Yeah）因其以下特性成为热门选择：

内存占用仅为原始数据的 1.5~3 倍
支持磁盘存储索引
单查询响应时间稳定在毫秒级

特性	annoy	FAISS	HNSW
构建速度	快（O(n log n)）	中等	慢（O(n log n)）
内存效率	极佳（树结构压缩）	中等（需量化）	较差（图结构）
查询精度	中等（依赖树数量）	高（IVF+PCA）	极高（层级图）
动态更新	支持（重建部分树）	部分支持	不支持

annoy 的突出优势：

适合内存敏感型场景（如边缘设备）
支持多进程共享只读索引
无需 GPU 加速即可获得良好性能

annoy 通过递归空间分割构建二叉树：

随机投影：为每个节点生成随机单位向量（projection vector）
节点分裂：将数据投影到该向量，按中位数分为两个子集
递归构建：对子集重复上述过程直到叶子节点包含 <= K 个点（默认 K =20）

关键数学操作：

split\_point = median(\{v \cdot p | v \in V\})

其中 v 为数据向量，p 为投影向量，·表示点积

单棵树检索可能遗漏近邻，annoy 通过构建多棵树（forest）提高稳定性：

每棵树使用不同的随机种子生成投影向量
查询时并行搜索所有树，合并结果后去重排序
经验表明，树数量在 10~100 时性价比最高

from annoy import AnnoyIndex
import numpy as np

# 初始化索引（512 维向量）t = AnnoyIndex(512, 'angular')  # 余弦相似度用 'angular'

# 添加向量（实际项目建议批量添加）for i in range(100000):
    v = np.random.rand(512).astype('float32')
    t.add_item(i, v)

# 构建 100 棵树，每棵树构建 2 次（n_jobs 并行）t.build(100, n_jobs=2)  # 典型树数量：10-500

# 持久化存储
t.save('vectors.ann')

# 加载索引（多进程可共享）u = AnnoyIndex(512, 'angular')
u.load('vectors.ann')  # 内存映射模式

# 单点查询（返回前 10 近邻）neighbors, distances = u.get_nns_by_item(0, 10, include_distances=True)

# 批量查询优化
import concurrent.futures

def batch_query(queries, k=10):
    with concurrent.futures.ThreadPoolExecutor() as executor:
        return list(executor.map(lambda q: u.get_nns_by_vector(q, k), queries))