相关文章推荐
飞奔的篮球  ·  林正英(武術指導、演員)照片,刊於《電影雙周 ...·  2 周前    · 
大鼻子的课本  ·  London College of ...·  3 周前    · 
重感情的热水瓶  ·  贾跃亭朋友圈“炮轰”高合汽车:“行业的耻辱”·  9 月前    · 
老实的回锅肉  ·  中山市农业农村局政务网站·  12 月前    · 
闷骚的紫菜  ·  奇迹暖暖温柔召唤暖暖王室成员是谁?奇迹暖暖小 ...·  1 年前    · 
小百科  ›  Elasticsearch:普通检索和向量检索的异同?开发者社区
检索 数据检索 云数据 聚类 elasticsearch
飞奔的蚂蚁
2 年前
作者头像
铭毅天下
0 篇文章

Elasticsearch:普通检索和向量检索的异同?

前往专栏
腾讯云
开发者社区
文档 意见反馈 控制台
首页
学习
活动
专区
工具
TVP
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP
返回腾讯云官网
社区首页 > 专栏 > 铭毅天下 > 正文

Elasticsearch:普通检索和向量检索的异同?

发布 于 2022-02-09 14:41:49
1.6K 0
举报

1、引言

《 Elasticsearch 向量搜索的工程化实战 》文章一经发出,收到很多留言。读者对向量检索和普通检索的区别充满了好奇,所以就有了今天的文章。

2、普通搜索 VS 向量搜索

向量搜索已经在黑暗中成长了有些年头了,但是随着近几年机器学习和深度学习的蓬勃发展,“特别是万物皆可 embedding“的观点越来越流行之后,向量搜索才逐渐从小众的技术走入人们的视野之中。相较于普通搜索(基于词元和倒排索引),向量搜索会成为一个革命者代替它(们)的位置,还是会与它互补,并有机的整合在一起呢?

2.1 overview

首先,我们先来了解一下这两种搜索方案的特点以及各自的优缺点

2.1.1 普通搜索

以广泛被使用的 Lucene 、 Elasticsearch 、 Solr ,以及最近出来的一些类似 MeiliSearch 、 Redisearch 等为代表,基于词元和倒排索引所构建的普通搜索,是建立在准确的搜索内容和检索语句上的,他们往往通过各种方式对文档进行分词( analyze ),通过诸如 BKD tree 等数据结构,将拆解出来的词元( token )进行倒排索引,在检索时也会对检索语句进行同样的分词处理,通过相同词元的匹配进行召回,再通过文本相关性的算法(如 TF/IDF 、 BM25 等)对结果进行打分排序,最终返回结果。

因此,他们大多具有以下的特点:

  1. 具有较高的索引速度
  2. 中等的索引大小
  3. 较高的查询速度(在 大数据 量的场景)
  4. 良好的缩放比例
  5. (对于精确匹配)具有完美的精度
  6. 精确且无损的词元和词组搜索
  7. 只能通过词元的精确匹配做召回
  8. 无法捕获语义与相似性
    1. ES 的 synonym 是类似在同一个位置把所有预先定义的同义词同时索引来实现的

2.1.2 向量搜索

如果你在搜索时不知道确切的 query 词元 ,或者你希望能对更广泛的同/近义词所指向的内容进行召回,可以考虑通过向量搜索来完成。目前市面上比较流行的向量搜索解决方案,无论是业界流行的 Faiss 、 ScANN 库,还是工业级的开源解决方案 Milvus 、 Jina ,或者 Elasticsearch 及其衍生品 Elastiknn 、 OpenDistro Elasticsearch KNN ,多少会通过 KNN ( K nearest neighbors )对向量进行预聚类的方式进行存取加速。(参考的benchmark)

所以,他们大多会具有以下一些特点:

  1. 较慢的索引速度
  2. 较大的索引大小
  3. 较慢的查询速度(在大数据量的场景)
  4. 有限的缩放比例
  5. (对于精确匹配)具有较低的精度
  6. 较差的词元和词组的搜索能力
  7. 通过向量(某些解决方案中可以包含一部分标量字段)进行召回
  8. 对近似语义的捕获程度较高,可以很好的处理同/近义词

2.1.3 小结

通过普通搜索或者向量搜索构建个简单的搜索引擎系统并不难,但是随着数据量的增长、并发请求的增加、数据使用场景的变化,搜索引擎系统需要更多的组件一同完成其功能,如搜索前的数据预处理,到搜索过程中的query理解、改写、自动补全,缓存,分数计算,地理位置信息计算,到返回结果前的结果排序和过滤,结果分页等。

2.2 数据结构与搜索算法

之所以普通搜索和向量搜索会存在上面那些特点和差异,是因为他们构建数据的索引的数据结构以及召回算分的算法有很大差异,我们分别来看他们。

2.2.1 普通搜索

2.2.1.1 倒排索引

倒排索引是一个类似 hashmap 的数据结构,它的 key 是每个词元,而 value 是一个包含这个词元的所有文档的 id 列表(也可能是 hashset 、链表等结构),这样的数据结构的好处在于对于一个词元,可以用接近 O(1) 的代价来找到包含它的文章。有时倒排索引中也会包含词元在文档中的位置信息,这是为了能在搜索时,在考虑了 query 中的词元信息之外,也把词元的顺序也一并考虑进去。

2.2.1.2 LSM树

LSM 树(Log-Structured Merge-Tree),或称为日志结构合并树,被广泛运用于以 hbase 为代表的类 数据库 存储中,它的特点在于牺牲部分读的性能换取强大的写入性能,因为它作为一种基于硬盘的数据结构,可以明显的减少硬盘磁盘臂的开销,并能在较长的时间内提供文件的高速插入和删除。一般的倒排索引会构建在内存中,但随着数据量增加,我们可能需要通过磁盘来帮忙保存一部分数据,这就用到了 LSM树 ,因为硬盘(无论 SSD 还是 HDD 都比 RAM 慢的好几个数量级),而 LSM树 可以在写数据的时候先把数据缓存在内存中,等积累一定量之后再通过归并排序的方式将数据追加到磁盘队尾,以提高写入速度。

2.2.1.3 带版本的数据提交

LSM树 只解决了数据插入的问题,搜索引擎中还会存在大量的更新操作,这就涉及到了随机读写了,我们知道随机读写会比顺序读写慢得多,特别是在 HDD 硬盘上的读写,这时就需要使用带版本的数据提交操作了。由上一节可知,数据写入时会先写内存中的缓冲区( ES 的 translog 等)再通过定时提交的方式追加到磁盘中,在更新操作时也是一样的,不同的是搜索引擎往往会在内存中保留数据的指针,每次的更新(删除)操作作用在硬盘上也是追加操作,不同的是会将数据版本 +1,同时将指针指向新的地址,在召回时访问数据只访问最新版本的数据,同时定时对磁盘中的数据进行 merge 操作,清理掉过期的旧版本的数据,从而释放磁盘空间。

2.2.1.4 升级和调优

存储:

  1. Size-tiered compaction
  2. Leveled compaction
  3. Sharded compaction

索引:

  1. zstd(Zstandard)压缩
  2. Elias-Fano 编码
  3. 停止词
  4. 词干
  5. ngram 索引

2.2.2 向量搜索

向量搜索就完全不一样了,由于他们索引的不是【词元 - 文档】的信息而是向量,所以他们会在索引构建的时候会尝试通过聚类而非倒排索引的方式构建。

市面上大部分的向量搜索引擎是靠 KNN 配合距离计算来进行存储的,差别可能会是距离计算公式以及存储结构的优化。常见的距离计算如:

  1. 欧式距离 [euclidian distance] https://en.wikipedia.org/wiki/Euclidean_distance
  2. 点积 [dot product] https://en.wikipedia.org/wiki/Dot_product
  3. cosine 相似度[cosine similarity] https://en.wikipedia.org/wiki/Dot_product

2.2.2.1 索引数据

向量搜索的数据索引不同于普通搜索的分词,他们会需要先通过各种 machine learning 、 deep learning 技术将文档、句子、词组等转化成向量存进搜索引擎,搜索引擎会根据配置使用距离计算模块对向量进行聚类保存。

常见的向量化(嵌入)的算法:

  1. [Word2Vec] https://en.wikipedia.org/wiki/Word2vec
  2. [GloVe] https://en.wikipedia.org/wiki/GloVe_(machine_learning)
  3. [fastText] https://en.wikipedia.org/wiki/FastText
  4. [BERT] https://github.com/google-research/bert
  5. Word level embeddings from BERT
  6. Sentence level embeddings from BERT

2.2.2.2 召回数据

向量搜索的召回和索引一样是基于向量距离的,从简单到复杂可以大致分为线性搜索、分级导航(Hierarchical Navigable Small Worlds (HNSW))、索引分块及聚类等

  1. 线性搜索
    1. 顾名思义,线性搜索就是将 query 向量和索引中所有的向量依次比较,再按距离排序
    2. ES 对 Dense Vector 字段的处理就是线性搜索
    3. 这是最简单也是最慢的方式,而且随着索引数据量的上升,召回时间也会随之大幅上升
  2. 分级导航
    1. 介绍 CN http://d0evi1.com/hnsw/
    2. 介绍 EN https://www.pinecone.io/learn/hnsw/
    3. 通过近似图遍历的方式找到更接近的向量进行距离计算
  3. 索引分块及聚类
    1. K中心聚类 [k-medoids clustering] https://en.wikipedia.org/wiki/K-medoids
    2. 围绕中心分区(Partitioning Around Medoids (PAM))
    3. Correlated-Sequential-Halving
    4. Voronoi iteration with Voronoi cells (Dirichlet tessellation)
    5. K中值聚类[k-medians clustering] https://en.wikipedia.org/wiki/K-medians_clustering
    6. Kmeans聚类 [k-means/k-centroids clustering] https://en.wikipedia.org/wiki/K-means_clustering
    7. [Locality Sensitive Hashing] https://en.wikipedia.org/wiki/Locality-sensitive_hashing
    8. [Support Vector machines] https://de.wikipedia.org/wiki/Support_Vector_Machine
    9. 是向量搜索中较为常用的方式,通过预先配置的参数对向量进行 KNN 聚类的方式进行索引
    10. 召回时会通过寻找较近的核向量的方式来找到 topK 的向量进行
    11. 主要包含的一些方式:

2.2.2.3 升级和调优

其他一些可用的开源库

  1. [NGT] https://github.com/yahoojapan/NGT
  2. [ANNOY] https://github.com/spotify/annoy
  3. [RNSG] https://arxiv.org/abs/1707.00143
  4. [ScaNN] https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html
  5. 更多
    1. [ann-benchmarks] https://github.com/erikbern/ann-benchmarks
    2. [awesome-vector-search] https://github.com/currentsapi/awesome-vector-search

索引优化:

  1. 用zstd对文档进行压缩
  2. 向量优化(vector quantization (VQ))
  3. 主成分分析([Principal component analysis (PCA)]https://en.wikipedia.org/wiki/Principal_component_analysis
    1. 主要用于降维,把向量维度减少,通过损失部分精度来获取更小储存体积
  4. 乘积量化(Product Quantization (PQ))
    1. 用于压缩和储存大维向量
  5. Optimized Product Quantization (OPQ)
  6. CPU 和/或 GPU 的硬件加速

针对性能和准确性的权衡:

  1. 在相同的搜索场景中,准确性往往意味着更高维更高精度的向量,但是这些向量的计算(无论是线性还是聚类)中,单个向量间的计算成本会随之上升,使得整个召回过程性能下降
  2. 同时可以通过 nlist 、 nprobe 以及其他聚类、距离计算公式的调整来调整精度和性能

作者介绍

死敌wen,Elastic 认证工程师,搜索架构师,10年+工作经验,毕业于复旦大学。

博客:https://blog.csdn.net/weixin_40601534

Github:https://github.com/godlockin

点击展开阅读全文
文章分享自微信公众号:
铭毅天下Elasticsearch
铭毅天下Elasticsearch

扫码关注公众号

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

原始发表:2022-01-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

https
网络安全
github
git
开源
登录 后参与评论
关于作者
0
文章
0
累计阅读量
0
获赞
前往专栏
关注 - 腾讯云 开发者 公众号
将获得
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
扫码关注腾讯云开发者
NEW
切换旧版
领券
  • 社区

    • 专栏文章
    • 阅读清单
    • 互动问答
    • 技术沙龙
    • 技术视频
    • 团队主页
    • 腾讯云TI平台
  • 活动

    • 自媒体分享计划
    • 邀请作者入驻
    • 自荐上首页
    • 技术竞赛
  • 资源

    • 技术周刊
    • 社区标签
    • 开发者手册
    • 开发者实验室
  • 关于

    • 社区规范
    • 免责声明
    • 联系我们
    • 友情链接

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

  • 域名注册
  • 云服务器
  • 区块链服务
  • 消息队列
  • 网络加速
  • 云数据库
  • 域名解析
  • 云存储
  • 视频直播

热门推荐

  • 人脸识别
  • 腾讯会议
  • 企业云
  • CDN加速
  • 视频通话
  • 图像分析
  • MySQL 数据库
  • SSL 证书
  • 语音识别

更多推荐

  • 数据安全
  • 负载均衡
  • 短信
  • 文字识别
  • 云点播
  • 商标注册
  • 小程序开发
  • 网站监控
  • 数据迁移

Copyright © 2013 - 2023 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

深圳市腾讯计算机系统有限公司 ICP备案/许可证号: 粤B2-20090059 深公网安备号 44030502008569

腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

问题归档 专栏文章 快讯文章归档 关键词归档 开发者手册归档 开发者手册 Section 归档
 
推荐文章
飞奔的篮球  ·  林正英(武術指導、演員)照片,刊於《電影雙周刊》 (1982 ...
2 周前
大鼻子的课本  ·  London College of Contemporary Music | LCCM
3 周前
重感情的热水瓶  ·  贾跃亭朋友圈“炮轰”高合汽车:“行业的耻辱”
9 月前
老实的回锅肉  ·  中山市农业农村局政务网站
12 月前
闷骚的紫菜  ·  奇迹暖暖温柔召唤暖暖王室成员是谁?奇迹暖暖小区茶话会答案分享_ ...
1 年前
Link管理   ·   Sov5搜索   ·   小百科
小百科 - 百科知识指南