OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天读一篇 Paper, 领域不限.

这是 OPED 挑战的第三篇, 论文为 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph

这篇论文是有一点 Hardcore 的, 涉及到了很多数学证明, 我感觉自己也是力有不逮, 这里就大概讲一下论文的几个核心思想.

之所以读这篇论文, 是之前实现了类似的 ANN 的系统, 用的是 Product-Quantization 类型的算法, 想看看其他类型的算法大概是什么样的.

基于图的算法搜索思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/** 
 * 在图中搜索和 {@param query} 最相近的 {@param k} 个节点.
 * {@param graph}: 需要搜索的图
 * {@param startPoint}: 一个起点, 这个起点是任意的, 但一般会通过某中方法精挑细选一下.
 * {@param query}: 需要搜索的点.
 * {@param l}: 一个算法参数, 越大越准, 但是更久
 */
public List<Node> search(Graph graph, Node startPoint, Node query, int l, int k) {
    var candidates = new ArrayList<Node>();
    var visited = new HashSet<Node>();
    candidates.add(startPoint);
    var i = 0;
    while (i < l) {
        var firstUnvisitedNode = candidates.stream().filter(c -> !visited.contains(c))
            .findFirst()
            .orElse(null);
        if (firstUnvisitedNode == null) {
            break;
        }
        i = candidates.indexOf(firstUnvisitedNode);
        visited.add(firstUnvisitedNode);
        for (Node n : firstUnvisitedNode.neighbors()) {
            candidates.add(n);
        }
        candidates.sort(byDistanceTo(query));
        candidates = candidates.subList(0, l);
    }
    return candidates.subList(0, k);
}

上面的伪代码描述了搜索的算法. 这个算法的思路很简单, 它的复杂度和搜索链路的长度有关, 和每个节点的出度也有关, 如果我们能在不影响结果的情况下, 简化这个图, 就能提高性能. 因此论文的核心思想主要就是以下四点:

  1. 保证图的连通性.
  2. 减少节点的平均出度.
  3. 减少搜索路径长度.
  4. 减少图的大小和生成图的开销.

Monotic Search Network

在这篇论文之前, 有人提出了 Monotic Search Network(MSNET) 的概念, 即给定任何一对节点 p 和 q, 都至少有一条从 p 到 q 的路径, 使得路径上每前进一个点, 到 q 的距离都单调递减. 这样一条路径叫做 Monotonic Path.
一个全联通图显然是一个 MSNET, 但是这个图的出度是 N, 搜索复杂度过于爆炸. 所以有很多论文提出了很多生成更小 MSNET 的算法. 但是这些算法的复杂度都很高, 这篇论文提出了一种新方法, 以及一种更快的生成近似 MSNET 的方法. 算法本身比较简单, 但是证明比较复杂, 这里就不细说了, 感兴趣的可以读一下原文 (链接在最上面).

和我之前采用的 Product Quantization 方法的比较

我个人感觉 Product Quantization 的方法更容易理解. 但是如这篇论文所说，使用 PQ 或者其他基于 LSH, Tree 的算法, 本质上都是剪枝的过程. 而这些算法为了减少内存消耗, 丢失了实际的距离的信息, 在搜索过程中需要搜索的点还是和 N 成正比的. 而这篇基于图的算法可以做到 O(log n) 级别.