标题：可索引的距离估算编码用于近似最近邻搜索

编者的总结

1. 基本思路是通过LSH大幅降维，然后建多维索引树。
2. 搜索时先在索引树上找精确tNN，然后在其中计算真实距离。
3. 可以做内存型（kd-tree），也可以做磁盘型(R-tree)。
4. 查询效率和精度，和基于图的，基于乘积量化的仍然不在一个量级上；但构建时间也领先二者1-2个量级，索引大小也远远小于图的，但不如乘积量化的。

编者的思考

1. 索引大小、构建时长，在SRS的基础上做了进一步的提升。
2. 查询时间更长了，尤其在小数据集上(disk-resident)，在索引树上的精确tNN显然拖慢了效率，这也是为了弥补哈希函数精度不够的缺陷。
3. 总体来说应该和SRS是一个alternative，因为查询时间的原因，不能作为完美的提升。尤其是要想获得更高的精度，IO次数要增加很多。
4. 在高维向量空间和欧氏距离上的实验效果不知怎么样。

ABSTRACT

• iDEC(indexable distance estimating codes)：可索引的距离估算编码，用于提升LSH方法框架。

2. BACKGROUND

2.1 Problem Description

c-ANN：真实1NN距离的c倍之内的点。

2.2 LSH and Hard-Decision Decoding

简单回顾下，LSH是能让原本距离相近的点，在hash之后，碰撞的概率更高。
通常用一组哈希函数，将原始数据映射成一个向量，对应一个hash bucket。query也hash到对应bucket，从中取出数据进行具体计算。
作者称之为“硬决策”解码，因为只探测了一个bucket。

2.3 ToW-Based Error-Estimating Codes

通信领域有验错码和纠错码，一些纠错码可以用于做LSH的哈希函数。
对于二进制码，欧氏距离的平方和海明距离是一样的。一种称之为ToW（拔河）的验错码，就是二进制信息的欧氏距离的平方。

• 基于此定义哈希函数：其中R是一个向量，每个位置是1或-1，概率等同。

  • 这样的R做成一组，就是一个hash family。

    
    image.png
• 再进一步，改造一下hash函数：其中b是【0,w】的一个随机数，w是bucket宽度。

  • 就构成了LSH Family。

    
    image.png
• 这样的LSH Family质量不算很高，但作者没有对它做优化，因为在后面做的不是“硬决策”，因此可以有一定精度弥补。

4. IDEC FRAMEWORK

4.1 Dimensionality Reduction

LSH的一个基本框架就是首先将源数据映射到新的空间里面，这种映射必须具有Local-sensitive的特征，也可以称为近似保留的特征（统计意义上）。

4.2 Indexing

降维之后，数据集可以用各种多维索引，因为此时维数已经很低：

• 内存型：kd-tree, ball tree, vp-tree, cover tree
• 磁盘型：R-tree

4.3 Query Processing

搜索过程很简单，首先在hash过的空间上做精确tnn搜索，然后将这部分数据算真实距离，找到ANN。

• 因为并非是找对应的一个bucket，而是找一组备选，所以这种搜索策略称为“软决策”。

  
  image.png
• 查询复杂度分析：【暂时省略】

4.4 Why k-d Tree?

• 简单来说，就是搜索效率高。

  
  image.png

4.5 iDEC for External-Memory Operations

如果是大数据集，就用R-tree。

• 查询复杂度：【暂时省略】

5. IDEC FOR ANN-H

海明距离的ANN搜索。
只要确定了用哪个LSH family, iDEC就已经是具体的方法了。
在海明距离的情况中，就用之前提到的基于拔河验错码的LSH family。它将二进制数据，转换为高维向量（整数）和欧氏距离。

• 与SRS的比较：
  • 和IDEC一样，SRS的哈希函数也是和随机向量R做内积，但是SRS的随机向量是浮点数的，因此映射出来的向量也是浮点数的，最终影响到索引大小比iDEC要大一些。
  • 如果数据集也是浮点数向量，用欧氏距离做度量，那么IDEC和SRS的索引大小就是一致的了。

6. IDEC FOR ANN-E

讲iDEC框架用于编辑距离（字符串）的，设计了新的哈希函数。
【详情省略】

7. EVALUATION

7.3 Performance Evaluation for ANN-H

7.3.3 In-Memory Experimental Results

• 索引大小在LSH的方法里面是非常轻型的，胜过了SRS。

  
  image.png

• 构建速度相对也要快很多。

  
  image.png

• 查询质量和效率方面，肯定是不如图方法和乘积量化方法。

  
  image.png
  image.png

7.3.4 External-Memory Experimental Results

• 索引大小方面仍然占据优势。比QALSH和C2LSH更轻因为这两位动辄去建上百棵B+树，那在索引大小方面自然是没法比较了。比SRS更小来源于我们之前说的原因，整数和浮点数的Byte差异正好是两倍。

  
  image.png
• IOcost相对小很多，可以理解因为索引已经小了很多。

• 具体的查询时间，iDEC比SRS略长，比另两个要好很多，尤其是在数据集较大的时候，CPU计算也比另两个要快。

  
  image.png