标题：SPANN：高效的十亿级别近似相似性搜索

编者的总结

1. 整体结构就是K-means tree（有基于图的查询优化），平衡K-means的手段就是分层迭代，每一层的扇出（K）设置的小一点。
2. 另一个贡献是把边缘点重复放置分区，并基于RNG剪枝掉距离太近的分区不做放置。

编者的思考

1. 聚类中心太多了，接近20%的数据点，仍然会对内存负载过高。
2. 分布式的设计仍有待考量。

Abstract

目前的内存ANNS算法虽然召回极高，但是资源消耗过于昂贵。
本文提的SPANN算法，是内存-磁盘混合型索引系统，使用少量的内存和SSD，基于反转索引的思想。

1 Introduction

在本文之前，混合型索引系统中的STOA是DiskANN：https://www.jianshu.com/p/07ed2202f107。
其余图算法均是纯内存的。

2 Background and Related Work

对于ANNS问题，扩展性到达十亿级别的分两类：

• 乘积量化+翻转索引的：这类的问题在于乘积量化作为一种有损压缩，会导致在大数据集的情况下，精度下降严重。
  乘积量化：https://www.jianshu.com/p/533ac746748b
  优化乘积量化：https://www.jianshu.com/p/ecf37bbca6c1

• 基于近似图的算法：这类的问题在于内存消耗太严重，不消耗内存的，也需要用乘积量化来进行有损压缩。
  DiskANN：https://www.jianshu.com/p/07ed2202f107

3 SPANN

• 索引结构：翻转列表。将数据集分成N个列表，把每个列表的中心点放内存，具体列表内容放到磁盘存。
• 搜索：根据query找到距离最近的K个列表中心（内存操作），然后把对应的K个列表从磁盘上load上来，搜索之。

3.1 Challenges

• Posting length limitation：列表长度决定一次IO的代价，因此必须要有限制。然而实际上将数据集分区并保证平衡，是很困难的一件事。

• Boundary issue: 分区算法的固有弊病，即一旦query在两个分区边界，搜一个不搜另一个，会导致至少一半概率的召回丢失。

  
  image.png

• Diverse search difficulty：不同query有不同的搜索难度，如下图，为了找到1NN，需要搜索的列表数差距甚远。

  
  image.png

3.2 Key techniques to address the challenges

3.2.1 Posting length limitation

本文利用了下面这个式子：

image.png

式子分为两部分，第一部分描述分区的质量，即所有数据距离其对应中心点的距离和。第二部分描述均衡性，即各分区size的方差。

• 第一部分：X为数据集（每个向量长度为m），C为N个中心，即N×m，H为指示矩阵，|X|×N，指示每个数据属于哪个聚类中心。F范数为矩阵中所有值的平方和。
• 第二部分，括号外表示所有分区加和，括号内第一项表示第i个分区的size，第二项是分区平均size。
• 限制条件：每个数据点只能属于一个分区。

由于本文的N十分巨大，所以不能直接利用此式。
作者采用的方式是K-means tree，直到每个分区size达标，每一层的K都相对较小。

image.png
为了节省一些时间，作者把聚类中心换成离聚类中心最近的数据点。针对这些点，还可以把K-means tree换成RNG图来加速搜索。
https://github.com/microsoft/SPTAG

3.2.2 Posting list expansion

对于分区边界点，如果一个点和一个其他分区中心点的距离，和当前分区中心点的距离差不太多，那么就重复放置一次，如下图：

image.png

• 问题：每个分区列表其实size并不大，重复放置后，很可能多个分区之间内容差不多。
• 解决方案：引入RNG图的思想。假设点x位于某分区，分区聚类中心为c1，如果，那么我们就不会考虑在c2分区重复放置x。
  image.png
• 原因：两个相互靠近的分区是大概率在一次查询中同时搜索的，所以没有必要在很相邻的分区上做重复放置，而是应该向相对较远的位置做放置。

3.2.3 Query-aware dynamic pruning

query只搜索和最近聚类中心距离倍的聚类中心。

4 Experiment

4.2 SPANN on single machine

4.2.1 Comparison with state-of-the-art billion-scale disk-based ANNS algorithms

• 比复杂的基于图的DiskANN在低精度下（不算很低）要好一些。

  
  image.png

4.2.2 Comparison with state-of-the-art all-in-memory ANNS algorithms

• 延迟虽然高，但是算上内存消耗（VQ指标）就要比STOA要好一些。

  
  image.png

4.2.3 Ablation studies

• 首先是聚类中心数量选取，这个量是比较大的，要16%的数据量。

  
  image.png

• 重复放置边缘点的次数对这个影响也颇大，到放置4次左右收敛。

  
  image.png

• 查询动态切割和预想的一样影响不大。

  
  image.png