Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速

这篇具有很好参考价值的文章主要介绍了Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者:Adrien Grand

Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速,Elasticsearch,Elastic,elasticsearch,大数据,搜索引擎,数据库,全文检索

Disjunctive queries(term_1 OR term_2 OR ... OR term_n)非常常用,因此在提高查询评估效率方面它们受到了广泛关注。 Apache Lucene 对于评估 disjunctive queries 有两个主要优化:一方面用于详尽评估的 BS1,另一方面用于计算热门命中的 MAXSCORE 和 WAND。 直到最近,这两种优化从未一起使用,但为了提高查询性能,特别是对于许多子句和/或高频子句,这种情况发生了变化。 请参阅下图中摘自 Lucene 夜间基准测试的注释 FK。

Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速,Elasticsearch,Elastic,elasticsearch,大数据,搜索引擎,数据库,全文检索

什么是 BS1?

在 Apache Lucene 中,查询负责创建匹配文档 ID 的排序流。 实现 disjunctive query 归结为采用 N 个输入查询,生成文档 ID 的排序流,并将它们组合成文档 ID 的合并排序流。 解决此问题的教科书方法包括将输入流放入按当前文档 ID 排序的最小堆数据结构中。 这种方法在 Lucene 中被称为 BooleanScorer2 (BS2)。

虽然 BS2 工作得很好,但每次需要移动到下一个匹配时都必须重新平衡堆,因此会产生一些开销。 BS1 试图通过将文档 ID 空间分割为包含 2,048 个文档的窗口来减少这种开销。 在每个窗口中,BS1 都会迭代所有匹配的文档 ID,一次一个子句。 对于每个文档 ID,它计算该文档 ID 在窗口中的索引,设置位集中的相应位,并将当前分数添加到 double[2048] 中的相应索引中。 迭代窗口内的匹配,然后包括迭代位集的位并在 double[2048] 中的相应索引处查找分数。 对于具有许多子句或高频子句的查询,此方法通常运行得更快。

Lucene 的创建者 Doug Cutting 在 1997 年发表的一篇名为 “总排名的空间优化” 的论文中描述了这两种方法。 BS2在本文中被称为 “并行合并” 并在4.1节中描述,而 BS1 被称为 “块合并(Block Merge)” 并在 4.2 节中描述。 这些可以说是比 BS1 和 BS2 更具描述性的名称。 请注意,论文中对 “块合并” 的描述与今天 Lucene 中的描述有很大不同,但底层思想是相同的。

什么是 MAXSCORE 和 WAND?

如果你只关心分数前 k 的匹配,你是否可以评估更少的命中? 答案是肯定的。 这就是 MAXSCORE 和 WAND 算法的目的。 虽然这些算法有所不同,但它们基于相同的想法 - 如果你可以获得每个子句可以产生的分数的良好上限,那么你可以使用此信息来跳过没有机会进入顶部的命中 - k 次点击。 有关此主题的更多信息,请参阅其他博客。

与详尽的评估相比,这些算法通常可以快几倍地返回 top-k 结果。 然而,也有一些情况不能很好地发挥作用。 一些例子包括:

  • 对许多个术语的 Disjunctive queries
  • 对具有次优分数上限的查询进行 Disjunctive queries(例如 (a AND b) OR (c AND d) 等连词的 disjunction)使用 MAXSCORE/WAND 不会看到与术语查询析取一样多的加速效果。
  • 古怪的权重,通常由学习稀疏检索模型使用,例如 Elastic Learned Sparse Encoder

当这些优化无法真正帮助跳过命中时,我们面临的挑战是我们仍在为其开销付费。 这是因为两种实现都需要在每次匹配时重新排序某些数据结构 - BS2 的情况就是因为最小堆的原因。 例如,我们有一些由 Elastic Learned Sparse Encoder 生成的查询,与 BS1 相比,使用 WAND 运行速度最多慢 5 倍。 这是由于缺少 BS1 优化、WAND 未能成功地实际跳过命中以及 WAND 由于数据结构重新排序而带来的额外每场比赛开销。

MAXSCORE 符合 BS1

直到最近,BS1 和 MAXSCORE/WAND 从未一起使用。 当不需要分数或需要详尽的评估时,将使用 BS1。 同时,当仅请求按降序排列的前 k 个命中时,将使用 MAXSCORE 或 WAND。

在研究上述有关 MAXSCORE 和 WAND 开销的挑战时,我们注意到 MAXSCORE 算法尤其可以轻松地从帮助 BS1 比 BS2 更快的相同优化中受益。 我们实现了这个想法,并通过 Lucene 的 BS1 的详尽评估和通过 MAXSCORE 和 WAND 的现有 top-k 优化对其进行了评估:

  • 从英文维基百科中提取的 10M 文档数据集。
  • 跨 2 到 24 个高频术语的 Disjunctions,其文档频率范围为 400K 到 4M 文档。
  • 查询在单个线程中运行,性能通过每秒可以运行的查询数来评估。 数字越高越好。

Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速,Elasticsearch,Elastic,elasticsearch,大数据,搜索引擎,数据库,全文检索

如上图所示,穷举评估只需要 8 个术语就可以比 top-k 优化运行得更快,因为后者无法跳过足够的命中来补偿其开销。 更糟糕的是,对于 24 个术语,尝试使用 top-k 优化会使查询运行速度比详尽评估慢 2.5 倍。

然而,结合 BS1 和 MAXSCORE 的析取查询的新评估逻辑始终优于这组查询的详尽评估和现有的 top-k 评估。

这一改进预计将在 Lucene 8.9 中发布,并在不久的将来在 Elasticsearch 中发布。 基本上,这意味着在对析取查询进行 top-k 搜索时,查询性能应该会更好,尤其是在以下情况下:

  • 有很多子句,
  • and/or 某些子句出现频率很高,
  • 和/或某些条款产生次优分数上限。

感谢您阅读此博客 - 我们希望您能享受查询加速带来的乐趣! 如果你想了解有关 top-k 查询处理优化的更多信息,请查看另一篇博客,我们在其中描述了如何在 Elasticsearch 7.0/Lucene 8.0 中引入这些优化。

原文:Bringing speedups to top-k queries with many and/or high-frequency terms | Elastic Blog文章来源地址https://www.toymoban.com/news/detail-709502.html

到了这里,关于Elasticsearch:为具有许多 and/or 高频术语的 top-k 查询带来加速的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】堆的应用——Top-K

    目录 前言: 一、Top-K问题描述: 二、不同解决思路实现: ①.排序法: ②.直接建堆法: ③.K堆法 总结:         上篇文章我们学习了二叉树的顺序存储结构,并且对于实际使用中所常用的顺序存储结构——堆的各个接口进行实现。这篇文章我们将对堆的实际应用进行更加

    2024年02月16日
    浏览(51)
  • 数据结构与算法:堆排序和TOP-K问题

    朋友们大家好,本节内容来到堆的应用:堆排序和topk问题 我们在c语言中已经见到过几种排序,冒泡排序,快速排序(qsort) 冒泡排序的时间复杂度为O(N 2 ),空间复杂度为O(1);qsort排序的时间复杂度为 O(nlogn),空间复杂度为O(logn),而今天所讲到的堆排序在时间与空间复杂度上相

    2024年03月08日
    浏览(58)
  • 什么是堆,如何实现?(附堆排序,TOP-K问题)

    欢迎来到 Claffic 的博客   💞💞💞 “春风里,是谁 花一样烂漫?” 前言: 二叉树给大家讲解的差不多了,接下来就是二叉树的实际应用了:这期我们来讲堆,它是一种顺序结构的特殊二叉树,可以实现排序等功能,那就让我们开始吧! 目录 🌸Part1: 何为堆 1.堆的概念 2.堆

    2023年04月11日
    浏览(34)
  • 二叉树的顺序结构及实现(堆、Top-k)

    1 二叉树的顺序结构 2 堆的概念及结构 3 堆的实现 4 堆的应用 1 二叉树的顺序结构        普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要

    2024年02月11日
    浏览(33)
  • Java中Elasticsearch使用类似MySQL的OR和AND查询

    本文用实例来介绍如何使用Spring Data Elasticsearch的ElasticsearchRestTemplate来操作ES,在Java中Elasticsearch使用类似MySQL的OR和AND进行多条件查询。 官网 Elasticsearch Operations 一种复合查询,把其余类型的查询包裹进来,支持以下三种逻辑关系。 ES查询实例如下: 在Java中代码示例: 该m

    2024年02月02日
    浏览(34)
  • 【JavaDS】优先级队列(PriorityQueue),堆,Top-k问题

    ✨ 博客主页: 心荣~ ✨ 系列专栏: 【Java实现数据结构】 ✨ 一句短话: 难在坚持,贵在坚持,成在坚持! 如果有一个 关键码的集合K = {k0,k1, k2,…,kn-1} ,把它的所有元素 按完全二叉树的顺序存储方式存储 在一 个一维数组中 ,并满足: Ki = K2i+1 且 Ki= K2i+2 (Ki = K2i+1 且 Ki = K2i

    2024年02月01日
    浏览(44)
  • 【数据结构】堆的实现,堆排序以及TOP-K问题

    目录 1.堆的概念及结构 2.堆的实现 2.1初始化堆 2.2销毁堆 2.3取堆顶元素 2.4返回堆的大小 2.5判断是否为空 2.6打印堆 2.7插入元素 2.8堆的向上调整 2.9弹出元素 2.10堆的向下调整 3. 建堆时间复杂度 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 堆是一种数据结构,它是由一组元素组成的,并

    2024年02月12日
    浏览(50)
  • 堆(两种建堆方法)、堆排序和Top-K问题

    是一种完全二叉树,分为大堆,小堆 如果有一个关键码的集合 int K[ ] = {27,15,19,18,28,34,65,49,25,37} ; 把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:K i =K 2*i+1 且K i =K 2*i+2 ( K i =K 2*i+1 且K i =K 2*i+2 ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大

    2023年04月09日
    浏览(31)
  • LLM探索:GPT类模型的几个常用参数 Top-k, Top-p, Temperature

    上一篇文章介绍了几个开源LLM的环境搭建和本地部署,在使用ChatGPT接口或者自己本地部署的LLM大模型的时候,经常会遇到这几个参数,本文简单介绍一下~ temperature top_p top_k 上一篇也有介绍过,这次看到一个不错的图 A recent breakthrough in artificial intelligence (AI) is the introduction

    2024年02月06日
    浏览(46)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包