论文部分内容阅读
摘要：为了解决相似查找请求，我们探讨了多维数据检索问题。在很多的情况下，相似检索是非常重要的。在本文中，我们为REIK覆盖网络提出了一个有效地相似查找算法，此时的网络称为SSREIK，SSREIK是一个新型的动态网络结构，这是为了分布式路由消息建立的。它允许范围估值，在分布方式中执行最近邻节点请求，并且利用一个分布式统计资料集合，以确保找到所有的相似对象。
近几年，P2P网络迅速成为计算机界关注的热点问题之一。P2P也就是对等网络，从计算模式上来说，打破了传统的C/S模式，在网络中的每个节点的地位都是对等的。每个节点即充当服务器，为其他节点提供服务，同时也享用其他节点提供的服务。除此之外，节点可在任何时刻加入或离开网络，并能路由到目的节点，节点动态地加入和离开网络时，维护网络的结构和功能成为设计的主要目的。在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户在系统中获取信息时，必须知道这些信息存放到哪个节点。
本文我们介绍一个带有相似查找算法的REIK覆盖网络，即SSREIK。它是利用分布式哈希表，确切的说，是在REIK覆盖网络中利用相似数据库查找方法。
一、网络的概述
SSREIK是解决REIK网络相似查找的框架。在SSREIK中，每个节点都包含在两层中，即REIK层和REIKiDistance层。在REIK网络中，利用哈希函数将每个数据对象都映射到一个逻辑名称空间，此空间也包含所有的逻辑节点，这样有利于节点间的路由。由于REIK层的节点相互链接，所以SSREIK网络的拓扑结构取决于REIK覆盖网络。
当一个新节点想加入网络时，它先接触一个已存在节点，并从REIKiDistance区域赋值一个键，它从相应的范围接收到键对应的数据对象。新节点也接收到REIKiDistance的配置。为了离开网络，节点必须通知它的后继节点，并将自身所有数据发送到后继节点。
REIKiDistance层形成了系统每个节点的接口。当接收到一个加入或离开操作时，它首先通过操作计算经过对象的REIKiDistance值。然后，REIK层地位键相应的节点，最后存储节点或删除。
在iDistance中由于常量c的使用，离散片组成的区域相当于簇。这样可能会发生：一个节点对应属于几个簇的键的区间。反过来也一样，对应一个簇的区间被划分为几个相邻的REIKiDistance节点。因此，存储数据的每个节点分别对应每个覆盖簇。
二、SSREIK的距离检索查找（iDistance）
在SSREIK中，每个节点都对应自己的数据，这构成了REIK覆盖网络。SSREIK是基于米制空间相似查找的向量检索算法。
首先，节点在局部数据上利用簇算法。簇算法产生了簇集C={Ci：（pi，ri）}。每个簇都由一个参考点和一个半径。每个数据对象都赋有最近簇，且利用iDistance方法映射一个一维数值。数据对象的iDistance值可用B+树表示。系统节点在他们的局部数据中主要执行范围查找。在簇列表中每个簇都执行范围查找算法。算法如下所示：
此算法展示了在任意节点上如何执行查找操作。如果请求范围与节点对应的簇区域相交，则执行第4行。因此，如果簇Ci满足不等式
，则区间 产生B+树。iDistance区间对应查找到的所有数据对象的簇区域。取回这些对象后，请求改进步骤。在改进步骤中，计算每个距离q的对象，如果在第8行小于r，则将对象添加到结果集S中。
对应每一个请求数据对象x，计算dist（q，x）且如果 ，则将x添加扫Range（q，r）请求结果集S中。
三、SSREIK的k个相似邻节点（K-NN）查找
分布式P2P系统中，查找操作的每个轮回代价都非常高。理想状态的P2P环境，优点是有个小的固定圈数，确保请求时间短，费用低。
本节中，我们介绍节点维护统计资料集的方法，此方法有助于计算从参考点p到第k个对象的距离，并避免了多重范围请求的执行。与iDistance方法相似，节点执行相应的最近邻节点请求。如果找到了不到k个数据对象，则增大请求半径，直到找到k个数据对象。由于我们的方法是一个结构化P2P环境，因此可利用小半径并不断增加直到找到k个数据对象。
通过分布式统计资料计算请求半径。如果为了查找k个对象操作失败，则不会避免第二次请求。在第二次请求中，上限由起始节点估算。为了减少查找操作成本，我们的方法利用了逐步增长半径。请求范围R（q，r）的底限为rlow，即R（q，r，rlow），且满足不等式 。在B+树中修改两个区间分别为：
为了降低K-NN查找成本，每个中间节点接收到具有最短距离的节点数目不超过k。
四、总结
P2P技术应用于大量数据共享系统中。这些系统的必要条件是在大量数据中定位数据的有效方法。但是，现在的大多數P2P系统既没有提供精确键匹配机制，也没有提供有效的解决算法。本文我们对REIK网络提出了一个相似查找算法，即SSREIK，这是一个动态结构网络，建立了分布式路由消息。它允许范围估值，在分布方式中执行最近邻节点请求，并且利用一个分布式统计资料集合，以确保找到所有的相似对象。
近几年，P2P网络迅速成为计算机界关注的热点问题之一。P2P也就是对等网络，从计算模式上来说，打破了传统的C/S模式，在网络中的每个节点的地位都是对等的。每个节点即充当服务器，为其他节点提供服务，同时也享用其他节点提供的服务。除此之外，节点可在任何时刻加入或离开网络，并能路由到目的节点，节点动态地加入和离开网络时，维护网络的结构和功能成为设计的主要目的。在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户在系统中获取信息时，必须知道这些信息存放到哪个节点。
本文我们介绍一个带有相似查找算法的REIK覆盖网络，即SSREIK。它是利用分布式哈希表，确切的说，是在REIK覆盖网络中利用相似数据库查找方法。
一、网络的概述
SSREIK是解决REIK网络相似查找的框架。在SSREIK中，每个节点都包含在两层中，即REIK层和REIKiDistance层。在REIK网络中，利用哈希函数将每个数据对象都映射到一个逻辑名称空间，此空间也包含所有的逻辑节点，这样有利于节点间的路由。由于REIK层的节点相互链接，所以SSREIK网络的拓扑结构取决于REIK覆盖网络。
当一个新节点想加入网络时，它先接触一个已存在节点，并从REIKiDistance区域赋值一个键，它从相应的范围接收到键对应的数据对象。新节点也接收到REIKiDistance的配置。为了离开网络，节点必须通知它的后继节点，并将自身所有数据发送到后继节点。
REIKiDistance层形成了系统每个节点的接口。当接收到一个加入或离开操作时，它首先通过操作计算经过对象的REIKiDistance值。然后，REIK层地位键相应的节点，最后存储节点或删除。
在iDistance中由于常量c的使用，离散片组成的区域相当于簇。这样可能会发生：一个节点对应属于几个簇的键的区间。反过来也一样，对应一个簇的区间被划分为几个相邻的REIKiDistance节点。因此，存储数据的每个节点分别对应每个覆盖簇。
二、SSREIK的距离检索查找（iDistance）
在SSREIK中，每个节点都对应自己的数据，这构成了REIK覆盖网络。SSREIK是基于米制空间相似查找的向量检索算法。
首先，节点在局部数据上利用簇算法。簇算法产生了簇集C={Ci：（pi，ri）}。每个簇都由一个参考点和一个半径。每个数据对象都赋有最近簇，且利用iDistance方法映射一个一维数值。数据对象的iDistance值可用B+树表示。系统节点在他们的局部数据中主要执行范围查找。在簇列表中每个簇都执行范围查找算法。算法如下所示：
此算法展示了在任意节点上如何执行查找操作。如果请求范围与节点对应的簇区域相交，则执行第4行。因此，如果簇Ci满足不等式
，则区间 产生B+树。iDistance区间对应查找到的所有数据对象的簇区域。取回这些对象后，请求改进步骤。在改进步骤中，计算每个距离q的对象，如果在第8行小于r，则将对象添加到结果集S中。
对应每一个请求数据对象x，计算dist（q，x）且如果 ，则将x添加扫Range（q，r）请求结果集S中。
三、SSREIK的k个相似邻节点（K-NN）查找
分布式P2P系统中，查找操作的每个轮回代价都非常高。理想状态的P2P环境，优点是有个小的固定圈数，确保请求时间短，费用低。
本节中，我们介绍节点维护统计资料集的方法，此方法有助于计算从参考点p到第k个对象的距离，并避免了多重范围请求的执行。与iDistance方法相似，节点执行相应的最近邻节点请求。如果找到了不到k个数据对象，则增大请求半径，直到找到k个数据对象。由于我们的方法是一个结构化P2P环境，因此可利用小半径并不断增加直到找到k个数据对象。
通过分布式统计资料计算请求半径。如果为了查找k个对象操作失败，则不会避免第二次请求。在第二次请求中，上限由起始节点估算。为了减少查找操作成本，我们的方法利用了逐步增长半径。请求范围R（q，r）的底限为rlow，即R（q，r，rlow），且满足不等式 。在B+树中修改两个区间分别为：
为了降低K-NN查找成本，每个中间节点接收到具有最短距离的节点数目不超过k。
四、总结
P2P技术应用于大量数据共享系统中。这些系统的必要条件是在大量数据中定位数据的有效方法。但是，现在的大多數P2P系统既没有提供精确键匹配机制，也没有提供有效的解决算法。本文我们对REIK网络提出了一个相似查找算法，即SSREIK，这是一个动态结构网络，建立了分布式路由消息。它允许范围估值，在分布方式中执行最近邻节点请求，并且利用一个分布式统计资料集合，以确保找到所有的相似对象。