（计算机应用技术专业论文）混合式p2p系统中的相似查询研究.pdfVIP

浙江大学硕士学位论文 摘要 摘要 从2 0 世纪8 0 年代以来，随着多媒体、w e b 等技术的发展，多媒体数据库在 许多应用领域变得非常重要，其中一个重要的研究方向便是针对这些数据对象建 模为高维数据向量，然后针对高维数据进行相似查询，包括基于内容的视频、音 频检索，流数据的匹配，数字图像处理，文本处理等。同时，由于相似查询计算 的复杂性，集中式处理会导致单机负荷过高，造成性能瓶颈等问题，因此，随着 p 2 p 系统的兴起和发展，分布式处理的研究成为了重点。然而当前的研究主要着 重于结构化p 2 p 系统和传感器网络上的相似查询，而对无结构化p 2 p 系统以及混 合式p 2 p 系统上的查询研究相对较少，因此，需要在p 2 p 系统的普适性问题上做 更多的研究。 本文的研究内容是如何在混合式p 2 p 系统中完成相似查询，包括最主要的两 个查询类型：窗口查询和补n 查询。首先分析了各种p 2 p 系统的结构，然后挑 选混合式p 2 p 系统作为底层p 2 p 系统，并针对其特点提出了一个相似查询的分布 式框架。 针对分布式框架，本文提出了两个分布式查询算法，用于解决窗口查询和 k n n 查询。算法在每个单独的网络节点上，数据通过一种降维算法映射到一维空 间，在超级节点上，构造数据的统计信息表以及构造网络查询树，算法在每次查 询时，按照查询树的规则来访问整个网络并利用统计信息剪枝网络中的节点查 询，避免网络的泛洪。在k n n 查询过程中，还提出了一个半径估计算法，用于将 复杂的扑n 查询转换为简单的范围查询。 实验使用了不同的数据集来评测两个算法的查询效率，实验表明这两个算法 具有很高的查询效率，并且针对k n n 查询，实验验证了半径估计算法的有效性和 可行性。 关键词：降维算法，超级节点p 2 p 系统，相似查询，高维数据，半径估计 a b s t r a c t w i t ht h ed e v e i o p m e n to fm u l t i m e d i a ，w e ba n d o t h e rt e c h n o l o g y ，m u l t i m e d i a d a t a b a s e sh a v eb e c o m ev e r yi m p o r t a n ti nm a n ya p p l i c a t i o n s ，o n eo f t h ei m p o r t a n t r e s e a r c hi st om o d e lt h e s ed a t ao b j e c t sw i t hh i g h d i m e n s i o n a lv e c t o r s ，a n da d d r e s s s i m i l a f i t yq u e r i e so nt h e m ，i n c l u d i n gc o n t e n t b a s e dv i d e o ，a u d i or e t r i e v a l ，d a t as 订e a m m a t c h i n g ，d i g i t a li m a g ep r o c e s s i n g ，t e x tp r o c e s s i n g ，e t c d u et ot h e c o m p l e x i t yo f s i m i l a r i t yq u e r i e s ，c e n t r a l i z e dp r o c e s s i n gw i l ll e a dh i g ho v e r l o a d sa n dp e r f o r m a n c e b o t t l e n e c k so nas i n g l ec o m p u t e r , t h e r e f o r e ，w i t ht h er i s eo f p 2 ps y s t e m s ，d i s t r i b u t e d p r o c e s s i n gh a sb e c o m et h ef o c u s r e s e a r c hp o i n t t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nt h et w om o s ti m p o r t a n ts i m i l a r i t yq u e r yt y p e s ： w i n d o w b a s e dr a n g e q u e r ya n dk - n e a r e s tn e i g h b o rq u e r y f i r s t l y , w es e l e c tt h es u p e r p e e rp 2 ps y s t e m sa st h eu n d e r l y i n gn e t w o r ko v e r l a ya n dd e s i g na d i s t r i b u t e d f r a m e w o r kf o rq u e r y t h e n w ep r o p o s et w oa l g o r i t h m st oa d d r e s st h ee f f i c i e n tp r o c e s s i n go f s i m i l a r i t y q u e r i e s ，w h i c hd a t ai sh o r i z o n t a l l yd i s t r i b u t e da c r o s st h ep 2 ps y s t e m s i n e a c hp e e r , d a t ai sm a p p e di n t oo n e d i m e n s i o n a lk e ya c c o r d i n g t oad i m e n s i o nr e d u c t i o na l g o r i t h m ， a n di ns u p e r - p e e r s ，n e t w o r kq u e r yt r e ei sb u i l tt om a k et h eq u e r yc a n a c c e s st h ew h o l e n e l f kb yr u l e ，s t a t i s t i ci n f o r m a t i o no fd a t ai sc o n s t r u c t e di no r d e r t op r u n et h e a c c e s s e dp e e r si ne a c hq u e r y i nt h ek n nq u e r yp r o c e s s ，ar a d i u se s t i m a t i o na l g o r i t h m i sp r o p o s e df o rt h ee s t i m a t i o no ft h ed i s t a n c ef r o mq u e r yp o i n tt ot h e 舻n e i g h b o r ， t h e nt h ec o m p l e xk n nq u e r yc a nb ec o n v e r t e dt oas i m p l er a n g eq u e r y i nt h ee x p e r i m e n t s ，w ee m p l o ys y n t h e t i cd a t ai n c l u d i n gu n i f o r md i s t r i b u t e dd a t a a n dg a u s s i a nd i s t r i b u t e dd a t at ot e s tt h ee f f i c i e n c ya n d c o l t e c t n e s s ，r e s u l t sr e v e a lt h e h i g hq u e r ye f f i c i e n c yo f t h eq u e r ya l g o r i t h m sa n de f f e c t i v e n e s so f t h er a d i u se s t i m a t i o n a l g o r i t h mf o rk n nq u e r y k e y w o r d s ：d i m e n s i o nr e d u c t i o n ，s u p e r - p e e rp 2 ps y s t e m s ，s i m i l a r i t yq u e r y , h i g h d i m e n s i o n a ld a t a , r a d i u se s t i m a t i o n 浙江大学硕士学位论文图目录 图目录 图1 1 二维空间上的圆形范围杏询示例2 图1 2 三维空间上的窗口查询示例3 图1 3 二维空间上的2 小烈查询示例3 图1 4 二维空间上的反向n n 奄洵示例4 图2 1 超级节点p 2 p 系统16 图2 2 分布式相似查询系统架构设计17 图3 1 ( a ) 数据映射示意图( b ) 转换后的q 示意图2 2 图3 2 超级节点s p 内部查询算法2 3 图3 3 ( a ) s p 连接图( b ) 构造的s p 拓扑图2 4 图3 4 构造杏询拓扑树算法2 5 图3 5 超级节点统计信息示意图2 6 图3 6 构造s p 统计信息算法2 6 图3 7 超级节点问查询算法一2 7 图3 8 均匀分布：范围查询的剪枝率。3 1 图3 9 均匀分布：选择率对查询的影响。3 l 图3 1 0 均匀分布：网络大小对查询的影响3 2 图3 1 l 高斯分布：范围查询的剪枝率3 2 图3 1 2 高斯分布：网络大小对查询的影响3 3 图4 1 最近邻居查询q ，和印2 的搜索区域：3 7 图4 2 ( a ) 超级聚类杏询示意图f b ) 超级聚类映射后查询区间4 0 图4 3 超级节点s p 内部奄询算法4 2 图4 4 超级节点统计信息示意图4 3 图4 5 超级节点间查询算法。4 4 图4 6 节点只的采样距离分布统计信息4 5 图4 7k n n 查询距离估计示意图。4 6 图4 。8 固定选择率的凤半径估计4 9 图4 9 变化选择率的凡半径估计4 9 图4 1 0 固定选择率的均匀分布数据集k n n 查询剪枝率5 0 图4 1 l 变化选择率的均匀分布数据集k n n 查询剪枝率5 0 图4 1 2 固定选择率的高斯分布数据集k n n 查询剪枝率5 l 图4 1 3 变化选择率的高斯分布数据集k n n 查询剪枝率5 2 l l i 浙江大学硕士学能论文表目录 表目录 表3 1 常用符号及含义2l 表3 2 节点尸统计信息表示格式2 3 表4 1 常用符号及含义3 5 表4 2 节点p 统计信息表示格式。3 9 表4 3 超级节点s 尸内部统计信息表示格式。4 0 i v 浙江大学硕i 二学位论文 第1 章绪论 第1 章绪论 1 1 研究背景及意义 从2 0 世纪8 0 年代以来，随着多媒体，w e b 等技术的发展，多媒体数据库在许多 应用领域变得非常重要，包括医疗数据分析，计算机辅助设计和制造( c a d c a m ) ， 地理信息系统，分子生物学，导航系统，智能交通，数字战场等。其中一个重要 的研究方向便是针对这些数据对象建模为高维数据向量，然后针对高维数据进行 相似查询，包括基于内容的视频、音频检索，流数据的匹配，数字图像处理，文本处 理等。 由于高维数据的查询和检索广泛的应用前景和市场价值，许多的研究者以及 数据库厂商都投入了大量的研发力量来解决此问题，从历年的数据库主流会议 s i g m o d ，v l d b ， c d e 等录用的文章来看，几乎所有大学的计算机系都有针对 此方面的研究，著名的包括香港科技大学，新加坡国立大学，斯坦福大学等。从 数据库厂商方面来看，o r a c l e ，i n f o r m i x ，d b 2 以及s q ls e r 、，e r 等也开始扩展当 前的关系数据模型来支持高维数据的查询和检索，其中包括o r a c l e 提供了定位器 ( l o c a t o r ) 以及基于位置查询的支持，i n f o r m i x 提供了r 树索引结构的实现等【l 】。 从另一方面来看，由于相似查询计算的复杂性，集中式处理会导致单机负荷 过高，造成性能瓶颈等问题，因此，分布式处理的研究成为了重点，尤其是随着 p 2 p 系统的兴起，高维数据的查询和检索有了分布式计算平台 2 】。 p 2 p 系统范型能有效的组织大量的数据，将数据源分布到不同的节点，同时， 如果能有效的利用分布式索引，高维数据的分布式查询将能够与集中式环境中的 技术更好的融合。但是当前的相似查询的研究主要局限在集巾式环境中或者结构 化p 2 p 系统中f 3 】3 ，而导致了节点不能够自治管理数据等缺点。 因此，如何在分布式环境中更好的利用当前集中式环境中的相似查询算法， 或者提出适合分布式环境的算法成为了当前相似查询的一个热点问题。 浙江大学硕士学位论文第l 章绪论 1 2 国内外研究现状及存在问题 1 2 1 相似查询处理类型 相似查询是一个难点，也是一个热点问题。每年的数据库主流会议和期刊都 有许多相关研究论文发表，因此，本节提供了一个综述，将国内外学者在相似查 询方面的研究工作及成果进行归纳总结，并分析出存在的问题，为后续的工作和 研究提供基础。 相似查询根据是否需要指定查询范围以及查询的结果集大小可以将其归为 以下几类【1 ，4 】： 1 ) 点查询( p o i n tq u e r y ) ：给定一个查询点q ，在当前的数据集合中查找所有 与g 完全重合的数据对象。一个更为简单的点查询是只判断数据集合是 否包含给定的数据点口。 2 ) 范围查询( r 锄g eq u e r y ) ：给定一个查询范围r ，一个范围查询查找出所有 被包含在r 的数据对象。二维空间里面，常见的范围r 包括矩形，圆， 图1 1 显示了一个圆形范围查询例子，查询结果包含两个空间数据对象a 和b 。 y c e 八o d ( ：a ) dx 图1 1 二维空间上的圆形范围查询示例 3 ) 窗口查询( w i n d o wq u e r y ) ：给定一个查询窗口w ，查找落在窗口里的空间 数据对象。d 维数据空间的查询窗口是一个d 维的矩形区域。图1 2 显示 了一个三维窗口查询例子，查询结果包含两个空间数据对象口和b 。 2 浙江大学硕f ：学位论文第l 章绪论 x y 图1 2 三维空间上的窗口查询示例 4 ) 最近邻居查询洲e a r e s tn e i g h b o rq u e r y ) ：给定一个查询点q ，一个距离度 量m ( 如欧几里德距离等) ，n n 查询查找出离g 最近的空间数据对象。 此查询在实际生活中非常有用，比如查找离学校最近的银行或者公交站 牌等。 5 ) k 最近邻居查询( k - n e a r e s tn e i g h b o rq u e r y ) ：k n n 查询是n n 查询的扩展， 定义为在数据空间中查找出离口最近的k 个空间数据对象。图1 3 显示 了一个二维空间的故扣2 ) 最近邻居查询例子，查询结果包含两个空间数 据对象a 和b 。 j y c ，一e d 、 e 、 ( iq a ) u d x 图1 3 二维空间上的2 - n n 查询示例 6 1 近似k 最近邻居查询( a p p r o x i m a t ek - n e a r e s tn e i g h b o rq u e r y ：a k n n 查 3 浙江大学硕士学位论文第l 章绪论 询是k n n 查询的近似。有时候用户查询并不关心精确的值，只要能在某 种概率( 8 0 等) 上满足，但足需要快速返回结果时，a k n n 就能发挥作用。 7 ) 反向k 最近邻居查i 自l ( r e v e r s ek - n e a r e s tn e i g h b o rq u e r y ) ：给定一个查询 点口，一个度量空间胍反向k 最近邻居查询查找出所有将g 作为其k 最近邻居的空间数据对象。图1 4 显示一个二维空间的反向珂扣1 ) 最近邻 居查询例子，空间数据点口和b 的n n 都是查询点g ，因此查询点印的反 向最近邻居是口和b 。 y e c d g ) lb 卜 u d x 图1 4 二维空间上的反向n n 查询示例 1 2 2 集中式环境下相似查询处理介绍 经过二十几年的发展，研究者针对相似查询提出了许多索引结构以及查询方 法，这主要是在集中式环境下针对数据本身的一些方法，分为以下几类。 1 2 2 1 基于树的索引方法 r 树【5 】是空间索引结构的鼻祖，其核心思想是利用了最小包围区域( m b r ) 来作为存储区域，方便了树型结构的构造和索引，其后，人们在此基础上针对不 同空间运算提出了不同改进，形成了一个繁荣的索引树族。 r 【6 】树不仅考虑了索引空间的m b r ，而且还考虑了索引空间的相交，优化了 节点的插入分裂算法。r + 【7 】树完全消除了m b r 的相交，减少了无效查询数，提 高了空间索引的效率。s s 树【8 】对心树进行了改进，用最小边界圆( m b c ) 代替m b r 4 浙江大学硕士学位论文第l 章绪论 表示区域的形状，提高了最邻近查询的性能，减少一半左右的存储空间。同时， s s 树改进了r 晕树的强制重插机制。当维数较高时，r 树及其变种的m b r 的相交 达到9 0 ，因此在高维情况下，性能将变得很差，甚至不如顺序扫描。x 树 9 】是 线性数组和层状r 树的结合体，通过引入超级节点，大大减少了m b r 之间的相 交，提高了查询效率。 k d 树【1 0 1 是空间划分最主要的数据结构，将查找空间不断从父节点包含的区域 分为相邻的两块区域，每块区域包含原来区域中的一半数据点。l s d “树【l l 】是针 对k d 树的变种，更加有效的改进了空间划分算法，使查询更加有效。q r 树【1 2 】 利用四叉树将空间划分成许多子空间，在各子空间内使用r 树索引，从而改良索 引空间的相交，q r 树结合了四又树与r 树的优点，是二者的综合应用。 当然还有许多基于r 树的变种，比如m 树【1 3 】，t v 树【1 4 】，s r 树【1 5 】等，主要 区别在于利用了不同的最小包围区域，从存储空间和查询性能上改进了r 树结构。 1 2 2 2 基于降维转换的方法 降维转换是另一类非常有效的高维数据相似查询方法。主要的思想是针对不 同的数据集，挑选最有代表性的一维或几维数据，构成索引数据源 1 6 1 。查询时， 首先将q 通过同样的降维算法转换到降维空间，然后查询索引获得候选结果集， 最后通过验证候选集合来获得最终的结果集。这也是过滤然后验证思想( f i l t e ra n d r e f i n e m e n t ) 的体现，能够在正确性和性能上做到有效的平衡。 这类方法以i d i s t a n c e l l 7 1 ，i m i n m a x 18 1 金字塔技术【19 】以及p 十树【2 0 】等为代表， 他们的共性在于都是把高维数据转化到单维上，然后使用b + 树来索引。 i d i 她c e 【1 7 】的方法主要是将高维数据分成很多的分区每个分区中选取一个 中心点，根据数据点与分区中心点的距离，分配数据点到离它最近的分区中。 i d i s t a n c e 【1 7 】索引的关键点在于它索引的是数据点和中心点的距离主要解决k n n 查询问题。与i d i s t a n c e 07 】不同的是，i m i n m a x i s 】为处理高维范围查询而设计，它 的设计动机是：对于一个多维的范围查询，需要为每个维度指查询范围，而满足 查询结果的高维数据点，需要在每个维度上都满足查询条件才能作为结果：因而 浙江大学硕士学伉论文第l 章绪论 对高维数据点，可以合理地选择其中的某个维度，在该维度上做该高维数据点的 索引。金字塔技术0 9 和p + 树【2 0 】足一种能够有效支持不同的查询类型( 窗口查询以 及k n n 查询) 的索引方法。与前面两种方法类似，它也是适用于映射的方法，将 高维数据映射到一维，然后使用b + 树索引。在p + 树中，首先使用基于聚类的方 法将数据空间划分成为子空间，然后对这些子空间中的数据点，使用金字塔技术 来映射并索引到b + 树上。该技术的关键在于两方面：l 、它需要映射每个子空间 到单位超立方体中，从而使得金字塔技术可以被应用；2 、把聚类中心迁移到金 字塔技术中的金字塔点从而使得金字塔技术获得很高的效率。 1 2 2 3 基于数据压缩的方法 数据压缩是另一种有效的方法，主要思想是将高维数据通过编码压缩的方式 来转换为近似向量数据，并对近似向量数据进行索引和查询，获得候选结果集， 然后通过进一步筛选查找精确结果集。数据压缩方法有效的减小了数据和索引的 存储空间，并在查询性能上得到了提高，典型的包括向量近似文件( v af i l e ) 2 1 1 ，i q 树 2 2 】等压缩方法。 向量近似文件【2 1 】将数据空间划分为2 6 个超矩形单元( 其中b 是一个可调节参 数，表示高维数据压缩后的位长) ，针对每一个维度i ，用6 ，位来表示此维值，其 中维度d = b b ，因此，每一个高维数据点都可以近似表示为长度为b 的位串，查 询时，将查询点口转换为位串，然后顺序扫描2 6 个位串，然后将查找出的候选集 合进行进一步的验证，获取结果集。向量近似文件的大小远小于原始数据集合的 大小，因此，顺序扫描文件的效率也较高。i q 树【2 2 】扩展了向量近似文件的方法， 使用树结构来对压缩后的位串进行索引，将m 树【1 3 】和向量近似文件【2 1 】的优点进 行了结合。 总得来说，基于数据压缩的方法效率受到数据分布，数据维度大小，数据集 合大小的影响，针对不同的数据集合，同一种压缩方法的查询性能相差有可能很 大，因此，需要仔细设计压缩方法来保证方法的适用率。 6 浙江大学硕士学位论文第l 章绪论 1 2 2 4 基于随机算法的方法 基于随机算法的方法只能做近似查询，但是能快速获得结果，是性能和准确 性的一个折中方法。此方法突破了传统的基于层次分区的方法的局限性，能适用 很高的维度( 一般几十维到上百维) ，使用此方法来快速进行近似k n n 查询，同 时这些近似k n n 查询都有概率保证。这类方法主要以基于局部性哈希【2 3 】，基丁二 聚类【2 4 1 ，基于排序聚集【2 5 1 ，以及基于随机抽样的方法【2 6 】等为例。 局部性哈希方法( l o c a l i t ys e n s i t i v eh a s h i n g ) 2 3 1 ，使用了一组称之为l o c a l i t y s e n s i t i v eh a s h i n g 的哈希函数，这些函数具有能够将高维相近的数据点映射到相 同的哈希值的特性。该方法有两个参数，z 和恩通过调节这两个参数，可以获 得一定精度的k n n 查询。但是该方法缺点在于参数比较难调节，而且相似查询能 达到的精度跟整个数据集中最近邻居距离有关。 基于聚类剪枝的方法1 2 4 】在预处理时从数据集合中选取一个数据点的子集，作 为剩下数据点的代表点。使用这些代表点，数据点被划分到距离最近的代表点中， 从而数据集合被划分成很多分区。查询处理的时候，选择与查询点最近的代表点， 在这些最近代表点所在的分区中查找跟查询点最近的邻居。 基于排序聚集的方法f 2 5 】是通过一些独立的“投票人来对数据集里面的数据 点来进行排序，然后通过一种高效的方法聚集所有“投票人的排序结果，称为 最后相似查询的结果。一般地，对高维数据集合，一般认为每个维度就是一个“投 票人。也就是说每个维度会先将所有的数据点以及查询点投影到一个该维度上， 接着依据投影后数据点与查询点在该维度的距离，对数据点进行排序，然后使用 聚集规则将所有维度的排序聚集，选择具有最好排序结果的数据点作为查询结 果。对欧氏空间距离公式，它能产生较为准确的近似最近邻居查询结果，在实际 中，仅仅需要访问5 的数据点就能够取得非常高的查询结果。这种方法是数据 库友好的，因为它能依靠一些预定好的顺序查询，而不是随机查询，而且不像其 他近似最近邻居查询需要额外的存储空间，该方法不需要额外的空间存储。 基于抽样的方法主要是利用随机抽样的方法做高维相似查询，在论文【2 6 】中， 作者提出了一种称为s a s h 的索引结构，通过在大量随机选择的数据点上递归创 7 浙江大学硕士学位论文第l 章绪论 建多级的随机抽样结构s a s h ，然后将剩下的数据点联系到许多个来自这些随机 抽样的数据点中。查询处理时候，首先在抽样中定位到合适的邻居，然后使用先 前定义好的连接来发现来自剩下数据集合中的最近邻居。该方法的好处在于它只 依靠两两距离的度量，而对数据的表示没有任何的要求。 1 2 2 5 基于新的度量空间的方法 此方法是从强调高维相似查询的有效性出发，基于新的相似度量公式而提出 的索引方法。这类方法一般提出了新的相似度量公式，克服了传统厶距离公式所 带来的干叶，种问题，例如随着维度的增加，数据点的最近和最远邻居距离相差变小， 导致查询的对比度变小，以及聚集所有维度的坐标差值导致部分差值较大的维度 主宰了相似度量公式中的大部分相似度。新的相似度量一般伴随新的索引技术， 这类索引以i g r i d1 2 7 】和n m a t c h1 2 8 为代表。 i g r i d 【2 7 】证明了对厶距离公式，随着维度的增加，与查询点最近和最远数据 点的距离差值会以一个很快的速度变小，从而厶距离公式的意义性值得怀疑，在 分析证明的基础上，作者提出了一个新的距离度量公式。在计算相似度时候，与 三。累加所有维度上的坐标差值来计算最后的距离不同，该公式只累加那些在相似 阈值范围内的维度坐标差，这样的度量方式能够容忍高维数据中的误差对相似计 算造成的影响，只选择那些在相似阈值范围内的维度来考虑相似性。在此基础上， 作者提出了一种与倒排索引类似的索引结构，该索引结构按照维度来组织数据， 每个维度上依据相似阈值以等深柱状图的方式来划分数据集。查询时候使用了一 个基于哈希表的方式来计算相似性。该索引方法不仅能支持高维相似查询，同时 也能支持投影范围查询( 也称为子空间范围查询) 。 n m a t c h1 2 8 针对当前高维以厶相似度计算方法的局限性：第一无法体现部分 相似性，第二两个数据点的距离经常被某些差值大的维度而影响。作者提出了两 个度量标准，包括k n m a t c h 以及频繁k - n m a t c h 。k 。n m m c h 模型将相似查询建 模为查询点和数据点在刀个维度上的匹配，这里即是一个小于数据集维度d 的整 数。而且这刀个维度是在查询过程中系统根据查询点和数据点的最佳匹配而自动 浙江大学硕十学位论文第l 章绪论 确定。在发现部分相似上，k - n - m a t c h 比易好，但是它不能发现数据点的全相似。 因为单个刀值仅仅衡量了数据点的某些属性差异而不是全部属性差异。基于此， 频繁k - n m a t c h 被提出，它通过尝试不同刀值，计算不同刀值k - n m a t c h 度量标 准下的k n n 查询，然后选择前面k 个出现最多的数据点作为最终的k n n 结果。 1 2 2 6 基于子空间相似性查询的方法 基于子空间相似性的方法是为了解决解决一种称为子空间查询的新型查询 【2 9 】。与传统相似查询在全空间范围内考虑整个搜索问题不同，子空间相似查询在 子空间中查找与查询点相似的数据点。被查询的子空间由用户给出，用户可以指 定任意的予空间作为查询对象空间。这类查询在数据挖掘中有着广泛的应用，因 为它尊重了用户的兴趣，不同用户兴趣代表不同查询子空间。论文【2 9 】提出了一个 基于多个哨兵点的方法来解决子空间相似性查询问题。 1 2 3p 2 p 系统的发展与现状 随着数据集大小不断增加，以及高效存储和检索的需求，分布式系统的研究 应运而生。p 2 p 系统作为一种网络新技术，依赖网络中参与者的计算能力和带宽， 共享网络中节点的数据和带宽，能够有效的避免单点失败问题，也保证了数据访 问的高效性和安全性【3 0 l 。 1 2 3 1 集中式p 2 p 系统 集中式p 2 p 系统是最简单的一类，类似于传统的客户端服务器形式的网络， 网络中有一个中心服务器保存节点的信息并对请求这些信息的要求做出响应，查 询时，中心服务器同时负责数据的定位和路由。同时如果节点之间互相较为熟悉， 也可以直接访问并获取数据，而不需要经过中心服务器，这是不同于c s 结构网 络的特点。b 0 1 n c t 3 l 】是较为典型的一个集中式p 2 p 系统。 这类系统的缺点就是中心服务器容易受到攻击而导致系统瘫痪，也就是常说 的单点失败问题，而且，中心服务器的访问成为了系统性能提高的一个瓶颈所在， 因此此类系统比较适合节点数较小的网络，扩展性不强。 9 浙江大学硕 ：学位论文第l 章绪论 1 2 3 2 分散式p 2 p 系统 分散式p 2 p 系统的设计是使p 2 p 系统走向成功的标志。在分散式p 2 p 系统中， 节点之间拥有平等的自主权以及责任，同时作为客户端和服务器端，没有中心服 务器和中心路由器的概念，被称为纯p 2 p 系统，能够有效的避免单点失败问题， 同时也具有可扩展性，健壮性等特征。g n u t e l l a 。f r e e n e t , c h o r d 3 2 1 c a n t 3 3 】等都属 于此类系统。 此类系统根据网络拓扑分为两类：无结构化p 2 p 系统和结构化p 2 p 系统。在 无结构化p 2 p 系统中，节点之间彼此形成无规则的网络拓扑结构，一个查询请求 需要广播到系统中所有的节点，然后由其他节点进行回答是否含有数据，优点是 节点是自治的，能够自由管理数据，而且网络之间构成的规则简单，不需要特殊 的设计，g n u t e l l a ，f r e e n e t 属于无结构化p 2 p 系统。而在结构化p 2 p 系统中，节 点之间彼此形成特定规则拓扑结构，数据按照一定的规则存储和索引f 通常根据分 布式哈希表d h t ，比如c h o r d 3 2 】1 ，因此，一个查询请求不需要泛洪整个网络， 能够快速的定位到数据所在的节点，效率非常高。但缺点在于，节点不是自治的， 不能够自由管理数据，数据都是按照一定的规则存放在网络中的节点，c h o r d 3 2 1 ， c a n t 3 3 1 属于结构化p 2 p 系统。 1 2 3 3 混合式p 2 p 系统 混合式p 2 p 系统结合了前两种系统的优点：集中式p 2 p 能够快速访问数据， 管理简单；分散式p 2 p 可扩展性强，能有效的避免单点失败问题。因此，混合式 p 2 p 系统将节点之间划分层次，将那些稳定，健壮的节点选作超级节点( s u p e rp e e r ) 用于管理数据，而将其他节点作为普通节点，存储数据，网络构成了一个层次拓 扑结构。对于在同个超级节点管理的普通节点之间互相访问效率非常高，而在 不同超级节点之间管理的节点之间访问效率较相对较低。系统的健壮性取决于超 级节点的数量和稳定度。典型的混合式p 2 p 系统包括b e s t p e e r t 3 4 1 s i m p e e r 3 s 。 p 2 p 系统还有许多挑战问题，包括系统健壮性，安全性，性能问题，路由和 1 0 浙江大学硕士学位论文第l 章绪论 资源发现，复杂查询处理，数据完整性和盗版问题，以及新的编程模型的设计等 3 0 l 。当然一个最主要的问题是如何将当前集中式环境下的各种成熟技术运用到 p 2 p 系统中，比如相似查询的各种技术，这是当前研究的一个热点问题。 1 2 4p 2 p 系统中的相似查询 p 2 p 系统的兴起与发展并不是为了某一类程序服务，因此，为了将相似查询 扩展到p 2 p 系统中，需要针对不同的网络拓扑设计新的索引结构或者其他技术， 也可以针对当前集中式环境下的优秀算法进行改进，使其能够应用到p 2 p 系统， 并保证系统的性能和可扩展性。 经过近几年的研究和发展，许多针对特定p 2 p 系统的查询算法和索引被提了 出来。首先是针对基于树的索引结构的扩展，主要有m u r k 3 6 】和v b i 树【3 7 1 这两 种方法将树结构和空间划分结合起来，将数据空间划分区域映射到不同的网络节 点，然后所有的划分区域构成一颗索引树，并利用p 2 p 系统的查询机制，保证了 树结构的维护和更新。但是由于树索引结构固有的缺点维度的增加会导致索 引查询性能急剧下降，因此，这两种方法在低维下能够很好的工作，但不能很好 的处理高维数据。 m c a n 3 8 】和m c h o r d 3 9 】的提出，有效地解决了在特定结构化p 2 p 系统中基于 度量空间的相似查询( 主要是k n n 查询) 。这两种算法发现了在集中式环境下距离 公式计算往往是查询的瓶颈问题所在，因此，算法的核心思想足将距离计算并行 到所有的节点同时计算，加快了查询处理过程。m c a n 3 8 1 底层的p 2 p 拓扑结构是 c a n e 3 3 j ，使用了一个基于哨兵的技术，将数据对象映射到一个n 维的向量空间， 而m c h o r d 3 9 基于c h o r d 3 2 】拓扑，将i d i s t a n c e 17 】降维算法应用到了结构化p 2 p 系 统中。但解决的问题和所使用的网络拓扑较为局限，不够通用。 有些应用更关注查询响应的速度，而将精确度放在了第二位，因此也有些研 究将重点放在了p 2 p 系统中的近似相似查询。l s hf o r e s t 4 0 l 主要应用在大型w e b 程序中，解决文本数据的相似查询，利用l s h 函数将高维数据映射到了不同的节 点，使查询能够快速地返回近似相似文本数据。文章【4 1 】也利用了l s h ，提出了一 浙江大学硕士学位论文第1 苹绪论 个在结构化p 2 p 系统中解决近似k n n 查询的方法。i d i s q u e 4 2 】也建立在结构化 p 2 p 系统上，利用了i d i s t a n c e 17 】和l s h 完成数据的映射转换，存储和查询。同时， 还提出了一个多重探测算法，在保证查询效率和准确性的情况下，将索引和数据 所需要的存储空间降至最低。s i m p e e rf 3 5 】解决了在超级节点p 2 p 系统中基于度量 空间的k n n 问题，利用了i d i s t a n c e 17 】将数据映射存储到普通节点，然后在超级 节点上构建数据的统计信息，查询时，利用这些统计信息来定位数据，避免了网 络的泛洪。 对于p 2 p 下的窗口查询，d i m 4 3 1 是一种在传感器网络中解决窗口查询的算 法，d i m 主要针对高维数据。建立一个二维的索引，同时对于传感器网络节点建立一 个k d 树【1 0 】索引，每个传感器是一个索引节点，查询时利用了g p s r 地理路由算 法来避免了网络的泛洪。m e r c u r y l 4 4 在此基础上提出了一个负载平衡的算法来有 效的处理窗口查询主要针对结构化p 2 p 系统做了改进使其能够支持范围查询。 d i m 的效率取决于数据的分布，针对偏移数据，d i m 不能有效的处理，因此，p o o l 4 5 】 针对此缺点进行了改进，利用结构化p 2 p 系统的信息提出了一个有效的数据存储 机制，针对不同的数据分布，能够有效的存储和查询，提高了窗口查询的效率。 这几种算法着重利用分布式网络的路由信息来支持窗口查询，更适用于结构化 p 2 p 系统中，导致了节点不能够自治管理数据等缺点。 1 2 5 存在问题 综上所述，数据库研究者在相似查询处理技术方面已经取得了许多优秀的成 果，但还是存在一些不足之处，有待进一步的深入研究。 1 、维度的诅咒问题：这是高维数据处理最本质的问题。随着数据维度的不 停增加，即使数据的选择率只有0 1 ，但足在每个单独的维度上搜索也 等同于线性扫描数据，在这种情况下，使用索引结构等的性能还不如扫 描整个数据集。 2 、数据和索引的分布式存储问题：要解决p 2 p 系统中的相似查询问题，首 先必须要解决数据和索引的分布式存储问题，当前很多的应用都足基于 1 2 浙江大学硕士学位论文 第l 章绪论 结构化p 2 p 系统，节点不能够自己管理数据，数据的存放需要按照网络 的规则存储到指定的节点，因此存在的问题足数据的分布和p 2 p 系统不 能很好的结合：理想状态下，相似的数据应该存放到同一个节点。如何 自适应的存储数据也是研究的一个重要方向。 3 ) 并行查询处理技术问题：如何有效地利用p 2 p 系统中的分布式数据和索 引，使查询处理能够并行执行，突破单机计算的瓶颈也是需要解决的一 个问题。当前的研究更多地专注于p 2 p 系统的改进，而没有专门针对特 定的应用而设计。 4 1p 2 p 系统的普适性问题：当前的研究主要着重于结构化p 2 p 系统和传感 器网络上的相似查询，而对无结构化p 2 p 系统以及混合式p 2 p 系统上的 查询研究相对较少。 1 3 本文的研究目标和内容 本文的研究目标是如何在混合式p 2 p 系统中完成相似查询，包括最主要的两 个查询类型：窗口查询和孙聃查询。通过分析研究当前的一些研究工作发现，算 法i m i n m a x 1 8 】和i d i s t a n c e 17 】在集中式环境下能够很好的处理相似查询，并且没有 维度诅咒问题的存在。因此，如何将这两个算法扩展应用到混合式p 2 p 系统中是 本文的研究重点。 本文的研究内容主要有以下几点： 1 1 分析各种p 2 p 系统的结构，然后挑选混合式p 2 p 系统作为底层p 2 p 系统， 并针对混合式p 2 p 系统的特点提出了一个相似查询的分布式框架。 2 1 扩展了i m i n m a x 1 8 l 算法到此分布式框架中，设计了构建统计信息，构建 查询树等算法，避免了网络查询的泛洪，有效的解决了窗口查询问题。 3 1 扩展了i d i s t a n c e 【1 7 1 算法到此分布式框架中，构建统计信息，并利用此信 息优化了数据访问的次数，有效的解决了k n n 查询问题。 4 、通过实验验证了算法的可行性和裁减率。 浙江大学硕士学位论文第1 章绪论 1 4 本文结构组织 本文一共分为五章，各章内容安排如下。 第一章介绍本文的研究背景和意义，综述了集中式环境下和p 2 p 系统中的相 似查询技术，分析了存在的问题，并提出了本文的研究目标和内容。 第二章详细介绍了混合式p 2 p 系统的特点，并提出了一个相似查询的分布式 框架。 第三章详细介绍了窗口查询算法的设计，着重研究了分布式查询处理技术， 并用实验验证了算法的有效性。 第四章详细介绍了k n n 查询算法的设计，着重研究了分布式查询处理技术， 并用实验验证了算法的有效性。 第五章总结本文完成的工作，并对未来的工作进行展望。 1 4 浙江大学硕士学位论文第2 章混合式p 2 p 相似查询系统总体结构设计 第2 章混合式p 2 p 相似查询系统总体结构设计 p 2 p 系统范型能有效的组织大量的数据，将数据源分布到不同的节点，本文 的研究目标是如何在混合式p 2 p 系统中完成相似查询，包括最主要的两个查询类 型：窗口查询和k n n 查询。为了完成相似查询，首先需要根据p 2 p 系统的特点 来进行查询系统的总体结构设计，保证在此总体平台上能够有效地实现各种相似 查询算法。 首先来形式化定义一下数据空间窗口查询和k n n 查询。考虑一个d 维的数 据空间，数据每个维度的值范围是 0 ，1 】，因此一个d 维的点所在的范围空间可以表 示为( 0 ，1 】，【0 ，1 】， 0 ，1 】，【o ，1 1 ) 。将一个数据点x 以及其最大最小值表示为式( 2 1 ) ： 石= ( 五，艺，) x ( 0 ，1 】1 ，【0 ，l 】： 0 ，1 l ) x m “= m a x , d _ _ l 薯 x m i a = m i n d l 公式( 2 1 ) 同时，将基于查询点g 的