大规模向量相似度检索方案

清疚 2022-12-29 09:45 203阅读 0赞

# 1. 引入 #

有很多指标可以用来衡量向量的相似度，比如余弦距离、汉明距离、欧氏距离等。

在图像、视频、文本、音频领域，做向量的相似性搜索，有很多应用点，比如：图像识别，语音识别、垃圾邮件过滤。

这种基于相似度检索的方案，不同于机器学习模型的方案。比如用有监督学习模型来做人脸识别，模型的可解释性较低，而基于相似度搜索来做人脸识别，可解释性就更高。

但是，当数据量很大，比如几千万张图片，要做相似度搜索，就比较困难了。穷举法固然可行，但非常耗时。针对这种场景，本文主要介绍方案级别的信息。

# 2. 常用方案 #

通用的向量相似度检索方法，主要是如下几种

1.  穷举搜索

该方案是O(n)的时间复杂度，只适用于数据量较少的情况。

1.  基于MySQL的搜索

通过巧妙构造数据库表结构来实现。比如将向量拆分为N段，根据鸽巢原理，相似度为M（M<N）的向量，一定有N-M段值是完全相同的，这就可以用SQL的多段OR在一起来查询。

1.  KD-Tree

构建一颗树，与BST非常类似，能用来做二分查找，时间复杂度为O(logN)

1.  ES

ElasticSearch在7.x版本之后，集成了向量搜索的功能。

1.  向量搜索引擎

Facebook等公司开发了专门针对向量做相似度搜索的引擎，有的还可以支持GPU，分布式部署。

# 3. 向量检索算法 #

目前大部分向量搜索引擎用的都是hnsw算法，Google在2019年8月提出了一个新的算法，叫ScaNN (Scalable Nearest Neighbors) ，从他们的测试数据（https://github.com/google-research/google-research/tree/master/scann）中可以看出，ScaNN可以吊打其他所有算法。从这个链接中也能看到几乎所有的向量检索算法。

# 4. 向量检索引擎 #

向量相似度搜索引擎内部集成了多种算法，多种索引，能根据不同类型的数据和不同类似的搜索要求来动态选择搜索策略，做到更好的搜索效率，是一个比较好的选择。目前常见的向量搜索引擎如下

1.  faiss

*  开发者：Facebook
 *  是否开源：开源
 *  链接：https://github.com/facebookresearch/faiss
 *  优点：
    
     *  比较成熟，相关资料多，github上星很高
     *  支持CPU和GPU加速

1.  milvus

*  开发者：Zilla（国产软件，上海公司）
 *  是否开源：开源
 *  链接：https://github.com/milvus-io/milvus
 *  优点：
    
     *  资料多，已经加入linux基金项目，技术社区维护的比较好，也有自己的博客更新及时
     *  支持GPU加速
     *  国内阿里、小米等很多大公司都在使用

1.  SPTAG

*  开发者：Microsoft
 *  是否开源：开源
 *  链接：https://github.com/microsoft/SPTAG
 *  优点：对比下来其他引擎，发现SPTAG有没优势

1.  annoy

*  一个库，不支持GPU之类的加速和其他复杂应用

1.  Zsearch

*  开发者：蚂蚁金服
 *  是否开源：不开源
 *  介绍链接：https://segmentfault.com/a/1190000021334725

1.  vearch

*  开发者：京东
 *  是否开源：开源
 *  链接：https://www.infoq.cn/article/gxYOJ0m5rpMpIEwvz9GR
 *  优点：在 faiss 的基础上研发了 vearch，提供了类似 ES的灵活易用的API

1.  ESKNN

*  开发者：AMAZON
 *  是否开源：开源
 *  链接：https://github.com/opendistro-for-elasticsearch/k-NN
 *  优点：AMAZON直接在ES基础上的修改，有看到说使用起来比较耗内存的说法

# 5. 性能数据 #

本文查找了上面提到的一些向量搜索引擎的性能数据，总结如下表：

<table> 
 <thead> 
  <tr> 
   <th>Engine</th> 
   <th>Performance</th> 
   <th>Data Size</th> 
   <th>Vector Size</th> 
   <th>Link</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ES</td> 
   <td>0.6s</td> 
   <td>1,000,000</td> 
   <td>128</td> 
   <td>https://github.com/jobergum/dense-vector-ranking-performance</td> 
  </tr> 
  <tr> 
   <td>ES-aliyun</td> 
   <td>0.09s</td> 
   <td>20,000,000</td> 
   <td>128</td> 
   <td>https://developer.aliyun.com/article/738155</td> 
  </tr> 
  <tr> 
   <td>milvus</td> 
   <td>27ms</td> 
   <td>1,000,000,000</td> 
   <td>128</td> 
   <td>https://github.com/milvus-io/milvus/blob/master/docs/test_report/milvus_ivfsq8_test_report_detailed_version.md</td> 
  </tr> 
  <tr> 
   <td>SPTAG</td> 
   <td>not good</td> 
   <td>N/A</td> 
   <td>N/A</td> 
   <td>https://github.com/microsoft/SPTAG/issues/80</td> 
  </tr> 
  <tr> 
   <td>https://github.com/microsoft/SPTAG/issues/76</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

可以看到，对比下来，发现milvus性能很不错。

# 6. milvus介绍 #

1.  如何安装（用docker，很方便就能配置起来）

*  https://milvus.io/cn/docs/install\_milvus.md

1.  python SDK及其用法（经实测，效率确实不错）

*  https://github.com/milvus-io/pymilvus

1.  图形界面（经实测，安装配置使用也方便）

*  https://milvus.io/cn/gui/