标题：可索引的距离估算编码用于近似最近邻搜索
编者的总结
- 基本思路是通过LSH大幅降维，然后建多维索引树。
- 搜索时先在索引树上找精确tNN，然后在其中计算真实距离。
- 可以做内存型（kd-tree），也可以做磁盘型(R-tree)。
- 查询效率和精度，和基于图的，基于乘积量化的仍然不在一个量级上；但构建时间也领先二者1-2个量级，索引大小也远远小于图的，但不如乘积量化的。
编者的思考
- 索引大小、构建时长，在SRS的基础上做了进一步的提升。
- 查询时间更长了，尤其在小数据集上(disk-resident)，在索引树上的精确tNN显然拖慢了效率，这也是为了弥补哈希函数精度不够的缺陷。
- 总体来说应该和SRS是一个alternative，因为查询时间的原因，不能作为完美的提升。尤其是要想获得更高的精度，IO次数要增加很多。
- 在高维向量空间和欧氏距离上的实验效果不知怎么样。
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
