（计算机软件与理论专业论文）skyline扩展查询研究.pdf

摘要 摘要 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 计算的各种算法及其变形；进而深入探讨和分析了为了满足人们各种不同 查询需求而提出的多种s k y l i n e 查询方案，包括子空间上的s k y l i n e 查询、动态s k y l i n e 查 询、k 支配s k y l i n e 查询和约束s k y l i n e 查询等；最后详细分析了在不同应用环境下例 女l j w e b 信息系统、数据流环境、微观经济学等中的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 查询问题。 以往相关的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 扩展查询方案，然后为这 些扩展查询设计了基于共享计算思想的批处理高效算法，最后用一系列实验证明了 这些算法的有效性。 s k y l i d 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 有多远? 我们提出了一 种新颖的度量：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 计算方法来获 得解决方案。我们设计了三个有效计算s k y l i n e 距离的算法。首先基于对数据和问题 的直观观察，设计了动态规划算法；其次基于若干的理论证明，提出一个排序一投影 算法，算法递归地将高维空间分解为多个低维空间，降低了计算难度；然后基于空 间划分思想设计和实现了一个能高效裁剪搜索空间的空间划分算法；最后通过理论 和实验证明了以上算法的有效性。 多目标决策问题的应用场景往往是交互式的，用户需要对数据集进行不断的探 查，因此要求系统具有较高的响应速度，但目前数据在往海量化、高维化的方向 第i 页 中山大学博士学位论文 发展，单机算法常常不能达到实际应用的要求。随着并行计算环境越来越普遍，扩 展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 查询算法，利用了z o r d e r 地址的单调顺序性和聚集性来提高分布 式系统中的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 距离；负载均衡 第i i 页 a b s t r a c t a b s t r a c t s k y l i n ei st h ep o i n t st h a ta r en o td o m i n a t e db ya n yo t h e rp o i n t si nt h eg i v e nd a t a s e t t h e s o - c a l l e dd o m i n a n to p e r a t i o ni nt h ed a t a s e tm e a n sad a t ao b j e c ti sn o tw o r s et h a na n o t h e rd a t a o b j e c to ne v e r yd i m e n s i o na n db e t t e rt h a ni to na tl e a s to n ed i m e n s i o n t h eg o o d n e s so rb a d n e s s o fad i m e n s i o nh a sn ou n i f o r md e f i n i t i o n s i tc a nb ed e c i d e db yu s e r s p r e f e r e n c e s ，e x p e r i e n c ea n d k n o w l e d g e t h es k y l i n eo p e r a t o ra n di t se f f i c i e n tc o m p u t a t i o nh a v er e c e i v e dal o to fa t t e n t i o ni n t h ed a t a b a s ec o m m u n i t ym a i n l yd u et ot h ei m p o r t a n c eo fs k y l i n ec o m p u t a t i o ni nm u l t i - c r i t e r i a d e c i s i o nm a k i n ga p p l i c a t i o n sa n dp r e f e r e n c e - b a s e dq u e r ya n s w e r i n g f i r s t l y , a sag o o db e g i n n i n ga n dan e c e s s a r yb a s eo fr e s e a r c h ，w eg i v ear e v i e wo ft h ec u r r e n t s t u d i e so fs k y l i n eq u e r y ac o m p r e h e n s i v ea n a l y s i so fv a r i o u sa l g o r i t h m sa n dt h e i rd e f o r m a t i o n i nas t a t i ca n dc e n t r a l i z e de n v i r o n m e n ti sg i v e n m o s to ft h ep r e v i o u sw o r kf o c u s e so nc o m p u t i n g t h es k y l i n ee f f i c i e n t l yb yi n d e x i n gs t r u c t u r eo rc o d i n gt e c h n i q u e s n e x t ，w ea l s od i s c u s sav a r i e t y o fs k y l i n ee x t e n s i o nq u e r i e si nd e p t h ，w h i c ha i ma ts a t i s f y i n gp e o p l e sv a r i o u sd e m a n d s s k y - l i n ee x t e n s i o nq u e r i e si n c l u d et h es u b s p a c es k y l i n eq u e r y , d y n a m i cs k y l i n eq u e r y , k d o m i n a n c e q u e r i e sa n dc o n s t r a i n e ds k y l i n eq u e r y , e t c f i n a l l y , w es t u d i e ds k y l i n ec o m p u t a t i o ni nd i f f e r e n t a p p l i c a t i o ne n v i r o n m e n t si nd e t a i l ss u c ha sw e b i n f o r m a t i o ns y s t e m s ，d a t as t r e a me n v i r o n m e n t ， m i c r o - e c o n o m i c s ，e t c o u rr e s e a r c hi n c l u d e st h r e et o p i c s ：t h em u t u a ls k y l i n er e c o m m e n d a t i o np r o b l e m ，t h es k y l i n e d i s t a n c ep r o b l e ma n dt h ep r o g r e s s i v es k y l i n ei nl o a db a l a n c i n gd i s t r i b u t e ds y s t e mp r o b l e m e x i s t i n gs t u d i e sf o c u so nc o m p u t i n gt h es k y l i n e ( s ) f o rag i v e nd a t as e ti ne i t h e rt h ef u l ls p a c e o rs u b s p a c e s i nr e a la p p l i c a t i o n sw h e ns e l e c t i o n si n v o l v em o r et h a no n ep a r t y , s k y l i n ea n a l y s i sc a n b em u c hm o r ec o m p l i c a t e d ，s u c ha sh o m e o w n e r sa n dr e n t e r s ，a u c t i o n ，m e r g e r sa n da c q u i s i t i o n s ， e t c b o t hs i d e sh o p et oa c h i e v et h eb e s tm a t c hu n d e rc e r t m nc o n s t r a i n si nt h e s es c e n a r i o s t h i s p a p e rs t u d i e sap r a c t i c a la n dn o v e lp r o b l e mo fm a k i n gr e c o m m e n d a t i o n sb e t w e e nt w op a r t i e ss u c h a sa p p l i c a n t sa n dj o bp o s i t i o n s w em o d e lt h ec o m p e t e n tc h o i c e so fe a c hp a r t yu s i n gs k y l i n e s i n o r d e rt om a k er e c o m m e n d a t i o n si nv a r i o u ss c e n a r i o s ，w ep r o p o s eas e r i e so fs k y l i n ev i e wq u e r i e s t om a k er e c o m m e n d a t i o n s ，w eo f t e nn e e dt oa n s w e rs k y l i n ev i e wq u e r i e sf o rm a n ye n t r i e s ( e g ， m a n ya p p l i c a n t sv e r s u sm a n yj o b s ) i no n eo rt w op a r t i e si nb a t c h h o w e v e r ，t h ee x i s t i n gs k y l i n e c o m p u t a t i o na l g o r i t h m sf o c u so na n s w e r i n gas i n g l es k y l i n eq u e r ya tat i m e ，a n dd on o tc o n s i d e r s h a r i n gc o m p u t a t i o nw h e na n s w e r i n gs k y l i n ev i e wq u e r i e sf o ra l lm e m b e r si no n ep a r t yo rb o t h p a r t i e s t ot a c k l et h eb a t c hr e c o m m e n d a t i o np r o b l e m ，w ed e v e l o ps e v e r a le f f i c i e n ta l g o r i t h m st o p r o c e s ss k y l i n ev i e wq u e r i e si nb a t c h t h ee x p e r i m e n tr e s u l t sd e m o n s t r a t et h a to u ra l g o r i t h m s s i g n i f i c a n t l yo u t p e r f o r mt h es t a t e - o f - t h e - a r tm e t h o d s s k y l i n eh a sb e e nw i d e l yr e c o g n i z e da sb e i n gu s e f u lf o rm u l t i c r i t e r i ad e c i s i o nm a k i n ga p p l i - c a t i o n s w h i l em o s to ft h ee x i s t i n gw o r kc o m p u t e ss k y l i n e si nv a r i o u sc o n t e x t s ，i nt h i sp a p e rw e c o n s i d e ran o v e lp r o b l e m ：h o wf a ra w a yap o i n ti sf r o mt h es k y l i n e ? w ep r o p o s ean o v e ln o t i o n o fs k y l i n ed i s t a n c ew h i c hm e a s u r e st h em i n i m u mc o s to fu p g r a d i n gap o i n tt ot h es k y l i n eg i v e n 第i i i 页 中山大学博士学位论文 ac o s tf u n c t i o n s k y l i n ed i s t a n c ec a nb er e g a r d e da sam e a s u r eo fm u l t i d i m e n s i o n a lc o m p e t e n c e ， a n dc a nb eu s e dt or a n kp o s s i b l ec h o i c e si nr e c o m m e n d a t i o ns y s t e m s c o m p u t i n gs k y l i n ed i s t a n c e s e f f i c i e n t l yi sf a rf r o mt r i v i a la n dc a n n o tb eh a n d l e db ya n ys t r a i g h t f o r w a r de x t e n s i o no ft h ee x i s t i n g s k y l i n ec o m p u t a t i o nm e t h o d s t ot a c k l et h i sp r o b l e m ，w es y s t e m a t i c a l l ye x p l o r es e v e r a ld i r e c t i o n s w ef i r s tp r e s e n tad y n a m i cp r o g r a m m i n gm e t h o d t h e n ，w ei n v e s t i g a t et h eb o u n d a r yo fs k y l i n e s a n dd e v e l o pas o r t p r o j e c t i o nm e t h o dw h i c hu t i l i z e st h es k y l i n eb o u n d a r yi nc a l c u l a t i n gs k y l i n e d i s t a n c e s l a s t ，w ed e v e l o pas p a c ep a r t i t i o n i n gm e t h o dt op r u n et h es e a r c hs p a c ee f f i c i e n t l y w e r e p o r te x t e n s i v ee x p e r i m e n tr e s u l t sw h i c hs h o wt h a to u rm e t h o d sa r ee f f i c i e n ta n ds c a l a b l e t h ea p p l i c a t i o n so fs k y l i n eq u e r yi nr e a lw o r l do f t e nr e q u i r er a p i dr e s p o n s et i m et os a t i s f y c u s t o m e r s b u ti nm a s s i v ea n dh i g hd i m e n s i o n a ld a t ac i r c u m s t a n c e s ，a l g o r i t h m sd e s i g n e df o r s i n g l ep r o c e s s o ro f t e nc a n n o tr e a c ht h ea c t u a ld e m a n d w i t ht h ei n c r e a s i n g l yd e v e l o p m e n to f p a r a l l e lc o m p u t i n ge n v i r o n m e n t ，p a r a l l e ls k y l i n eq u e r yp r o c e s s i n gc a ns i g n i f i c a n t l yr e d u c et h e q u e r yr e s p o n s et i m ea n di m p r o v et h ef l e x i b i l i t ya n de f f e c t i v e n e s so ft h eo v e r a l ls y s t e m m o s t o fp r e v i o u ss t u d i e sf o c u so nh o wt or e d u c ec o m m u n i c a t i o nc o s tac o m p l e xn e t w o r ke n v i r o n m e n t ， w h i l ei g n o r ec o n s i d e r i n gh o wt oi m p r o v es k y l i n ec o m p u t i n gp e r f o r m a n c ei nl a n o rm u l t i - p r o c e s s o r c l u s t e rw i t hh i g h - b a n d w i d t h i nt h i sp a p e r w es t u d yt h ep r o b l e mo fp r o g r e s s i v ea n dl o a db a l a n c i n g d i s t r i b u t e ds k y l i n ea n a l y s i s al o a db a l a n c i n gp a r a l l e ls k y l i n eq u e r ya l g o r i t h mf o rm u l t i - p r o c e s s o r c l u s t e r so rh i g h s p e e dn e t w o r ke n v i r o n m e n ti sp r e s e n t o u ra l g o r i t h mu t i l i z e st h em o n o t o n i c o r d e r i n ga n dc l u s t e r i n gp r o p e r t i e so fz - o r d e rt od e c r e a s ed o m i n a n c et e s t sa n ds i g n i f i c a n t l ys h o r t e n s t h er e s p o n s et i m eb yp e r f o r m i n gp a r a l l e lp r o c e s s i n go v e rm u l t i p l ep r o c e s s o r s i ti sa l s op r o v e dt h a t o u ra l g o r i t h mi sc o n v e r g e n t e x t e n s i v ee x p e r i m e n t sh a v eb e e nc o n d u c t e dt od e m o n s t r a t et h e f e a s i b i l i t ya n de f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h mi nd i f f e r e n td a t ad i s t r i b u t i o n k e yw o r d s ：s k y l i n eq u e r y ；m u t u a ls k y l i n e ；s k y l i n ed i s t a n c e ；l o a db a l a n c i n g 第i v 页 表目录 表目录 2 1 图2 1 中数据的位图1 0 2 2 一个4 维的数据集1 4 2 3 七一支配关系中的循环支配1 9 2 4 各静态算法对s k y l i n e 扩展的支持2 1 3 1 一组求职者2 6 3 。2 一组工作职位2 6 3 3 表3 1 和表3 2 中8 种s k y l i n ev i e 碴询的结果4 1 3 4 实验参数4 2 4 1 动态规划法的例子5 3 5 1 一个2 维数据空间中的数据集及对应的z - o r d e r 地址7 2 5 2n b a 数据集上的性能比较7 7 5 3 数据集大小设置7 8 5 4 参数设置7 8 第1 0 5 页 图目录 图目录 n a s s a u 海滩酒店的s k y l i n e 广州城市天际线局部 s k y l i n e 计算的一般流程 2 t 数据空间中的支配关系和s k y l i n e 集合 d g c 算法中的多路归并方案 算法对图2 1 中数据空间的划分 算法对3 维数据空间的划分 b b s y f 法运行的某个时刻 4 维数据空间中不同子空间s k y l i n e 表2 2 中数据集完整的s k y c u b 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 集 图2 1 数据集中的k s k y b a n d ( k = 3 ) 。 约束s k y l i n e 查询 层次结构示例( 值越大越好) 3 2 i n v e r s es k y 如n e 区域的例子3 5 8 种s k y l i n ev i e w 查询的关系4 0 e 舵c to fc a r d i n a l i t y 4 3 e 舶c to f d i m e n s i o n a l i t y 4 3 e 髓c to f v i e ws i z e 4 3 e f f e c to fv i e wo v e r l a p 4 4 e f f e c to fc a r d i n a l i t y 4 4 e f f e c to f d i m e n s i o n a l i t y 。1 4 e f r e c to f v i e ws i z e 4 5 e f f b c to f v i e wo v e r l a p 4 5 酒店的例子4 7 2 维空间中的动态规划法5 3 3 维空间的例子( 注意坐标是反方向的) 5 4 图4 3 的2 d 投影5 8 空间划分法的例子6 0 局部最优点的个数6 3 三个算法的比较6 4 空间划分法的裁剪能力6 5 第1 0 7 页 1 2 3 8 0 2 2 3 5 5 7 8 9 1 2 3 8加地挖埒”玛均殂 l 2 3 1 2 3 4 5 6 7 8 9 1 1 1 2 3 4 5 6 7 8 9 1 1 1 2 3 4 5 6 7 8 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 中山大学博士学位论文 4 9 4 1 0 4 1 1 4 1 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 1 0 5 1 l 5 1 2 5 1 3 5 1 4 5 1 5 5 1 6 5 1 7 5 1 8 5 1 9 5 2 0 5 2 1 5 2 2 5 2 3 5 2 4 3 维数据空间中的局部最优点 空间划分法中参数l i m i t 的作用 高基数下的空间划分法 n b a 数据集上的实验结果 一个2 维空间中的z o r d e r 曲线 例5 2 的z - o r d e r 曲线 不同维度上的响应时间( 每节h ix1 0 7 个数据1 不同维度上的响应时间( 每节点2x1 0 t 个数据) 不同维度上的响应时间( 每节点3 1 0 7 个数据) 不同维度上的响应时间( 每节点4 1 0 7 个数据) 不同维度上的响应时间( 每节点5x1 0 7 个数据1 不同数据规模下的响应时间( d = 2 、 不同数据规模下的响应时间( d = 3 ) 不同数据规模下的响应时i 盲- j ( d = 4 ) 不同数据规模下的响应时间( d = 5 ) 不同维度下的均值m e a n 不同维度下的标准差s t d e v 不同数据分布下的均值m e a n 不同数据分布下的标准差s t d e v 不同数据规模下的均值m e a n 不同数据规模下的标准差s t d e v l b p s 响应时间的加速度 负载均衡 通信量( 每节点1x1 0 7 个数据) 通信量( 每节点2x1 0 7 个数据) 通信量( 每节点3x1 0 7 个数据) 通信量( 每节点4 1 0 7 个数据) 通信量( 每节点5 1 0 7 个数据) 第1 0 8 页 ：g 宕 宕 g 符他循阳约阳舳缸乩跎跎s8韶阻阻雅踮踮8；8盯盯 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：洳f ，6 年锄细 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有 权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保 存学位论文。 保密论文保密期满 学位论文作者签名日期：珈f 年月日 导师张压坚一慨b 卜年 5 0 ) 两个集合，要求在两个 不同的价格范围内进行s k y l i n e 查询以提供给用户更多的选择。 例12 形象地说明了s k y h n e 查询名称的由来。 倒1 , 2 图j2 给出了广州_ 喊市踟“耻( 天际线，也称寿城市轮廓) 的局部。在囤中我们能看到 的建筑物要2 高度比其他建筑物高，要幺离据影点比较近。换而言之，在“高度”和“离摄影点 距离”两个堆度上不被其他建筑精支配的建筑斩就椅成t 广州的无际线。 目12r h 城市 镕a 自* 由于s k y l i n e 查询计算在数据仓库、推荐应用，电子商务多标准决策中的良好应用前景，使 其成为当前数据库界研宄的热点之一，受到了学术界和工业界的广泛关注。从2 0 0 1 年至今，数 第2 页 第一章绪论 据库领域相关的高水平国际会议p o d s 、v l d b 、s i g m o d 、i c d e 、i c d m 上发表了许多高质 量的论文，呈现出了大量的研究成果，国际学术期刊a c mt r a n s a c t i o n so nd a t a b a s es y s t e m ( t o d s ) 、i e e et r a n s a c t i o n so nk n o w l e d g ea n dd a t ae n g i n e e r i n g ( t k d e ) 、a c mt r a n s a c t i o n s o nk n o w l e d g ed i s c o v e r yf r o md a t a ( t k d d ) 陆续也发表了这方面的文章。 1 2研究现状与面临的挑战 s k y l i n e 查询是一个典型的多目标优化问题【2 1 ，应用范围相当广泛，包括数据仓库、个性化 推荐、数据库可视化、城市导航系统等等，是近年来数据库技术领域的一个研究重点和热点，在 国际会议和期刊涌现出很多的相关论文。本小节先给出一个现有研究成果的概览和分类，具体 的研究综述在下一章展开。 首先，目前在集中静态环境下利用空间索引或编码技术快速进行s k y l i n e 计算的研究已比较 成熟【3 ，4 】，涌现了如b n l ，d d c ，b i t m a p ，i n d e x ，b b s ，l 后粥等算法。这类算法通常只关注 于如何快速回答在单个静态数据集上的s k y l i n e 简单查询。 s k y l i n e 查询算法流程通常如图1 3 所示【5 】。 图1 3s 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 查询问题。而随着空间维 度的增长，不仅使得s k y l i n e 计算更加困难，还导致s k y l i n e 点的数目大大增加，从而无法为用户 作出决策提供准确、直观的依据，为了解决这个问题，提出了k 支配查询、基于评分的s k y l i n e 查 询、计数s k y l i n e 查询、t o p - k 支配查询、七一s k y b a n d 查询、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 计算方案的改进。针对w | e b 信息系统中资源分布相对独立的情况，b a l k e 等首次对分布式 第3 页 中山大学博士学位论文 环境下的s k y l i n e 计算进行了研究；b i nc u i 等提出一个基于水平划分的分布式s k y l i n e 算法一p a d s k y l i n e ；有的文献还将分布式s k y l i n e 算法扩展到p 2 p 网络；在数据流研究领域里，也出现了多 篇论文讨论s k y l i n e 在数据流环境下的应用：c u i p i n gl i 等探讨 s k y l i n e 查询在微观经济学中的 应用；h u a n g 等提出了在移动对象情形下的持续的s k y l i n e 查询问题； 还有一些学者开始探讨具体应用数据库环境下的s k y l i n e 实现和语义。s k y l i n e 查询的其他应 用还包括中间件环境、空间数据库、隐私保护、图像数据库、时间序列数据库、x m l 数据库等 等。 本文研究的出发点主要来源于已有s k y l i n e 研究中几个尚未解决的新问题。目前已有s k y l i n e 查 询研究： 1 ) 只能处理单个数据集单方查询； 2 ) 只关注如何计算数据集中的s k y l i n e 点集，而忽视大部分非s k y l i n e 数据点需求： 3 ) 缺乏在高带宽分布式环境下计算大规模数据中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 查询算法还需要考虑：响应速度、渐进性、可扩展性、可 维护和稳定性等等。这些都是现实且困难的研究课题。 1 3本文工作 本文工作主要集中在s k y l i n e 查询问题中的三个扩展查询研究，分别是双方决策5 b 的s k y l i n e 推 荐问题，s k y l i n e g i 离问题以及负载均衡的分布式s k y l i n e 查询问题。 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 查询、动态s k y l i n e 查询、k 一支配查询 和约束s k y l i n e 查询等；最后，详细研究了在不同应用环境下例如w e b 信息系统、数据流环境、 微观经济学等中的s k y l i n e 计算改进方案。 2 ) 双方决策中的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 为决策双方的竞争性选择进行了建模，我们首先 为用户可能提出的多种需求定义了