SONG: Approximate Nearest Neighbor Search on GPU

# 原 ANNS 搜索过程

维护三个数据结构 q: 候选集 topk: 结果集 visited: 已访问节点

# SONG 系统

将上述算法全部迁移到了 GPU 中来运行。如图所示为 SONG 系统的处理流程梗概。在每轮迭代中，首先将用于拓展的结点（即需要计算距离的结点）从 GPU 的 Global memory 中存储的图数据中复制到共享内存中（Candidate Locating），随后，多个 GPU 中的 warp（32 个线程）并行地计算这些结点到查询点的距离（Bulk Distance Computation），并将计算得到的结果存到共享内存中。最后，一个 warp 中的其中一个线程使用计算得到的距离数值修改算法中提到的 q，topk，visited 三个数据结构。

# 优化

# 固定点的度数

更好寻址

# [[Bloom filter]]

访问列表不必精确回答 —— 假阳性是可以容忍的（ 已访问告知我们某个元素已被访问，但实际上并没有 ）

# 有界优先队列

只需维护优先队列前 K 个，实现了对称最小 - 最大堆的 GPU 版本

# 选择性插入优化

减少哈希表和布隆过滤器的插入以减少内存消耗 在插入之前进行选择：过滤掉所有与前 K 个元素的距离较大的顶点 —— 只有当一个顶点位于当前与查询点距离最近的前 K 个顶点中时，它才会被标记为已访问并推入 q 中

# 访问删除优化

当一个顶点从优先队列 q 中提取并处理后，如果该顶点没有更新 topk，我们可以将其从访问过的列表中删除。同样，当 topk 被更新时，弹出的顶点也可以从访问过的哈希表中删除。 当应用访问删除优化时，哈希表访问过的顶点恰好是 q（大小最多为 K）和 topk（大小最多为 K）的并集。因此，访问过的顶点的大小被限制在 2K 之内。

# 距离计算

每个线程负责计算一个维度子集的部分距离。 32 个线程被组织在一起以访问连续的内存地址。如果我们并发处理候选者，则每个线程的内访问模式是独立的 —— 将产生更多的缓存 miss。

# 超出 GPU 内存数据集的问题

# 使用随机哈希技术

为此，采用了随机哈希技术，将高维数据编码为位向量。这样，哈希后的数据集可以适应 GPU 内存，并在低维位上计算距离。

# 1-bit 随机投影

在众多概率哈希方法中，本文重点介绍了一种名为 “1-bit 随机投影” 的方法。这种方法通过生成一个随机向量 r ，并计算数据向量 u 和 v 在 r 上的投影符号来进行哈希。公式如下：

$$Pr⁡(sgn(u⋅r)=sgn(v⋅r))= 1 - \frac{\theta(u,v)}{\pi}$$

其中，θ(u,v) 是向量 u 和 v 之间的角度。如果 r 的条目从独立同分布的柯西分布中采样，而不是正态分布，则这种碰撞概率与 χ2 相似度密切相关。

# 哈希后的数据处理

对于每个数据点，映射到一个 h 位向量中。位向量之间的汉明距离是原始数据中相似性的良好估计。在实现中， h 可以设置为 32 的倍数，以便将位向量存储为几个 32 位无符号整数。这样，一个 h 位向量的内存占用等同于 h/32 个单精度浮点值的空间。