欢迎光临本站!

高维数据索引-度量空间高维索引

来源:技术探讨    更新时间:2019-12-17 14:19:12    编辑:老王    浏览:448

  度量空间高维索引的分类


  度量空间高维索引利用满足三角不等式性质的距离函数来实现高维数据的相似性搜索,从不同的角度可以对度量空间高维索引做出不同的分类。

  (1)根据索引组织形式,可分为树型索引和非树型索引。树型索引中索引节点按照树的形式组织,如BK-树[40]、VP-树[41]等;非树型索引中索引节点不按照树的形状组织,如AESA[42]等。

  (2)根据索引构建过程中所使用的距离函数类型,可分为离散距离类及连续距离类。离散距离类索引利用离散距离函数构建索引,距离函数提供有限数量的距离值,如BK-树;连续距离类利用连续的距离函数构建索引,距离函数提供大量甚至无限的距离值,如M-树[43]等。

  (3)混合索引方法将树状索引与顺序扫描方法相结合,具体实例有GC-树[44]、DABS-树[45]等。

  典型度量空间高维索引


  (1)VP-树类。VP-树为一种连续距离类树型索引,采用自上而下的方法来构建,利用数据对象到参考点之间的相对距离修剪查询过程中与给定查询语义无关的数据,不支持数据的更新和删除。VP-树(图7)递归构造一棵平衡二叉树,首先选择任意数据对象p作为根节点(参考点),同时计算出其他数据到p的中值距离M;然后将与p的距离小于M的一半数据放入左子树,另一半放入右子树;针对左右子树重复执行上述过程,直到节点中数据数目小于给定的阈值。

高维数据索引-度量空间高维索引

  针对VP-树采用二叉树结构所导致的索引高度很高,从而引起大量的距离计算,造成性能下降的问题,MVPT[46]在一个节点中使用多个参考点对数据进行划分,一定程度上提高了搜索效率。VPF[47]将VP-树的每一层中参考点距离大约为M的“中间部分”数据对象挑选出来,并用“中间部分”数据构建第二棵树,以此类推获得具有多棵树的“森林”。这样当需要搜索“中间部分”数据时,不用同时进入左右子树进行搜索。

  (2)BK-树类。BK-树(图8)属于离散距离类树状索引,索引树的构造过程如下:首先从空间内原始数据集U中任意选择一个数据对象p∈U作为根节点,然后利用离散距离函数将剩余的数据对象划分为多个子集作为树的分支。对于每个离散距离i,定义子集Ui={u∈U,d(u,p)=i}为距离根节点为i的所有数据元素的集合,并为每一个非空子集Ui在BK-树上建立分支。然后为所有的非空子集Ui循环构造BK-树直到子集中剩余元素数目为1或小于给定的阈值为止,所有将作为子集根节点的数据对象称为支点(pivot)。

高维数据索引-度量空间高维索引

  FQ-树[48]对BK-树的结构进行了改进。与BK-树不同的是,FQ-树所有的数据元素存储在叶子节点中,且存储在同一层节点中的所有支点是相同的。该结构可以减少查询时距离比较的次数,代价是树的高度增加。FHQ-树[49]对FQ-树进一步做了改进———强制所有的叶子节点在同一高度上,这样的设置使我们进行相似性搜索时可以统一考虑同一层的节点,不用额外区分叶子节点和中间节点,提高了搜索效率,但其代价是增加了某些叶子节点的高度。FQA[50]不是树的形式,但具有比FHQ-树更紧凑的结构。FQA将FHQ-树叶子节点中的数据按从左至右的顺序放入一个数组中,并记录下从根节点到数据的高度。在同样内存的情况下,FQA可以较FHQ-树访问更多的支点,从而提高搜索效率。

  (3)M-树类。M-树是基于连续距离类的平衡树状索引。在M-树中每个节点中首先选取代表元素,然后将靠近代表元素的数据构建成以代表元素为根的子树,代表元素存储其覆盖半径信息。当进行相似性搜索时,首先比较搜索范围与节点中代表元素的覆盖范围以确定语义相关(范围相交)的子树,然后进入子树中进一步搜索。当插入数据时,选择距离最近的代表元素对应的子树插入,当引起节点溢出时,需执行分裂操作(图9)。M-树可以支持数据的更新,同时很大程度上减少了相似性搜索过程中的计算量,但是没有处理好节点间的重叠问题。

高维数据索引-度量空间高维索引

  MB+-树[51]针对节点间的重叠问题,利用B+-树和Block-树索引空间内高维数据,避免了兄弟节点间的区域重叠。M2-树[52]使用多种距离函数,可以同时根据数据的多个特征对数据进行检索,实现了高维数据的复杂查询。Slim-树[53]提出了基于最小生成树的节点分裂方法,并通过一个后处理过程最小化索引节点数目及节点间的重叠度。M+-树[54]提出了一种基于距离及关键维的两步分割策略,根据对相似性影响最大的关键维对数据进行二次过滤,在有效提高数据分割效率的同时降低了索引树的高度。MS-树[55]提出了活动子空间和非活动子空间的概念,并通过一种空间映射方法减少对非活动子空间的访问次数,提高了查询性能。

  (4)混合索引结构。高维索引能够有效处理聚类或分布密集的数据集,当数据分布特别稀疏时,采用顺序扫描可能更加有效。混合索引能够区分数据集在空间中的分布状态,针对不同的数据分布针对性的采用顺序扫描或树状索引,能够有效的提高相似性搜索的效率。如GC-树首先根据一个密度函数划分数据密集区域及稀疏区域,然后对两者分布采用树状索引及顺序扫描;DABS-树根据数据分布动态调整数据页大小,并通过顺序扫描一个一级目录以解决目录过载的问题;文献[56]对树状索引无法有效处理的数据采用顺序扫描的方法,能够一定程度上解决“维灾”带来的影响。文献[57]提出一种基于查询采样的高维数据混合索引结构,基于查询采样的方法将分步稀疏的数据从树状索引中分离出来,并对其进行顺序扫描处理,能够有效提高搜索效率。

  此外,学者们还提出了多种索引结构,如针对离散距离函数的BK-树;动态多级树SA-树[58];可适用于离散距离函数及连续距离函数的BS-树[59]等,这里不再详细介绍。

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜