欢迎光临本站!

分布式高维索引技术

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

  分布式多维索引综合了多维索引及分布式技术的优点,在语义空间中进行语义相似性搜索过程中通过高维索引技术修剪掉大量无关的搜索路径,并将计算搜索任务交由网络中所有参与者分担,实现了系统的可扩展性并克服了单点失败等问题。

  (1)基于P2P实现iDistance


  M-Chord[86]方法将iDistance与P2P相结合实现了语义空间中的相似性搜索。该方法首先对高维语义空间内的数据进行聚类,然后利用iDistance方法将高维数据对象映射到一个[0,2m)的一维关键字区域,保证不同的聚类间的高维数据映射到一维数轴上不同的区间内,确保网络中每个peer负责一个区间,并通过维护一个B+-tree来实现数据插入,删除及检索功能。在相似搜索过程中,首先确定查询的搜索区间,然后在区间内精确搜索得出结果。

  R-Chord[87]与M-Chord相似,实现了Chord与iDistance的结合。区别是R-Chord定义了相对位置码(RelativePositionCode,RPC)用以实现搜索过程中的进一步数据过滤。利用RPC可以过滤掉下界距离比修剪距离大的数据对象,减少距离计算,提高搜索效果。

  MCAN[88]结合CAN及iDistance技术用来实现语义空间中的相似搜索。它利用一种基于支点的技术为语义空间中的每个数据对象关联一个坐标,将数据对象映射到一个N维向量空间,并将映射后的对象分布于CAN网络内,将度量空间中的相似搜索转变为CAN空间内的搜索。

  SIMPEER[89]。M-Chord及MCAN方法数据预处理阶段(聚类及映射)仍以集中的方式处理,SIMPEER则完全实现了整个查询过程的分布式处理。SIMPEER采用一种三层聚类机制(peer,super-peer,routingclusters):每个peer聚类其自身数据,并用iDistance索引;super-peer管理所负责peer的聚类信息并利用扩展的iDistance方法计算hyper-clusters,hyper-clusters用以决定哪个peer处理super-peer接收到的查询请求;Hyper-clusters信息在super-peer间交互并进一步汇总产生一系列路由簇(RoutingClusters),路由簇信息保存在super-peer层,用来在super-peer网络中路由一个查询请求。

  SiMPSON[90]也为在高维语义空间中实现相似搜索的一种P2P索引结构。在SiMPSON中,任何支持一维范围查询的结构式P2P系统可作为其底层拓扑。首先每个peer局部聚类本地数据,然后基于iDistance方法将聚类范围映射为2个一维索引值(开始索引和结束索引),并利用一维索引值缩小搜索区间,从而减少搜索代价。

  (2)基于P2P实现R树


  P2PR-树[91]将P2P中peer组织成分层的树形覆盖网,且将每个peer负责的空间数据表示为peerMBR。系统中每个peer维护一条到根的路径,查询请求必须经过根节点才能达到目的节点。P2PR-树为不平衡树,如果数据是倾斜的,一些peer必须维护很长的路径信息,进而会降低搜索性能。

  NR-树[92]是R*-树的分布式结构。peers分为super-peers及passive-peers。super-peers管理一定数量的passive-peers形成一个簇。如果passive-peers数量超过一个阈值,簇依据CAN的方法执行分裂。super-peers构成一个CAN覆盖网来实现彼此间的通信。在每个簇中,super-peers负责构建分布式R*-树,当一个passive-peers发送一个查询请求,首先将其发送到super-peers,然后super-peers将请求发送给可能包含答案的passive-peers。

  P2PRdNN-树[93]结构与NR-树类似,唯一区别为super-peers间利用主通道以广播的方式传递消息。但是super-peers间以广播形式传递消息将导致系统较高的通信代价。

  RT-CAN[94]以云计算为研究背景,将CAN及R-树技术相结合用以研究云系统中索引高维数据的问题。系统为每个peer分配两个角色:存储节点及覆盖节点。存储节点维护一部分数据并为本地数据构建一个R-树。覆盖节点为CAN网络中的一个节点,负责CAN的一个分区。RT-CAN的发布策略为:对于一个将要发布的R-树节点N,如果其半径小于给定阈值,则将其发送到包含N中心的所有簇节点;否则所有与N重叠的CAN节点在其全局索引中维护N。对于一个窗口查询:首先将查询请求路由到包含查询窗口中心的CAN节点,然后将该查询递归发送到所有与查询窗口重叠的邻居,存储节点如果收到查询请求则搜索本地索引并返回结果。

  (3)基于P2P实现KD树


  DiST[95]为一种KD-树与CAN技术相结合的分布式多维索引结构。DiST利用KD-树划分方法划分语义空间,CAN网络中每个peer负责一个子空间并创建本地索引。全局索引分布于所有的节点中,每个peer仅有局部索引,并根据局部索引路由查询请求。

  DKDT[96]将Chord与KD-树相结合用以解决P2P系统中的相似搜索问题。该方法首席循环基于KD-树划分语义空间直到子空间内数据数目不高于给定的阈值,然后利用一个hash函数将每个子空间映射到底层覆盖网络。Peers利用Chord协议维护映射到环上的子空间,同时以DHT方式及KD-树方式维护peers。每个peer维护一个称为TreeInformationBase(TIB)的局部数据库。由于Chord及KD-树相互并不匹配,因此在DKDT中维护两个结构将导致较大的维护成本。对于一个范围查询,查询发起者利用TIB决定树中覆盖查询点的最低节点(peer),然后发送查询到该peer,接收到查询的peer不仅搜索本地数据而且根据其TIB将查询转发到其他peers进一步搜索。对于KNN查询,在范围查询的基础上查询发起者通过维护一个优先队列用以获取最优结果。

  m-LIGHT[97]与DKDT类似,利用KD-树划分空间,并为KD-树中每个叶子节点(子空间)分配一个关键字。通过关键字,每个叶子节点被底层DHT中的一个peer管理。m-LIGHT搜索机制与DKDT方法类似,其不同之处是m-LIGHT在插入,查询及删除数据的过程中利用一个数据感知分裂(data-awaresplitting)策略来确保系统负载平衡。

  SkipIndex[98]将SkipGraph及KD-树相结合以解决高维索引问题。该方法利用KD-树划分空间,然后根据分裂记录,KD-树的每个叶子节点(数据子空间)分配一个由0/1组成的位串作为该节点的关键字,实现了对子空间的编码;然后根据关键字将叶子节点与SkipGraph相关联,则数据的搜索,插入及删除操作可以依据SkipGraph协议实施。

  此外,学者们还提出了多种不同的基于P2P的高维索引技术,如Squid[99]、Z-NET[100]等基于P2P实现的空间填充曲线技术,LINP[101]等基于P2P实现的VA-file技术等。

评论区

表情

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

相关内容

点击排行

随机新闻

评论排行榜