（计算机软件与理论专业论文）pbasq：一种基于划分的skyline查询算法.pdf

兰州大学硕士研究生毕业论文 摘要 s k y l i n e 查询作为数据挖掘的重要分支，广泛应用于多标准决策、可视化和 用户参考查询等领域。近年来，在数据库和信息检索研究领域，有效计算s k y l i n e 的问题已经引起国内外研究者的广泛关注。现有的技术主要是对数据实行批处理 和在线处理；采用的划分方法主要为物理划分或根据分段的维值进行划分，并没 有对被划分的各部分间所固有的特性进行深入分析。 本文在数据划分方面进行了探讨。首先在n n 算法的基础上，深入分析了被 n n 点划分后各区域间的支配关系，研究了相关性质，发现并证明了被全局n n 点划分一次后，区域间具有单向的不完全支配关系；其次利用上述性质并结合可 应用于任意维空间的b n l 算法提出了一种基于划分的p b a s q 算法。该算法由 于实现了有效的过滤和减少了那些不具有支配关系区域间的支配检查，节省了内 存空间的占用，提高了执行效率。同时，该算法还具有传输s k y l i n e 结果的实时 性，当全部的s k y l i n e 点还未获得前，全局的n n 点作为第一个s k y l i n e 点可以立 刻返回给用户，并且随着时间的延长会不断返回其它s k y l i n e 点；再次提出了一 个改进算法，该改进算法利用低维空间的划分方法解决高维空间s k y l i n e 计算问 题，增加了高维空间s k y l i n e 查询的可行性；最后，进行了大量的实验验证，实 验结果表明，p b a s q 算法和改进算法是有效的。 关键词：数据挖掘，s k y l i n e 查询，划分，支配。 兰州大学硕士研究生毕业论文 a b s t r a c t s k y l i n eq u e r y , as u b - a r e ao fd a t am i n i n g , h a sv a r i o u sa p p l i c a t i o n s s u c ha s m u l t i c r i t e r i o nd e c i s i o nm a k i n g , v i s u a l i z a t i o na n du s e rp r e f e r e n c eq u e r i e s r e c e n t l y , i nd a t a b a s ea n di n f o r m a t i o nr e t r i e v a l ，t h ep r o b l e mo fh o wt oe f f i c i e n t l yc o m p u t e s k y l i n eh a sa t t r a c t e de x t e n s i v ea t t e n t i o n c u r r e n tt e c h n o l o g i e ss of a rm a i n l yf o c u so n b a t c hp r o c e s s i n ga n do n l i n ep r o c e s s i n gw h i l et h ep a r t i t i o nm e t h o d sb a s i c a l l yd e p e n d o np h y s i c a ld i v i s i o no ru s ed i m e n s i o n a lv a l u e so fs e c t i o n sa n dt h e yl a c ko fi n d e p t h a n a l y s i so ft h ei n t r i n s i cr e l a t i o n sb e t w e e n t h er e g i o n sp a r t i t i o n e d i nt h i sp a p e r , w ed e l v ei n t ot h ep r o b l e mo fd a t ap a r t i t i o n f i r s t ，o nt h eb a s i so f n n - a l g o d t h m ，w ea n a l y z et h ed o m i n a n tr e l a t i o n sb e t w e e nr e g i o n sp a r t i t i o n e db yn n p o i n ta n d ，b ys t u d y i n gt h e i rr e l a t e dp r o p e r t i e s ，w eh a v ed i s c o v e r e da n dp r o v e dt h a t t h e r ei sa l lu n i d i r e c t i o n a li n c o m p l e t ed o m i n a n tr e l a t i o nb e t w e e nt h er e g i o n so n 0 8 p a r t i t i o n e db yg l o b a ln np o i n t s e c o n d l y , w ep r o p o s eap a r t i t i o nb a s e da l g o r i t h m p b a s qw h i c he m p l o y st h ep r o p e r t i e sm e n t i o n e da n db o r r o w si d e a sf r o mb n l a l g o r i t h ma sb n l c a nb ea p p l i e di na r b i t r a r yd i m e n s i o n s b yf i l t r a t i o na n dr e d u c t i o n o ft h en u m b e ro fd o m i n a n tc h e c k i n gb e t w e e nt h o s er e g i o n so fn o n - d o m i n a t i o n , p b a s q s a v e sm e m o r yr e s o u r c e sa n di m p r o v e se x e c u t i o ne f f i c i e n c y p b a s qh a sa r e a lt i m ep r o p e r t yo ft r a n s m i t t i n gs k y l i n er e s u l t s ；t h eg l o b a ln np o i n t ，b e i n gt h ef i r s t s k y l i n ep o i n t ，i sr e t u r n e dt ou s e ri m m e d i a t e l yb e f o r eo b t a i n i n gt h ee n t i r es k y l i n e p o i n t s a n d ，a st i m eg o e so n , p b a s qr e t u r n sa l lo ft h eo t h e rs k y l i n ep o i n t s t h i r d l y , w ep r o p o s ea ni m p r o v e da l g o r i t h m t h ea l g o r i t h mb ym e a n so fap a r t i t i o nm e t h o df o r l o w - d i m e n s i o ns p a c e ，s o l v e ss k y l i n ec o m p u t a t i o n a lp r o b l e mi nh i g h - d i m e n s i o ns p a c e a n dt h u si n c r e a s e si t sf e a s i b i l i t y f i n a l l y , w ev a l i d a t eo u ra l g o m h m sw i t he x t e n s i v e e x p e r i m e n t sa n dt h er e s u l t sh a v es h o w nt h a tp b a s q a n di t si m p r o v e da l g o r i t h m sa r e e f f i c i e n t k e yw o r d s ：d a t am i n i n g , s k y l i n eq u e r i e s ，p a r t i t i o n ，d o m i n a t e 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：社 日 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：显殴丰岑导师签名： 仡f日 期： a , - o g t - 7 兰州大学硕士研究生毕业论文 1 1 研究背景 第一章引言 数据库管理系统在许多应用中被广泛使用，其中多标准决策就是关键之一。 这些应用具有以下特点： l 、针对多属性数据集，查询结果具有代表性，有时结果还互相矛盾。比如， 假设你到大连去旅游，需要找一个靠近海边并且便宜的旅馆，很显然，既便宜又 靠近海边的这两个要求是相互补足的，因为靠近海边的旅馆价格要贵一些，而价 格便宜的旅馆离海边却要远些。 2 、在上述应用中，通常没有单独的最优解。因为在上面的例子中几乎不可 能存在一个既最便宜又靠海边最近的旅馆。我们只是期望得到一个旅馆的列表， 这些旅馆离海边相对近一些，但价格又不是很贵。 3 、由于该应用的第二个特性，用户可以选择自己满意的旅馆。即，用户可 以从那些好的候选旅馆中根据个人对价格和到海边距离的意愿作最后的决定。 4 、对于相同的查询，不同的用户偏好不同，选择的结果也不相同。比如有 些人想花不多的钱靠海边近，有些人只需要旅馆最便宜，到海边乘车方便就可以 了，而还有些人只要求离海边最近，花多少钱不在乎。因此对数据库管理系统而 言，能够返回所有供用户选择的有兴趣的结果是很重要的。 传统的数据库管理系统支持这种应用是通过返回所有符合用户请求的结果 来完成的。在上面的例子中，如果用户指定旅馆价格在1 0 0 - 2 0 0 元之间，到海边 的距离在3 公里以内，系统会返回所有满足这些条件的旅馆，其实这些旅馆并不 十分有用。因为，用户从大量的旅馆信息中去做决策，太烦琐了，更重要的是可 能选择的结果并不是有兴趣的，或是完全不相关的。比如：两个旅馆a 和b ，a 和b 都满足上述条件，是系统返回的两个结果，实际上a 不但比b 便宜，而且更 靠近海边，很显然，用户对a 旅馆要比对b 旅馆更有兴趣。 为了有效的支持这些多标准决策的应用，b o r z s 如等人通过在s q l 语句中 扩展一个s k y l i n e 操作来扩充数据库系统。这个操作将从一个潜在的大的数据集 中过滤出所有的有兴趣的结果，s k y l i n e 的定义如下：给定一个d 维的数据点( 目 兰州大学硕士研究生毕业论文 标元组) 的集合，s k y l i n e 点是由所有不被其它点支配的点组成的，它也是点的 集合。一个点p = m l 】，p 2 】，“d 】) 支配另一个点q = ( q 【1 】，q 【2 】，q e d ) ，当且 仅当在所有的维上p i 】q 【i 】( 1 i d ) ，并且至少存在一个维jp 满足p j 】 提出了对数据集进行划分的思想和基本理论； 2 兰州大学硕士研究生毕业论文 证明了该理论的正确性，并给出了基于划分的算法p b a s q ； 提出了p b a s q 的一个改进算法，即：用低维空间的划分方法解决高维 空间s k y l i n e 计算； 通过实验来验证p b a s q 及改进算法的正确性及有效性； 本文深入研究了利用n n 点一次划分后各区域间所固有的特性，这对于提高 s k y li n e 计算的算法执行效率和并行查询处理具有重要意义。而且对于我们今后 处理大的数据集提供了方法和参考。 1 3 本文组织 本文共分五章，下面简要介绍一下各章的内容： 第一章阐述了课题的研究背景、主要研究工作及创新之处和组织结构； 第二章介绍了s k y l i n e 查询的相关工作，分析了传统算法的优缺点； 第三章提出了对数据集进行了划分的思想及算法，并对算法进行了改进； 第四章给出了实验和分析； 第五章是对论文研究工作的总结，以及对未来工作的展望。 兰州大学硕士研究生毕业论文 第二章相关研究工作 在这一章里，简单回顾了s k y l i n e 计算的相关工作，2 1 节里介绍了背景知识， 2 2 到2 4 节描述了s k y l i n e 计算的相关算法。 2 1 背景知识 s k y l i n e 查询作为数据挖掘的重要研究分支，广泛应用于多标准决策、用 户参考查询等领域，主要是从一个潜在的、大的数据集中找出有兴趣的点( 元组 目标) ，这些点都是不被其它点所支配的。一个点p 支配另一个点q ，如果在所 有的维上，p 好于或等于q ，但至少在一个维上要好于q 。 第一个s k y l i n e 算法 2 是k u n g 等人提出，用于求解最大向量问题，s k y l i n e 操作 1 是b o r z s o n y i 等人提出，目的是返回那些不被其它点支配的点的集合，使 用s k y l i n e 术语是因为它返回的点连成图形的一种反映 1 。 支配的概念可形式化描述为：给定一个d 维的数据集s ，a 。( 1 j 国用来表 示每一个维。刃是由所有的雄组成的维集，刃= ( a 。，a ：，a d ) 。p 和q 是s 中的两个数据点，pg q 在维a ，上的值表示为p a ， 和q a ， ，p 支配q ，如果v a 。， p a i q a ， ，3a ，p a ， 2 = 0 0 0 0 0 0 1 1 1 0 ，从1 的个数可以判断p 7 不是s k y l i n e 点，从l 的位置可以判断p 7 被 p s 和p 9 支配，所以点p 7 不是s k y l i n e 点。当判断p 8 是否是s k y l i n e 点时，b l 和b 2 位串 分别是：0 0 1 0 0 0 0 1 0 0 和0 0 0 0 0 0 0 1 1 1 ，如图2 6 中画虚框的两列。b l 八b 2 = 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 11 l = 0 0 0 0 0 0 0 1 0 0 ，结果中只有1 个1 ，所以p 8 是s k y l i n e 点。 为了获得全部的s k y l i n e 点，位图算法对数据集中每个点重复上面的操作。 2 2 4 索弓i ( i n d e xa l g o r i t h m ) 算法 给定一个d 维的数据点的集合p ，索引算法【4 】将数据集p 组织到d 个b + - t r e e 索引中。一个数据点p = ( p 【1 】，p 2 】 “d ) 被指派到第i ( 1 i d ) 个b + - t r e e 索引 中，当且仅当点p 在所有的坐标值中p 【i 】有最小的坐标值，然后对指派到索引中 兰州大学硕士研究生毕业论文 的点按在第i 个维上最小的坐标值递增的顺序排列。每一个b + - t r e e 索引的关键 字是每一个数据点的最小坐标值( 通过m i n v a l u e 表示) 。在同一个b + - t r e e 索引 中，具有相同最小值的数据点被保持在同一个批次中。 为了计算s k y l i n e 点，所有当前s k y l i n e 点坐标的最大值被保留，通过 m a x v a l u e 表示。显然，如果当前找到的s k y l i n e 点的m i n v a l u e 比s k y l i n e 列表中 s k y l i n e 点的m a x v a l u e 大于或等于，则程序终止，在b + - t r e e 索引中没有被处理 的数据点可以被安全的删除。处理每一个批次包括两步。l 、找出每一个批次的 s k y l i n e 点2 、将1 中的s k y l i n e 点和已经找到的s k y l i n e 列表中的s k y l i n e 点进行 比较，如果通过支配检查证明该点是s k y l i n e 点，则将它插入到列表中，返回给 用户。一旦发现新的s k y l i n e 点，m a x v a l u e 可能会被更新。索引算法开始时从具 有最小值的m i n v a l u e 索引开始，处理完该批次后，继续对另一个具有最小值的 m i n v a l u e 索引处理，将所有具有最小值m i n v a l u e 的索引处理完后，算法继续对 新的最小值m i n v a l u e 执行相同的操作，直到m i n v a l u e 比m a x v a l u e 大时，算法 终止。算法的执行顺序如图2 7 所示，箭头所指方向为对每个索引中每个批次进 行处理，左侧的文字标明对索引处理执行的顺序。当算法终止后，列表中找到的 s k y l i n e 点就是全部的s k y l i n e 点。 s t e p l s t e p 2 s t e p 3 s t e p 4 i n d e xli n d e x 2 m i n va l u eb a t c hm h wa l u eb a t c h 图2 7a ne x a m p l eo fi n d e xa l g o r i t h m 我们仍然考虑图2 2 a 中的例子。因为是二维数据集，所以，所有的数据点 被指派到2 个b + - t r e e 索引中，如图2 7 所示。它们的位置和顺序是按照在每一个 索引上最小值m i n v a l u e 递增的顺序进行的，由于每一个批次中，具有相同 m i n v a l u e 值的点只有一个，所以处理一个批次时，不再找批次内部的s k y l i n e 点。 索引算法执行时，依次处理m i n v a l u e = l 的批次。此时s k y l i n e 列表为空，p 3 和 p 1 0 被加入到s k y l i n e 列表中，因为p 3 和p 1 0 它们没有被当前的s k y l i n e 点支配， 兰州大学硕士研究生毕业论文 此时m a x v a l u e 被更新到9 ，相似的p 8 和p 9 在它们的批次被处理完后也被加入 到s k y l i n e 列中，此时m i n v a l u e = 2 ，m a x v a l u e = 9 ，因为正在处理的点是p 9 ，此时 最小值m i n v a l u e = - 2 ，s k y l i n e 列表中s k y l i n e 点的最大值仍然是9 ，没有变化。索 引算法按照m i n v a l u e 值递增的顺序继续对剩余的批次进行检查，p 4 、p 7 、p 6 、 p 5 和p 2 都被s k y l i n e 列表中的s k y l i n e 点支配，所以立即被删除，并没有加入到 列表中，当p 1 被处理时，m i n v a l u e - - 9 ，此时的m a x v a l u e 仍然是9 ， m i n v a l u e = m a x v a l u e ，p l 不是s k y l i n e 点，p l 即刻被删除，算法终止。本例中自 p l 后已经没有数据点，如果p 1 后仍然有数据点，则p 1 之后的数据点可以立刻 被删除，不必再进行处理。此时s k y l i n e 列表中的数据点是p 3 、p 1 0 、p 8 和p 9 。 索引算法输出s k y l i n e 列表中的数据点，即：该数据集的s k y l i n e 点为： p 3 、p l o 、 p 8 、p 9 。 2 2 5 最近邻( n e a r e s tn e i g h b o ra l g o r i t h m ) 算法 最近邻n n 算法【5 】是基于以下观察。 观察：给定一个数据集和一个单调的距离函数f ( 比如：欧几里德距离) ，到 原点的最近邻点是s k y l i n e 点。 这个观察很容易通过反证法证明。假设最近邻数据点p 不是一个s k y l i n e 点， 即p 被其它一些数据点支配，假设为p ，因此p 的每个坐标值不会大于p 的， 并且至少有一个坐标值比p 的要小，根据单调的距离函数，很容易得到p 到原点 的距离比p 到原点的距离要小，则p 是到原点的最近邻点，这和p 是到原点的最 近邻点相矛盾，因此，最近邻点属于s k y l i n e 点。 基于上面的观察，为了计算给定数据集的s k y l i n e 点，n n 算法首先找到原 点的最近邻点p ，然后用点p 划分数据空间得到三个部分。如图2 8 a 所示。 1 4 兰州大学硕士研究生毕业论文 ( a ) t h e 缸s k y l i n e p o i n t a l l t h e 蛐p 幽船 图2 8a ne x a m p l eo f n na l g o r i t h m 部分1 ：以原点为左下角，以点p 为右上角的矩形区域r 1 ，如图2 8 a 的r 1 区域。显然p 被这个区域的数据点支配，然而根据上面的观察，这部分是空的， 没有数据点落在这里，也就没有点可以支配点p 。 部分2 ：以点p 为左下角，以数据空间的右上角为右上角的区域r 4 ，所有 在这个部分的数据点被p 支配，因此这个部分不可能是s k y l i n e 点，可以被安全 的删除。 部分3 ：其它的区域r 2 和r 3 ，即灰色的区域部分。这两个区域的特性就是 局部的s k y l i n e 点属于全局的s k y l i n e 点，因为点p 并不支配这两个区域中的任何 数据点。结果，n n 算法在这两个区域上递归地应用，直到所有的数据点被处理 由 兀。 我们仍然使用图2 2 a 的数据作为例子。到原点的最近邻点p 8 被发现后，数 据空间被划分成4 个部分，r 1 、r 2 、r 3 和r 4 。按照上面的叙述，n n 算法只需 要考虑区域r 2 和r 3 ，对于p - , 2 和r 3 每一个区域，n n 算法递归的找到到它的左 下角的最近邻点，并划分它成子区域，在i b 中因为只有一个数据点p 3 ，它被返 回作为一个s k y l i n e 点，在这个区域上的搜索处理结束。相似的，在i 也区域中 如图2 8 b 所示。p 9 被发现作为l 匕区域的n n 点，并且通过p 9 将i 也区域进一 步划分成四个部分。在i 匕区域中p 1 0 作为r 2 子区域的n n 点被发现后，n n 算 法结束，并且输出所有找到的n n 点作为s k y l i n e 点。它们分别是 p 8 、p 3 、p 9 、 p 1 0 。 通常，对于多维空间( d 2 ) ，部分3 的区域会出现重叠。图2 9 显示了n n y 硷9 l 7 6 5 4 3 2 l y 阳9 s 7 6，t 3 2 l 兰州大学硕士研究生毕业论文 算法在三维空间的例子，当第一个s k y l i n e 点p 被找到后( 图2 9 a ) ，n n 算法进 一步研究部分3 的区域，如图2 9 ( b ) ( d ) 。3 个区域r a 、r b 和r c 被生成和处理。 ( a ) t h ef a s ts k y t i a ep o i n t ( b ) t h ef i r s tr e _ r i c hi ap a r t3 c j ms c c o i l d 嘶i n 叫3 俩m t h i r d 嘶缸p | r t3 图2 9n n a l g o r i t h mo n3d i m e n s i o n a ls p a c e 显然，每个区域相互重叠会导致重复搜索和重复的结果。为了消除这些重复操作 和重复的复本，n n 算法在多维空间上采取了如下方法与策略。 l a i s s e r - f a i r en n 算法保持一个全局的哈希表，用来存储已经计算过的 s k y l i n e 点，当一个s k y l i n e 点被发现后，它首先要对哈希表进行检查，如果它在 哈希表里不存在，则它被输出，并插入到哈希表里，否则它被忽略，因为它已经 被发现过了。这个方法是简单的和有效的。然而它并不能在重叠区域中消除重复 搜索。 p r o p a g a t e 一旦一个s k y l i n e 点p 被发现，通过点p 用同样的方法重新划分 区域，n n 算法检查所有的区域是否有重复区域，如果有则删除。虽然这个方法 不会将相同的s k y l i n e 点返回多次，但是每一个s k y l i n e 点p 被发现后，去重复划 分所有包含点p 的区域会导致高的计算代价。 m e r g e 这个方法的基本思想是合并一些区域，这样n n 查询的总数目就会 减少。和p r o p a g a t e 相似，这个方法也会导致很高的c p u 代价，因为去找能合 并的区域进行合并这也需要很高的代价。 f i n e - g r a i n e dp a r t i t i o n i n g 当一个s k y l i n e 点被发现后，原始的n n 算法划分 1 6 兰州大学硕士研究生毕业论文 空间到d 个区域。为了消除重叠区域，f i n e - g r a i n e dp a r t i t i o n i n g 划分方法每次 生成2 d 个非重叠区域。图2 9 a 的例子中，空间被划分成8 个区域，显然r 2 i u 属于部分3 ，结果n n 算法在这些区域上递归地调用。虽然这种方法避免了重复 搜索和复本结果，但是它会遇到这样一种情况，在一个区域里找到的s k y l i n e 点 ( 比如r 7 ) 可以被另一个区域里的s k y l i n e 点( 比如r 3 ) 支配。因此，当一个 s k y l i n e 点被发现后，它要和所有已经找到的s k y l i n e 点进行检查，以消除这种影 响。 2 2 6b b s ( b r a n c ha n db o u n ds k y l i n ea l g o r i t h m ) 算法 像n n 算法一样，b b s ( b r a n c ha n db o u n ds k y e ) 算法【6 ，7 】也是基于最近邻 搜索技术。假设数据集被一个r - t r 索引，b b s 算法不但是一个i o 最优，而且 r - t r e e 存取节点数最少。为了计算s k y l i n e 点，b b s 算法按照最好优先的方式遍 历r - t r e e ，即它一直检查和扩展在所有未访问的节点中靠近原点最近的节点。为 了完成这个目标，b b s 算法使用了一个堆( h e a p ) ，在这个堆里，每一个入1 2 ( e n t r y ) ( r - t r e e 节点或数据点) 的关键值是它到原点的最小值。在这里，一个r - t r e e 节 点到原点的最小距离被定义成它的左下角坐标的各坐标值的和。开始的时候， r - t r e e 根节点的所有孩子入口被插入到堆中，在每次迭代中，最顶的入口e 从堆 中删除，并且检查到目前为止已经找到的s k y l i n e 点。如果e 被当前的s k y l i n e 点支配，则e 被删除，否则，根据e 的类型，e 要么进行扩展，要么输出作为一 个s k y l i n e 点。如果e 是一个r - t r e e 节点，那么它通过所有不被当前s k y l i n e 点支 配的孩子入口进行扩展，将这些孩子入口扩展到堆中。如果e 是一个数据点，则 它被输出作为一个新s k y l i n e 点。当堆空时，b b s 算法结束。为了加速入口e 是 否被当前的s k y l i n e 点支配的比较，最好是当前的s k y l i n e 点在主存中用r - t r e e 来保持。 1 7 兰州大学硕士研究生毕业论文 ( a ) d a t 嬲e t x 缈) r - t v 坤 图2 10a ne x a m p l ed a t a s e ta n di t sr - t r e e 同样考虑图2 2 a 的例子，图2 1 0 a 给出了数据集，图2 1 0 b 给出了相应的 r - t r e e 。为了计算s k y l i n e ，b b s 首先插入入口e l 和e 2 到堆里，如图2 1 1 列表。 a c t i o n h e a ps k y l i n e e x p e n dq e ：i ，5 ) ，q ，咄( e 2 ，7 ) a e x i m n df 3 e x p e n de 4 e x p e n df ；2 e x p e n de 5 ( p 815 ) ，( e 4 ：6 ) ，( c 2 ，7 ) ：0 j 6 ，9 ) p o ，7 ) ，e 2 ，7 ) ? 伽6 ，9 ) ：函1 0 ：l o ) ，p r ? 1 2 ) ( e 5 ，7 ) ，( 凡19 ) ，伽1 0 ，1 ( ) ) ，扔，1 2 ) ( p 3 ，8 ，j j 6 ：9 ) ，妇l o 1 0 ) ：臼7 1 2 ) e x $ 1 m i n e 脚，p l o ? 刃 刀 2 1 8 p 8 ， p 8 ，2 ，9 p a 册? p a p s ：瑚，p 3 p l o 图2 11a ne x a m p l eo fb b sa l g o r i t h m 因为p 1 比p 2 更接近原点，所以p 1 被扩展到e 3 和p 4 ，接下来扩展p 3 ，当p 3 被 处理后，它所包含的两个数据点p 8 和p 6 被插入到堆中。之后，p 8 被处理。因 为p 8 不被任何当前的s k y l i n e 点支配( 当前s k y l i n e 点为空) ，所以p 8 输出作为 一个新的s k y l i n e 点。相似的，9 4 被扩展后，它的数据点 p 9 、p 1 0 、p 7 被插入 到堆中，堆中的先后顺序是按照到原点的最小距离由小到大排列的。当p 2 被扩 展时，它的孩子入口e 6 被一个s k y l i n e 点( p 8 ) 支配，口6 被删除。用同样的方 法，p 5 被处理后，仅数据点p 3 被插入到堆中，然后b b s 算法继续对堆里剩余的 数据点逐一检查，直到所有的数据被处理完。仅数据点p 3 和p 1 0 不被当前的 s k y l i n e 点( p s 、p 9 ) 支配，将其输出作为新的s k y l i n e 点，最终s k y l i n e 结果是 p 8 ，p 9 ，p 3 ，p 1 0 o 1 8 y 9 8 7 8 5 4 3 2 ， 兰州大学硕士研究生毕业论文 2 2 7s f s ( s o r tf i l t e rs k y l i n ea l g o r i t h m ) 算法 s f s ( s o r tf i l t e rs k y l i n e ) 算法【9 】是b n l 算法的一个改进。为了改善b n l 算法，s f s 算法对每个数据点p = ( p 【l 】，p 【2 】，p 【d 】) 提出了熵值e ( p ) 的概念。 d e ( p ) = l i l ( p 小- 1 ) l = l 其中p i 是“i 】的标准化值。显然，给定两个数据点p 和q ，p 不能支配q ，如果 e ( p ) e ( q ) 。基于这种观察，s f s 算法首先对所有的数据点按照它们的熵值升序 排列，处理完后，s f s 按照b n l 算法处理排过序的数据集。 同样使用图2 2 a 中的数据集，所有数据点相应的标准化坐标和熵值显示在 图2 1 2 的列表中。 掣 ( 6 ，8 ) p 3( 1 ，7 ) p 4( 3 ，彩 印( 7 ，6 ) p 6( 4 ，5 ) 矽( 8 4 ) p 3 ( 2 3 ) p( 5 2 ) p l o( 9 ，1 ) 1 0 6 o 6 3 o 7 3 l - 0 7 4 o 9 2 0 m o 5 9 0 7 4 图2 1 2a ne x a m p l eo fs f sa l g o r i t h m 假设窗口的大小是3 ，按照熵值排完序后，数据点的顺序是：p 8 、p 9 、p 3 、 p 4 、p 6 、p 1 0 、p 7 、p 5 、p 2 、p l 。算法执行时，三个点p 8 、p 9 和p 3 互不支配， 所以它们被插入到窗口中，此时窗口已满。接下来p 4 和p 6 被处理，两个点被删 除，因为这两个点被窗口中的候选s k y l i n e 点p 8 支配。然后p 1 0 被处理，并且被 写入临时文件中，因为它不被窗口中的任何一个候选s k y l i n e 点支配，剩下的其 它数据点被处理，并且被删除，因为它们被窗口中候选s k y l i n e 点p 8 、p 9 和p 3 支配，此时第一次迭代结束。在下一次迭代开始时，所有在窗口中的数据点被输 出作为s k y l i n e 点，因为p 8 、p 9 和p 3 的时间戳都比p 1 0 的时间戳6 小。第二次 迭代时，临时文件中只有一个数据点p l o ，s f s 在p 1 0 被处理完后终止。将两次 1 9 妙乃田田野彭筇力玲 o o o o o o o o o ， ， ， ， ， ， ， ， ， 6 l 3 7 4 8 2 5 9 o 0 o o o o o o o 兰州大学硕士研究生毕业论文 输出的s k y l i n e 点合并后，得到全部的s k y l i n e 点，它们是 p 8 、p 9 、p 3 、p 1 0 。 和b n l 算法相比，s f s 算法具有以下优势： 1 、所有的数据点间比较的次数减少了。因为具有较小熵值的数据点首先被 检查，s k y l i n e 点能够较早的被发现。因此，数据点和窗口中不是s k y l i n e 的数据 点进行比较是没有必要的，从而减少了比较次数。 2 、s f s 较b n l 算法而言是一个进步的算法。当一个数据点p 被加入到窗口 时，它被保证是一个s k y l i n e 点，这是因为所有没有被处理的数据点并不会支配 点p ，因为它们的熵值要比e 0 ) 大。即：没有( 很少有) 点可以支配比它自身熵 值小的点。 当限制窗口大小时，s f s 算法减少了比较次数，提高了算法执行效率，但是 在不限制窗口大小和数据集很大时，由于对数据集执行对数运算和排序，会消耗 很多时间，影响了整个算法的执行效率。 2 3 具有指定支配属性的s k y l i n e 计算 在 1 0 q a 已经证明，对于一个d 维且有n 个数据点的随机数据集，s k y l i n e f t i 拘 期望值是o ( 1 n d - 1n ( d 一1 ) ! ) 。当一个大的、具有很多s l 【y l i n e 点的数据集存在时， 全部的s k y l i n e 点对于决策选择可能是无益的。因此，用一些指定的支配属性来选 择数据点的问题最近已经引起人们的关注和研究【1 1 ，1 2 ，1 3 】。 2 3 1 有代表性的近似支配 k o l t u na n dp a p a d i m i t r i o u 等人 11 】提出了一个有代表性的近似支配概念a d r ( a p p r o x i m a t e l yd o m i n a t i n g r e p r e s e n t a t i v e s ) ，它是由近似支配所有数据点的最 小的数据点的集合组成。特别，给定一个d 维的数据集p 和一个e ( o ) ，a d r 的问题就是找到一个p 的子集q ，点的个数最少( 集的势最小) ，p 中的每一个数 据点p 都被( 1 一e ) q 支配，其中p p ，q q 。显然，当e = 0 时，a d r 问题就 是求解全部s k y l i n e 的i h - 题。 在二维空间中，a d r 问题可以通过贪心算法解决。假设数据点p ( p 1 1 ，p 【2 】) 按照它第一个坐标值( p 1 】) 递增的顺序排序。开始时，第一个数据点p 。被记录， 然后下面的数据点被检查，直到数据点q 被发现，满足( 1 一) q 【l 】p 。【1 】，q 2 】是 兰州大学硕士研究生毕业论文 最小的。这样点q 就被插入到a d r 中，之后，算法继续检查没有被处理的点，以 便确定下一个p 。，并满足p s 1 】 ( 1 - e ) q 【l 】，并g p “2 】最大。如果满足这样条件的 p l 存在，那么上面寻找a d r i 约过程重复，直到所有的数据点被处理完。最后，所 有在a d r 中的数据点被输出，作为结果。 而且已经证明，对于三维或更高维空间，该问题是一佃难问题。 2 3 2t o p k 频繁s k y l i n e 给定一个点的集合和一个约束条件，t o p - k 查询返回给定约束条件下的k 个 数据点。约束条件可以是一个偏好函数，也可以是一定的规则，比如：支配其它 数据点最多的k 个s k y l i n e 点等。 c h a r t 等人【1 3 】提出了一个新颖的概念“s k y l i n e 频率( s k y l i n ef r e q u e n c y ) ， 用它来界定数据点兴趣的级别。给定一个d 维的数据点的集合p ，s k y l i n e 频率用 如) 来表示，它代表当p p 是一个s k y l i n e 点时，子空间的个数。基于s k y l i n e 频率概念，t o p - k 频繁s k y l i n e 被提出。特别是t o p - k 频繁s k y l i n e 查询，就是去 寻找k 个具有最大s k y l i n e 频率值的数据点。 为了解决t o p k 频繁s k y l i n e 查询，支配子空间( d o m i n a t i n g s u b s p a c e s ) 的概 念被提出。一个子空间s 对于点p 是一个支配子空间，如果在子空间s 上存在支配 点p 的一些数据点。在s 上，维的数目被定义成点p 的支配频率( d o m i n a t i n g f r e q u e n c y ) ，很容易看n f o ) = 2 d d o ) 一1 。t o p - k 频繁s 蚴i n e 查询可以通过寻找 k 个具有最小频率的数据点来计算。 t o p k 频繁s k y l i n e 查询的基本思想是对于每个点，去确认它们的最大支配子 空间集，然后p 的支配频率被计算，最后k 个具有最小支配频率的数据点被输出作 为结果。 1 4 中还提出了寻找“k 个最具代表的s k y l i n e 查询”。其目的是返回k 个 s k y l i n e 点，保证其它数据点被这k 个s k y l i n e 点中至少一个点支配，是最大的子 集。 2 3 3k - 支配s k y l i n e 为了能从高维空间的s k y l i n e 点中寻找更重要和更有意义的s k y l i n e 点，c h a n 2 l 兰州大学硕士研究生毕业论文 等人【1 2 】缓和支配的思想到l 【- 支配上，一个点p 被说成是k 支配另一个点q ，如 果在k 个维上，点p 好于等于点q ，并且在这k 个维上至少有一个维要好于点q 。 给定一个数据集和一个整数k ，k 支配s k y l i n e 是由所有不被其它数据点k 支配 的数据点组成。在k 支配s k y l i n e 里的数据点称为k - 支配s k y l i n e 点。 【1 2 】提出了三种有效算法，即：一次扫描算法、两次扫描算法和分类检索 ( s o r t e d - r e t r i e v a l ) 算法。 2 4 其它相关研究工作 除了上面介绍的算法和研究工作外，还有许多研究者在s k y l i n e 领域做了深 入地研究。【1 6 f f = 1 1 7 针对d 维空间上有2 d 1 个非空子空间，提出了求解全部子 空间的s k y c u b e 算法。【1 7 】、【1 8 介绍了在分布式环境下计算s k y l i n e 。【2 0 】、【2 1 】 和【2 2 】介绍了在数据流上连续处理s k y l i n e 查询。更多更新的研究工作请见参考 文献。 兰州大学硕士研究生毕业论文 第三章基于划分的s k y l i n e 查询算法 基于划分的s k y l