2021NIPS-(微软bing高维搜索引擎)SPANN: Hi
标题：SPANN：高效的十亿级别近似相似性搜索
编者的总结
- 整体结构就是K-means tree（有基于图的查询优化），平衡K-means的手段就是分层迭代，每一层的扇出（K）设置的小一点。
- 另一个贡献是把边缘点重复放置分区，并基于RNG剪枝掉距离太近的分区不做放置。
编者的思考
- 聚类中心太多了，接近20%的数据点，仍然会对内存负载过高。
- 分布式的设计仍有待考量。
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
