faiss索引调研(一)—— 基础知识

零、Delaunay 三角网

【定义】三角剖分:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G,该平面图满足条件:
1.除了端点,平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面,且所有三角面的合集是散点集V的凸包。
在实际中运用的最多的三角剖分是Delaunay三角剖分,它是一种特殊的三角剖分。先从Delaunay边说起:
【定义】Delaunay边:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。
【定义】Delaunay三角剖分:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。
【定义】假设T为V的任一三角剖分,则T是V的一个Delaunay三角剖分,当前仅当T中的每个三角形的外接圆的内部不包含V中任何的点。

v2-f8eec2fb8584dfcba30e3e40d4be9b6e_hd

一、Voronoi cell

http://www.csie.ntnu.edu.tw/~u91029/Neighbor.html
https://www.ryanligod.com/2018/10/09/2018-10-09 维诺图(Voronoi Diagram)分析与实现/

一个平面上散步着一些点,平面上的每一处都各自归属于其最近的点,属于不同点的面的交界处就形成了分界线,是左右两个不同类点的中垂线。简单来说就是,临近的点的中垂线形成了Voronoi图。

生成Voronoi的方法之一Delaunay 三角剖分算法:生成 Voronoi 图时先生成其对偶元 Delaunay 三角网,再找出三角网每一三角形的外接圆圆心,最后连接相邻三角形的外接圆圆心,形成以每一三角形顶点为生成元的多边形网。如下图:

二、PQ

https://blog.csdn.net/guanyonglai/article/details/78468673
https://blog.csdn.net/CHIERYU/article/details/50321473

Product Quantizer乘积量化,用于减小向量存储所需内存的一种方法。简单来说就是把每个索引向量切割成m个子向量,每个子向量自己用k-means聚类形成m个码本。对于检索库中的向量,把每个向量用这m个子向量的索引号来表示。

举个例子,比如说库里面有100万个128维向量,把这128维向量分为8个子向量,那么每个子向量就是128/8=16维子向量。之后在每个子向量形成的子向量空间中用k-meas聚类为256个类。然后把每个原始128维的向量的每个子向量在其对应的子向量空间中查找到自己属于哪个类,8个子向量分别在8个堆中查找属于256个类中的哪一个类,这样这个向量库就可以用256的八次方大小的矩阵来表示。然后在查找的时候,首先查看当前向量的1/8短向量,搜索到最近邻之后就可以排除掉向量库里面的其他255/256个向量,依此类推。

1138886-20170713165102025-150593021
(这里256 centroids 表示把这100万张图片的100万个特征向量的八分之一短向量聚为256类)
https://blog.csdn.net/guanyonglai/article/details/78468673
20151215224723962

算法主要通过以下几个步骤:

  1. 空间切分:将D维空间切分为M份(在上面的例子上M=8);
  2. 量化:计算每个短向量距离最近的聚类中心;
  3. 压缩:把原始向量生成为M维压缩向量;
  4. 距离计算:如何计算两个压缩向量的距离: 1.
  5. 左为对称计算:直接使用两个压缩向量x,y的索引值所对应的码字q(x),q(y)之间的距离代替。这个距离可以离线计算。
  6. 右为非对称计算:使用x,q(y)之间的距离代替x,y之间的距离,其中x是测试向量。虽然y的个数可能有上百万个,但是q(y)的个数只有k个,对于每个x,我们只需要在输入x之后先计算一遍x和k个q(y)的距离

总结:PQ其实可以类比于欧式空间中的笛卡尔积(假设集合A={a, b},集合B={0, 1, 2},则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。)。

20151215231350850

三、几种距离

编辑距离:给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数,操作只允许如下 3 种:

  1. 插入一个字符,例如:fj -> fxj<
  2. 删除一个字符,例如:fxj -> fj
  3. 替换一个字符,例如:fxj -> fyj

Jaccard距离:

四、LSH

局部敏感哈希的基本思想类似于一种空间域转换思想,LSH算法基于一个假设,如果两个文本在原有的数据空间是相似的,那么分别经过哈希函数转换以后的它们也具有很高的相似度;相反,如果它们本身是不相似的,那么经过转换后它们应仍不具有相似性。

五、HNSW(Hierarchical Navigable Small World)

https://www.ryanligod.com/2018/11/27/2018-11-27 HNSW 介绍/

  1. 对数据库向量进行Delaunay 三角剖分
  2. 搜索时:
    • 该算法贪婪地遍历来自上层的元素,直到达到局部最小值。
    • 贪婪算法:算法计算从查询到当前顶点的朋友列表的每个顶点的距离,然后选择具有最小距离的顶点。
  3. 如果查询与所选顶点之间的距离小于查询与当前元素之间的距离,则算法移动到所选顶点,并且它变为新的当前顶点。
  4. 算法在达到局部最小值时停止:一个顶点,其朋友列表不包含比顶点本身更接近查询的顶点
  5. 之后,搜索切换到较低层(具有较短 link),从元素重新开始,该元素是前一层中的局部最小值,并且该过程重复。
  6. 通过采用层状结构,将边按特征半径进行分层,从而将 NSW 的计算复杂度由多重对数(Polylogarithmic)复杂度降到了对数(logarithmic)复杂度。

六、kd树

https://zhuanlan.zhihu.com/p/23966698

comments powered by Disqus