行业报告 AI展会 数据标注 标注供求
数据标注数据集
主页 > 机器学习 > 正文

Lucene 6 数值索引以及空间索引方案

 

要解决的问题

  • 范围查询

在一个二维平面上,有很多点,给定一个矩形,怎么快速的将落在矩形中的点找出来?
这个问题还可以推广到任意维度,一维就是区间查询,三维就是在长方体内部。

  • 近邻查询

离我最近的餐馆有哪些?
这个问题可以抽象成二维空间中,要找出距离某个点最近的点的集合。

一维的场景

这个场景非常简单,只需要将数值类型数据做个全排序,不管是范围查询还是近邻查询只需要进行二分搜索就好了。

如果数据集特别大,内存中放不下,上面的方案就会有问题,因为所有数据没有办法全部 load 到内存中。

这个时候可以在内存中维护一份索引,索引的构建过程如下:

step 1: 对数据进行外排序。
step 2: 构建二叉搜索树,选取step 1中数据中位数作为根节点的值,并在在根节点中记录下中位数的位置。
step 3:递归构造根节点左子树和右子树,左子树的根节点依据step 2中中位数左侧的数据集构造,
右子树依据step 2中中位数右侧的数据集构造。
step 4: 持续上述递归构造过程直到节点关联的数据数集数量小于某个阈值。

上述索引构造完成之后,查询过程中首先将索引 load 到内存中,先在索引中查询,最后再将命中的数据块 load 到内存中进行查询。

范围查询

step 1: 如果根节点和query range相交,则依据根节点将query range划分成左右两个query range,
使用left query range在左子树中查询,right query range在右子树中查询。如果不相交,则根据范围在左或者右子树中查询。
step 2: 命中的数据block中,需要对起点和终点block进行精确的过滤,中间的block结果肯定都满足查询范围。

k 近邻查询

step 1: 比较查询值和根节点的大小,如果大于,则递归查找右子树,否则左子树。
step 2: 对递归路径维护一个k个数据的小根堆,使用路径命中的数据block中距离查询值最近的k个值初始化小根堆,比较函数是距离。
step 3: 在当前的路径节点中,如果索引节点表示的超平面距离查询点比堆中最大值近,则将超平面另一侧的数据加入到小根堆中。
step 4: 沿着递归路径向上回溯,直到将根节点处理完。

此时小根堆中的 k 个数据就是查询数值的 k 近邻。
说明:

  • 如果查询值和索引值相等,则左右子树中任选一边进行递归查找就可以了,不需要在两边都进行递归。

高维场景

有了一维场景,非常容易推广到高维的场景。

构建过程

step 1: 选择一个维度,将数据按照该维度排序,数据量大的话使用外排序。
step 2: 选取中位数作为根节点的split value,除此以外,根节点需要记录下是哪一个维度的split value。
step 3: 前面两步将数据集划分成两部分,分别对两部分重复step 1、step 2,构造根节点的左右子树。
step 4: 持续上述递归构造过程直到节点关联的数据数集数量小于某个阈值。

这里的关键就是怎么选择在哪一个维度上将数据进行划分,这个和数据在该维度上的分布关系很大,遵循的原则是在这一步骤中,该维度的数据分布最散。

范围查询

和一维的区别在于每一次划分 query range 要在相应的维度划分,其他没有任何变化。

k 近邻查询

和一维的区别在于回溯的过程中,查询点到超平面距离计算要相应的变化,其他没有区别。

merge 过程中的优化

两份索引 merge,对于一维的数据,可以使用归并排序,高维场景则需要当成一份数据集来处理,目前没有什么好的方法来优化高维数据 merge 的速度。

总结

上面的方案就是 lucene 6 对数值类数据(高维)范围查询和近邻查询的优化方案 (bkd tree),相比之前的前缀编码的方案,存储空间大约能节省 50%,查询速度提高 2 倍。
具体实验结果可以参考下面 elastic 的 blog。

参考资料

  • kd tree
  • KDB tree
  • bkd tree
  • es blog
  • lucene issue tracking

 

微信公众号

声明:本站部分作品是由网友自主投稿和发布、编辑整理上传,对此类作品本站仅提供交流平台,转载的目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,不为其版权负责。如果您发现网站上有侵犯您的知识产权的作品,请与我们取得联系,我们会及时修改或删除。

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
SEM推广服务

Copyright©2005-2026 Sykv.com 可思数据 版权所有    京ICP备14056871号

关于我们   免责声明   广告合作   版权声明   联系我们   原创投稿   网站地图  

可思数据 数据标注行业联盟

扫码入群
扫码关注

微信公众号

返回顶部