（计算机软件与理论专业论文）基于索引的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 计算问题，查询数据集上8 k y l i n e 点输出数目过多的 问题以及分类属性数据集上如何高效、动态地算出其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 的方法：c s k y ( c o u n tt h es k y l i n e ) ，该算法充 分利用了一个新颖的数据结构一i n v e r t s 结构的特性。i n v e r t s 特性之一是， 通过对目标数据集进行排序，存放最可能为s k y l i n e 点的数据于被优先扫描 的位置，使得c s k y 能够高效、渐进地计算出子空间上的s k y l i n e ；同时。该 结构的特点还在于，计算目标数据集中任意子空间上的s k y l i n e 都可以通过 中文摘要 至多扫描一遍该索引结构来完成。这样，c s k y 算法不仅拥有其他基于索引 的s k y l i n e 算法在计算固定数据集 = s k y l i n e 时的高效，且使这种高效为所有 子空间共享。另外，本文扩展了c s k y 算法以用来解决高维数据集上其他变 异s k y l i n e 查询。 2 本文针对高维数据集 ：s k y l i n e ) 艮寸通常过大这个较普遍的问题，提出了抽样 计算s k y l i n e 的算法：s s k y ( s a m p l et h es 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 n v e r t s 结构，s s k y 计算查询数据集上所有子空间 的最大平和点仅需线性于数据集势的复杂度，为o ( k n + k 2 ) ( 礼) ，文 中论证了该结果。这表明s s k y 计算抽样s k y l i n e 时，时间开销相当小。同时， 理论分析和实验结果更进一步说明，s s b 计算所得抽样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 计算问题。为此，我们先论证了 分类属性集与格结构的对应关系。利用该对应关系，本文提出了一个基于 格的l b s ( l a t t i c e - b a s e ds k y l i n ea l g o r i t h m ) 算法来高效处理分类属性数据集上 的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 计算 问题转化为对调整格进行遍历的过程。此外，本文论证了对分类属性数据 集对应格进行遍历，所需时间、空间复杂度分别为o ( u 2 “) 和0 ( 掣4 - n ) ，其 中n ，k ，“分别表示数据集的势、维度及编码所有维上相异元所需的最少比 特数。据我们所知，该结果远优于直接使用现有s k y l i n e 算法对分类属性数据 集进行s k y l i n e i = t 算的性能。 综上所述，本文基= j = i n v e r t s 、格等结构，针对s k y l i n e 计算中存在的三类问 题，分别给出了从概念定义、数据结构构建至u s k y l i n e 算法提出这一系列过程组成 中文摘要 的解决方案。所提出的高维数据集上高效s k y l i n e 算法c s l 【y 以及抽样s k y l i n e 计算方 法s s l ( ! l ，是对高维数据集上s k y l i n e 计算技术的有益补充 基于格结构的l b s 算法解 决了本文在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 ，分类属性 分类号：t p 3 1 1 a b s t r a c t t h ea d v a n c eo ft e c h n o l o g yh a sm a d ed a mc o l l e c t i o ne a s i e ra n df a s t e r t h u s c a u s i n gm a n ya p p l i c a t i o n si n v o l v e di nm a s sm e m o r y b a s e do nt h e s ef a c t s ，an e w o p e r a t o r ，w h i c hw a sa l w a y ss e e na sm e m o r y - b a s e dm e t h o db e f o r e ，h a db e e ni n t r o - d u c e di n t od a t a b a s ef i e l ds i n c e2 0 0 1 t h eo p e r a t o r ，c a l l e df o r ”s k y l i n e ”o p e r a t o r ， a i m st of i n dt 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 ti nt h ed a t a s e t a p o i n td o m i n a t e sa n o t h e rp o i n ti fi ti s 勰g o o do rb e t t e ri na l ld i m e n s i o n sa n db e t t e r i na tl e a s to n ed i m e n s i o n w h a ti sg o o do rb a di sn o ts t r i c t l yd e f i n e d a n dt o t a l l y d e p e n d so nt h eu s e rp r e f e r e n c e b a s e do nt h ed e f i n i t i o na b o v e ，t h es k y l i n eo p e r a t o rc a nd r a wap i c t u r eo ft h e o b j e c td a t a b a s e ，a n dh e l pt h eu 8 e f st of i n dt h ei n t e r e s t i n go b j e c t s u n f o r t u n a t e l y ， t h eo b v i o u sd i f f e r e n c e ，b e t w e e nt h ed e f i n i t i o n so ft h es k y l i n eo p e r a t o ra n dt h o s ei n t r a d i t i o n a lq u e r yl a n g u a g e s ，m a k e si tn e c e s s a r yt od e v e l o pa l lk i n d so fn e wa l g o - r i t h m st oi m p l e m e n tt h eo p e r a t o r r e c e n t l y , s k y l i n ec o m p u t i n gh a sb e e nb e c o m i n g ah o tt o p i cd u et oi t sp o t e n t i a la p p l i c a t i o n si nm a n ys c e n a r i o s ，i n c l u d i n gt r a d i t i o n a l d a t a b a s e ，d i s t r i b u t e dd a t a b a s e ，d a t as t r e a ma n de v e nt h ec a t e g o r i a ld a t a b a s ea n d s oo n b o t ht h ea c a d e m i ca n dt h ei n d u s t r i a lh a v ep a i dm u c ha t t e n t i o nt oi t i nt h i st h e s i s ，w ef o c u sm a i n l yo ne x p l o r i n gi n d e x - b a s e ds k y l i n ea l g o r i t h m s t a k i n gf u l lu 跎o fi n d e x i n gt e c h n o l o g y w es t u d ys k y u n ec o m p u t i n gi na n ys u b s p a c e o fh i g hd i m e n s i o n a ld a t a s e t t h ep r o b l e mo fs a m p l i n gt h el a r g e - s i z es k y l i n ea n d s k y l i n ec o m p u t i n gi nc a t e g o r i a ld a t a b a s e t h ec o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： 1 i nt h i st h e s i s ，w ep r o p o s ean e ws k y l i n ea l g o r i t h m ，c a l l e dc s k y ( c o u n tt h e s k y l i n e ) ，w h i c hc a ne f f i c i e n t l ye v a l u a t et h es k y l i n ei na n ys u b s e to fh i g hd i - m e n s i o n a ld a t a s e t ，a f t e rc o n s i d e r i n gt h ed i f f i c u l t i e sa n ds u r v e y i n gt h ee x i s t i n g s k y l i n ea l g o r i t h m s t h ed i f f i c u l t i e sa x et h a t ，i no n eh a n d ，t h eo t h e ri n d e x - b a s e ds k y l i n ea l g o r i t h m sc a nn o to rc a nn o te f f i c i e n t l ye v a l u a t et h es k y l i n ei n a n ys u b s e to ft h eh i g hd i m e n s i o n a ls p a c e ；i i lt h eo t h e rh a n d t h en o n - i n d e x e d x s k y l i n ea l g o r i t h m sc 锄d oi t b u ti ti sv e r yi n e 丘i c i e n t b a s e do nt h e s ef a c t s ， c s k ym a k e sf u l la d v a n t a g eo ft h ec h a r a c t e r i s t i c so fan o v e ld a t as t r u c t u r e ， c a l l e di n v e r t s 0 n eo ft h e mi st os o r tt h ea t t r i b u t ev a l u e si ne a c hd i m e n s i o n a n dp u t st h em o s tp o s s i b l es k y l i n ep o i n t st ot h ef i r s t l ys c a n n e dp l a c e s ，t h u s a s s u r i n gt h a tc s k yc a nr e t u r nt h es k y l i n ep o i n t s ，p r o g r e s s i v e l ya n de f f e c t i v e l y a tt h es a n l et i m e ，a n o t h e rc h a r a c t e r i s t i co fi n v e r t si st h a t ，t h es k y l i n eo fa n y s n b 6 e ti nh i g hd i m e n s i o n a ls p a c ec a nb ef o u n db ys c a n n i n gt h ei n v e r t ss t r u c - t u r ea tm o s to n ep a s s t h e r e f o r e ，c s k yc a nn o to n l ye f f i c i e n t l yf i n dt h es k y l i n e l i k eo t h e ri n d e x - b a s e da l g o r i t h m s b u ta l s od oi ti na n ys u b s e to ft h ew h o l e q u e r ys p a c e i na d d i t i o n ，w ee x t e n dc s k ya l g o r i t h mt op r o c e s st h ev a r i a n t s o fs k y l i n ec o m p u t i n g 2 w ed e v e l o pa na l g o r i t h mt os a m p l et h es k y l i n eo fh i g hd i m e n s i o n a ld a t a s e t c a l l e ds s k y ( s a m p l et h es 幻l i n e ) ，i no r d e rt op r e v e n tt o ol a r g e - s i z es k y l i n e p u z z l i n gt h eu s e r s c o n s e q u e n t l y , an e wc o n c e p t ，c a l l e df o rm i l dp o i n t ss e t ，i s i n t r o d u c e di nt h i st h e s i s ，i tc o n s i s t so ft h o s ep o i n t s ，w h i c hm i n i m a l8 c o r e 8i n a l ld i m e n s i o n sa r et h em o s ta m o n ga l lt h ep o i n t so fad n t a s e t a n dt h e n ，w e p r o v et h ec o i n c i d e n c er e l a t i o nb e t w e e no n es k y l i n ep o i n to fh i g hd i m e n s i o n a l s p a c ea n dt h em o s tm i l dp o i n t so fo n es u b s e t ，t h u se n a b l i n gi tt ot r a n s f o r m 8 k y l i n ec o m p u t i n gi nh i g hd i m e n s i o n a ls p a c et of i g u r i n go u tt h em o s tm i l d p o i n t si na l ls u b s e t s t h el a t t e rc o s t st h el i n e a rt i m ei nt h ec a r d i n a l i t yo ft h a t h i g hd i m e n s i o n a ld a t a s e tf o rf i x e dd i m e n s i o n a l i t yk w i t ht h ee x a c tc o m p l e x i t y o ( k n + k 2 ) ( 后 n ) ，w ep r o v et h ea b o v ec o n c l u s i o ni nt h e o r y f u r t h e r m o r e ， w ed e m o n s t r a t et h a tt h es a m p l es k y l i n e ，r e t u r n e df r o ms s k y , i sf a i r l ys i m i l a r t ot h eo r i g i ns k y l i n e 3 i nt h i st h e s i s ，w es t u d yt h ee v a l u a t i o no ft w ok i n d so fs k y l i n eq u e r i e si nc a r e - g o r i a ld a t a b a s e ：t h es t a t i ca n dt h ed y n a m i cs k y l i n ec o m p u t i n g o n eo ft h e m i st h en o r m a l - m e a n i n g ( a l s oc a l l e ds t a t i cs k y l i n ec o m p u t i n g ) s k y l i n eq u e r y t o c o n q u e ri t ，w ef i r s tp r o v eo n et oo n ec o r r e s p o n d e n c eb e t w e e no n ec a t e g o r i a l d a t a s e ta n do n el a t t i c es t r u c t u r e b a s e do nt h ec o r r e s p o n d e n c e ，w ec a nm a p t h ed a t ai nq u e r yd a t a b a s et ot h ep o i n t so ft h el a t t i c es t r u c t u r e ，t h u st r a n s - f o r m i n gs k y l i n ec o m p u t i n gt ot r a v e r s i n gt h el a t t i c es t r u c t u r e ，w h i c hn o to n l y c o s t sm u c hl e s so v e r h e a d ，b u ta l s oa v o i d ss c a n n i n gt h ed a t a b a s em a n yp a s s e s i nm yt h e s i s ，t h ep r o c e s s i n gm e t h o di sn a m e dw i t hl b s ( l a t t i c e - b a s e ds k y l i n e a l g o r i t h m ) 。s e c o n d l y , w ec o n s i d e ra n o t h e rk i n do fs k y l i n ec o m p u t i n gi nc a t e g o - r i a ld a t a b a s ei nt h ec o n d i t i o nt h a tt h eo r d e ro ft h ea t t r i b u t ev a l u e si sd y n a m i c w i t ht h et l e rp r e f e r e n c e ，s i m i l a r l y , w ee x c a v a t et h er e l a t i o n sb e t w e e nt h ed v _ a b s t r 8 c t n a l n i co r d e ra n dt h ea d j u s t i n go ft h el a t t i c e t h u s ，w ec a nm a pt h ep r o c e d u r e o fc h a n g i n gt h ea t t r i b u t eo r d e ro n c et or e g u l a t i n gt h el a t t i c es t r u c t u r eo n e t i m e f u r t h e r m o r e ，w ec a nt r a v e r s et h er e g u l a t e dl a t t i c et og a i ns k y l i n e ，i n - s t e a do fd i r e c t l yc o m p u t i n gt h es k y l i n eb yc o m p a r i s o n ，o b v i o u s l y , t r a v e r s i n g t h el a t t i c ec o s t sm u c hl e a so v e r h e a dt h a nt h ec o m p u t i n gb yc o m p a r i s o n ，w h i c h i sp r o v e dt 0h a v et h ee x a c tt i m e ，s p a c ec o m p l e x i t y , f o ro ( u 2 ) a n d0 ( 2 “+ n ) r e s p e c t i v e l y t os u mu p ，b a s e do i li n v e r t sa n dl a t t i c es t r u c t u r e s ，t h et h e s i sp r e s e n t st h ei n - t e g r a ls o l u t i o n sf r o mt h ed e f i n i t i o no fc o n c e p t ，t h ec o n s t r u c t i o no fd a t as t r u c t u r e t ot h ef o r m u l a t i o no fa l g o r i t h m s c s k ya n ds s k ya r eg r e a tc o m p l e m e n t a r i t ya n d i m p r o v e m e n tt oe x i s t i n gs k y l i n ea l g o r i t h m so nh i g hd i m e u s i o n a ld a t a s e t s i nt h e t h e s i s ，an e wp r o b l e mi se x p r e s s e da ss k y l i n ec o m p u t i n gi nd y n a m i c - o r d e re a t e g o r i a l d a t a b a s e w ee x p l o r eal a t t i c e - b a s e dl b sa l g o r i t h mt oa t t a c ki t t h e o r e t i ca n a l y s i s a n de x p e r i m e n t a lr e s u l t ss h o wt h a to u ri n d e x - b a s e dm e t h o d sc a ns o l v et h e i rc o r r e - s p o n d i n gp r o b l e m se f f i c i e n t l ya n do u t p e r f o r mp r e 5 0 n es k y l i n ea l g o r i t h m si nt i m e a n ds p a c ec o m p l e x i t y a tt h es a n l et i m e ，t h e s ea l g o r i t h m sh a v es t r o n go n l i n ea l g o - r i t h mc h a r a c t e r i s t i c s h e n c e i tc o u l db ec o n c l u d e dt h a tt h ep r o p o s e da l g o r i t h m s c a nb ea p p l i e dt oo n l i n ed a t aa n a l y s i sf o rv e r yl a r g ed a t a b a s e k e y w o r d s ：s k y l i n e ，s u b s p a c e ，s a m p l es k y l i n e ，c a t e 鲥a ld a t a b a s e 图目录 1 1 酒店s k y l i n e 例子数据2 1 2 曼哈顿建筑物s k y l i n e ， 2 2 1 s k y l i n e 查询模型， 9 2 2 支配关系哈斯图表示1 1 2 3 酒店s k y l i n e 查询1 2 2 4 建筑物s k y l i n e 查询，1 2 2 5 一个表达s k y l i n e 查询的嵌套s q l 语句1 2 2 6 在b b s 中的r - 树1 7 3 1 投影前后s k y l i n e 变化，2 6 3 25 维子空间查询，3 5 3 3 邻近s k y l i n e 查询，3 5 3 4c p ut i m ev sd a t a b a s e ( 1 0 0 k b 、，3 6 3 5 独立数据集渐进查询，3 7 3 6 反相关数据集渐进查询，3 7 3 7e f f e c to f c a r d i n a l i t y ( d = 5 1 3 7 4 1 s k y l i n e 尺寸与数据集大小4 1 4 2 平和点例子，4 3 4 3 c s k yv 8s s k y ，5 2 4 4s s b 与维度变化5 2 4 5s s k y 与势的变化5 3 4 6 抽样结果值分布5 4 4 7 s k y l i n e 尺寸c s k yv ss s k y 5 4 4 8s s k y 结果数目。5 4 4 9s k y l i n e 尺寸c s k yv ss s k y 5 5 4 1 0s s k y 结果数目，5 5 图目录 5 1 三维布尔量哈斯图 5 2 有序分类属性格哈斯图 5 3 用户动态选择序对s k y l i n e 的影响， 5 4 不可达点例子， 5 5 变序哈希表 5 6 例子数据格重建过程。 5 7 总比特影响b n l + 、，sl b s 5 8 总比特影响l b sv bl b s - o r d e r ， 5 9 维度影响b n l + v 8l b s 5 1 0 维度影响l b sv sl b s - o r d e r 5 1 1 势的影响b n l + v 8l b s 5 1 2 势的影响l b sv sl b s - o r d e r 5 1 3 比特数和尺寸关系 5 1 4 尺寸影响l b sv 8b n l v 缸铊够以卯n n n n 他住符侣 表目录 2 1 一个s k y l i n e 数据例子1 1 2 2 基于索引的s k y l i n e 算法，2 0 2 3 通用s k y l i n e 算法，2 0 3 1 3 2 3 3 3 4 3 5 3 6 4 1 4 2 4 3 4 4 一个n b as k y l i n e 例子 i n v e r t s 数据结构 一个i n v e r t s 结构例子 c s k y 算法中一些符号表 c s k y 算法示例 s k y l i n e 尺寸 一个s k y l i n e 数据例子 s s k y 算法中一些符号表 一个i n v e r t s 结构例子 s s k y 算法示例， 5 1 一个分类属性的酒店数据例子，5 8 5 2 布尔量序变化处理，6 6 5 3l b s - c 中分类属性变量编码6 7 丝盯嚣跖 必弱鹞 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：陋日期： 论文使用授权声明 巫； 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容。可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：- j 弛导师签名：触日期：! 业 = 亡巴 一早 论 1 1 研究背景 自从上世纪四十年代第一台电子计算机艾尼阿克( e n i a c ) 诞生以来，开创 了一个以计算机部分代替人类劳动的现代信息社会。特别的，人们越来越依赖使 用计算机来存储、分析和处理各种数据。早期的基于文件系统的数据处理技术仅 能够处理有限规模的数据量。随着信息技术应用的不断深入，处理的数据量越来 越大，从数据获取的知识要求也越来越多，文件系统技术面临着数据有效管理的 困难，凸现出数据冗余、不致性、以及数据联系弱等弱点。 目前得到最广泛应用的数据处理技术是数据库管理系统( d a t a b a s em a n a g e - m e n ts y s t e m ，d b m s ) 和数据仓库技术( d a t aw a r e h o u s e ，d w ) 。对于关系数据 库的成功，我们不得不提至i s q l 查询语言。s q l 应用如此广泛，以至它几乎渗透 到所有的关系数据库管理系统中。 但是，随着信息技术应用的进一步深入和通讯技术的发展。一方面，人们收 集数据的手段和获得的数据更集加丰富；另一方面，用户希望从这些海量、高 维的数据集中获取更多有用的知识。传统的数据库s q l 查询语言在处理这些问题 遇到了挑战。我们举一个常见的例子【1 4 】。假设你要去旅游胜地巴哈马首都拿骚 ( n a s s a u ) 去度假，自然你希望寻找一个价格便宜尽量靠近海边的好酒店。不章的 是，这两方面考量是鱼和熊掌不可得兼的关系。通常，越靠近海边的酒店价格越 高。旅行社的数据库管理系统也不能为你决定哪个是最好的酒店。但是，其至少 应该告诉你一些你感兴趣的酒店。实际上，如果不是两方面都不好于其他酒店， 这样的酒店都是可以感兴趣的，我们称这样的酒店组成的集合为s k y l i n e ，每个可 以感兴趣的酒店谓之s p ( s k y l i n ep o i n t ) 点。如图1 1 ，其中a ，b ，c ，d ，e 点 表示的酒店就是上面所述用户感兴趣的，其他的则不是。更进一步，从这些酒店 中，用户可以根据自己的偏好作出选择。这包含两层含义：一是用户需要选择不 1 第 绪 1 绪论 同得查询属性组合集，如酒店例子，用户可能不仅关心价格和距离属性，可能关 注酒店的星级标准等等；二是对于选择的各属性给予不同的侧重，换句话说。用 户可能对查询数据集的不同属性给于不一样的关注权重。 酒店例子可以看出s k y l i n e 计算是非常有用的。当然，可以举出更多多属性决 策分析方面的应用。比如。企业寻找能力强但薪水低的雇员，用户希望买到价 格低质量好的商品等等。另外，s k y l i n e 操作对于数据库的可视化也非常有用。 图i 2 是一个曼哈顿建筑物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 的应用将会层出不穷。 p n ( $ ) 图1 1 ：酒店8 k y l i n e 例子数据 图1 2 ：曼哈顿建筑物s k y i i n e 从理论上来说，关系数据库查询语言s q l 没有完全对应的相关s k y l i n e 查询子 句。明显的，对于一维数据来说，s q l 的排序( s o r t ) 操作等同s k y l i n e 查询操 作；但是，对于二维以上的数据，s q l 不能有效地提供s k y l i n e 查询结果；当 然，s k y l i n e 计算结果可以通过嵌套s q l 语句来实现，但这样实现的计算s k y l i n e 方 式，其结果是效率非常低下，详细的例子可以参考文献 1 4 】。因此，传统的s q l 查 询语言不能很好地解决s k y l i n e 查询问题。需要开发新的算法来实现这样的查询需 求。 事实上，s k y l i n e 计算本身不是一个新的课题。早在上世纪7 0 年代，就有学者 研究m a m m a lv e c t o r 1 2 1 算并先后提出了很多高效的基于内存的算法。从本质 上来说，m a x i m a lv e c t o r 计算和s k y l i n e 计算是一致的。但各种应用所产生的新的 数据形式，使得这些算法或者对这些算法仅作简单的修改不能用来解决新环境下 的s k y l i n e 计算问题。下面我们给出几个具体应用场景： 2 时空数据 1 绪论 自美国副总统戈尔1 9 9 8 年1 月3 1 日提出“数字地球( d i g i t a l g l o b a l ) ”的概念 后，在信息产业、科技界、各国政府以及普通民众中引起了积极的反响。“数字 地球”为新世纪空间科学、信息科学和地球科学的发展提供了崭新的思路。“数 字地球”在国防、农业、气象等各方面具有非常重要的作用。为了不在这一关键 技术方面落后于发达国家，中国自1 9 9 6 年起也开始了空间信息基础设施的规划、 标准规范、关键技术及技术原型的研究。“数字地球”的核心思想是用数字化手 段处理地球问题，最大限度她整合信息资源形成时空数据库，其主要是由地学 数据、文本数据、基于因特网的操作平台和应用模型组成。该类数据明显特点 是多维、海量、随时间变化而不断更新。如何开发新的算法，处理这型数据库 中s k y l i n e 计算是一个令人非常向往的事情。 因特网数据 因特网数据极为丰富，既有实时通过网络传送的大量信息，同时不同的站点 也无时不在发布新的信息和更新自己的事务日志。例如，作为电子商务领头羊 的e b a y 公司，其存储主管p a u l s t r o n g 曾对e b a y 每天要处理的数据做了如下介绍： 平均每天的p v ( p a g e v i e w ) 超过1 0 亿；每秒钟交易大约1 7 0 0 美元的商品；每分 钟卖出一辆车；每秒钟卖出一件汽车饰品或者配件；每两分钟卖出一件钻石首 饰；6