【作者】 周敏奇；

【导师】 周傲英；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2008， 博士

【摘要】 对等计算(Peer-to-Peer,简称P2P)是一个自组织的分布式网络系统。脱胎于文件共享,当前P2P系统的研究热点已经逐步过渡到:系统资源共享、分布式数据管理等。这类研究给现代网络应用注入了新的活力,因为P2P系统打破了现有网络结构,进而提供了一个自组织、高分散、可扩展、节点对等的分布式网络。同时,这种分布式网络结构也给网络应用带来了很多新的挑战,例如,如何提供有效的复杂数据查询、如何获取当前网络中数据的分布信息等等。尽管对等计算系统在文件共享、简单数据管理方面已经取得了不少研究成果,但是许多问题(如复杂数据管理等)依旧亟待解决。本文的研究重点是在现有成熟的P2P覆盖网络(Chord)基础上,对其改进、优化,并提出了一个新的P2P系统——GChord系统。结合了Chord系统的路由特性和格雷码(GrayCode)数据索引编码的优点,GChord(Gray Code based Chord System)系统由此具备了支持复杂数据管理能力。现有GChord系统支持的复杂数据管理主要包括:当前网络中数据密度分布函数的准确估计、一维(多维)精确匹配查找、一维(多维)范围查找、偏好查找、多属性查找等。以后我们将对GChord系统不断研究、充实,使之成为一个完备的P2P系统。下面给出本文的主要贡献:●实现了GChord系统中节点管理和数据管理的无缝结合。GChord系统脱胎于Chord系统,但是青出于蓝而胜于蓝。GChord系统将原Chord系统中相互独立的节点管理和数据管理紧密地结合起来,进而获得了很多Chord系统不具备的特性。对于节点管理,GChord系统和Chord系统具有相同的组织、维护方式。对于数据管理,GChord系统结合了基于格雷码(任意相邻的两个格雷码相差一位)混洗编码(shuffle-based)的数据索引键值生成技术,实现了节点管理和数据管理的无缝结合。GChord系统的指表(fingertable,即路由表)不仅实现了节点路由的O(logn)复杂度,同时也实现了数据值域路由的O(logn)复杂度,其中n为系统中节点数目。突破了Chord系统只支持精确匹配查找的限制,GChord系统能够支持包括范围查找在内的许多复杂数据管理。●对GChord系统中分布无关数据密度分布函数估计提供了支持,即让网络中的每个节点都能精确估计当前网络中数据的密度分布。P2P系统的许多应用均受益于密度分布估计,例如:负载平衡分析、复杂数据查询和数据挖掘等等。分布无关数据密度函数估计算法的主要特性是,不论底层数据按照何种模型分布抑或是根本不存在任何分布模型,该算法均能以近似的估计精度准确估计当前网络中的数据密度分布函数。分布无关密度估计算法首先将底层数据的任意分布转换成一中间分布——累计概率分布函数。由于累计概率分布函数的输出在[0,1]之间均匀分布,因此接着对累计概率分布函数的输出随机采样,可以准确估计当前网络中数据的密度分布。本文在GChord系统环境下,提出了三种计算累计概率分布函数的有效算法和两种对累计概率分布函数的输出随机采样的算法。累计概率分布函数计算算法让网络中每个节点只维护累计概率分布函数中相互不重叠的一个片段,而所有这些片断综合起来又构成了完整的累计概率分布函数,由此降低了各个节点的维护代价。我们从理论上证明了累计概率分布函数的计算误差和分布无关数据密度估计的估计误差,同时给出了详尽的算法。充分的实验也证明了该算法在估计数据分布方面的有效性和高效性。●对GChord系统中偏好查找提供了支持。所谓偏好查找是指查询请求中包含有用户对各个属性项不同偏好程度并返回top-k条数据元组的查询。对于各个属性项具有不同偏好程度的查询请求,其查询结果可能大相径庭。现有数据索引技术均无法对偏好查找提供很好的支持。本文提出了一种在GChord系统上支持偏好查找的新颖方法。通过估计当前网络中的数据分布,并计算包含有top-k查询数据元组的区域范围,将偏好查找转换为范围查找并执行有效查找。通过对数据空间多维柱状图信息进行离散余弦变换可有效维护当前网络中数据的分布,从而实现数据密度分布的准确估计。本文也提出了对偏好矩阵(由查询请求给定)作奇异值分解,有效计算对应查找范围的算法。在实现偏好查找到范围查找的有效转换之后,通过多播区域(mutli-cast zone)的形式获取相关节点上的top-k条数据元组。本文给出了数据分布估计算法和范围计算的算法及其理论分析。详尽的实验证明了该方法在处理偏好查找方面的有效性和高效性。●对GChord系统中多属性范围查找提供了支持。所谓多属性查找是指查询请求中仅包含有用户关心属性项的谓词(即查询中包含的属性项可以是数据元组属性项集合的子集)。因此,该类查询请求中包含的谓词可以针对任意数目的属性项,也可以针对任意属性项之间的组合。现有P2P系统都无法高效的处理该类查询。由于GChord系统实现了节点管理和数据管理之间的无缝结合,进而实现了相邻数据之间的快速路由,由此提供了对多属性查询的良好支持。本文提出了使用卡诺图(Karnaugh map)有效计算包含有查询结果节点的算法,并且以多播树(multi-cast tree)的方式获取这些节点上数据元组的算法及其理论分析。详尽的试验证明了该方法在处理多属性查询的有效性和高效性。综上所述,本文详细介绍了GChord系统,及其支持的复杂数据管理操作。GChord系统实现了节点管理和数据管理的无缝结合,并对当前网络中分布无关数据密度的精确估计、偏好查找、多属性范围查找、一维精确匹配查找(源于对Chord系统的继承)、多维精确匹配查找和一维(多维)范围查找(源于对多属性范围查找的支持)提供了支持。这些功能满足了当前P2P系统发展的需要,促进了P2P系统的发展。以后我们将不断充实和完善GChord系统,使之成为一个成熟、完备的P2P系统。更多还原

【Abstract】 Peer-to-Peer(P2P in short) system is a self-organized distributed network system. Derived from file sharing,current research hot spots in P2P systems have been shifted to systemic resource sharing and distributed data management.Network applications are boosted immensely by such kind of research,since current network structure is broken through by P2P network systems which provided by a self-organized,highly distributed,scalable networks.Meanwhile,new challenges are brought into network applications under such kind of distributed network structures, such as providing complex query processing operators,estimating data density in the current system and so on.Much researches have been done and much goal has been achieved on resource sharing,simple data management in the P2P system environment,while lots of problems are still needed to be solved imperatively.The focus of this paper is to provide a new P2P system(called GChord),which is improved,optimized from one existing P2P overlay network(say Chord).GChord(Gray Code Based Chord) system provides well support to complex data management,since it combines the routing property of Chord and the excellency of data index based on shuffle-based Gray Code seamlessly.The complex data management supported by current GChord system can be listed as follows:data density estimation in the current network, one-dimensional(multi-dimensional) exact match query,one-dimensional(multidimensional) range query,preference query,multi-attribute(partial match) range query and so on.Moreover,new data management operators will be added to the new generation of GChord system,as our future research focus.The main contribution of this paper is to propose the new GChord system and its data management. The details are given as follows:●GChord system provides seamless combination between node management and data management.Inspired by Chord,GChord system out performance much over Chord.Since its seamless combination of node management and data management,complex data management operators can be supported by GChord while not by Chord.For node management,GChord has the same construction and maintenance as Chord.For data management,GChord provides Gray Code(any two adjacent Gray Codes differ in one-bit) based data index strategies,which in further results in the seamless combination of node management and data management.GChord system not only provides the complexity of O(logn) for node access in the system under its finger table, but also provides the complexity of O(logn) in data access according to its domain routing under its finger tables,where n is the number of nodes in the current system.Besides exact match query which provided by Chord,GChord system gives support to plenty of complex data management types.●GChord system gives support to the global data distribution estimation in the current system.It can benefit many P2P applications,such as load balancing analysis,query processing,data mining,and so on.In this paper,we propose a novel model named distribution-free data density estimation,which is based on distribution-free(i.e.,independent of data distributions) sampling on global cumulative distribution to achieve high estimation accuracy with low estimation cost regardless of distribution models of the underlying data.The idea of distribution-free estimation is deployed in GChord system by sampling a small subset of peers to estimate global data distribution over the data domain.Algorithms on computing and sampling global cumulative distribution based on which global data distribution is estimated are introduced with detailed theoretical analysis.Our extensive performance study confirms the effectiveness and efficiency of our methods under different data distributions in dynamic GChord networks.●GChord system gives support to preference query evaluation which returns top-k results according to users’ specific interests has been well studied in centralized databases.However,it has never been discussed in the Peer-to-Peer (P2P) environment and remains imperative to be solved.In this paper, we propose a novel method for efficient preference query processing in GChord system.By effectively calculating a corresponding range which contains top-k results based on estimated data density in the current system using discrete cosine transformed histogram information,a preference query is transformed into a range query for efficient processing.Singular value decomposition of preference matrix is deployed to simplify the progress of range computation. Algorithms on density estimation and range computation are given as well as the theoretical analysis.Our extensive performance study confirms the effectiveness and efficiency of our methods under different data distributions in GChord system.●GChrod system gives support to multi-attribute query.Multi-attribute query is referred to as a query which only contains predicates on attributes that users are interest(i.e.subset of attributes contained in data tuples).That’s to say,not only the number of attributes which have predicates in query could be arbitrary,but also the combination of attributes which have predicates in query could be arbitrary.That’s why such kind of queries can’t be supported well by existing P2P systems.However,GChord system gives well support to it,since it provides seamless combination between node management and data management,resulting in quick routing between data tuples according attribute domains.This paper proposes new algorithms on nodes computing which contains desired results based on Karnaugh map,and new algorithms on node accessing based on multi-cast tree constructed on-the-fly.Our extensive performance study confirms the effectiveness and efficiency of our methods for multi-attribute query in dynamic GChord networks.In a word,this paper gives a detailed discuss on GChord system and its functionality on data management,including overlay network and complex data management. GChord system achieves seamless combination between node management and data management.GChord system provides support to distribution-free data density estimation in the current network,preference query,multi-attribute(partial match) range query,one-dimensional exact match query(since the derivation from Chord system),multi-dimensional exact match and one-dimensional(multidimensional) range query(since the support for multi-attribute range query) and so on.For more applications to be supported in data management,we propose to give them with support in the next generation of GChord system.更多还原