您好,欢迎来到华佗健康网。
搜索
您的当前位置:首页一种处理Skyline查询的有效方法

一种处理Skyline查询的有效方法

来源:华佗健康网
计算机研究与发展 ISSN 1000—1239/CN 1 1-1777门rP Journal of Computer Resear'ch and Development 47(11):1947—1953,2010 一种处理Skyline查询的有效方法 黄震华 向 阳 薛永生。 刘啸岭。 (同济大学电子与信息工程学院 上海 200092) (厦门大学信息科学与技术学院 福建厦门 361005) 。(复旦大学信息科学与工程学院 上海 200433) (jukie.huang@gmail.corn) An Efficient Method for Processing Skyline Queries H uang Zhenhua ,Xiang Yang ,Xue Yongsheng。,and Liu Xiaoling。 (Schoo of Electronics and Information,Tongji University,Shanghai 200092) (Schoo of Inrformation Science and Technology,Xiamen University,Xiamen,Fujian 361005) (Schoo of Information Science and engineering,Fudan University,Shanghai 200433) Abstract Skyline query processing has recently received a lot of attenti on in database community. This is mainly due to the importance of skyline results in many applications,such as multi—criteria decision making,data mining,and user—preference queries.Given a set of k-dimensional obj ects,the skyline query finds the objects that are not dominated by others.When users issue multiple different dimensional space skyline quereis simultaneously,all the existing works obtain the results of these skyline queries from the original relational table from scratch.Clearly,the existing approaches are extremely inefficient as the cardinality of the original relational table and the number of skyline queries increase.Motivated by the above fact,an efficient method,called EAPSQ(efficient algorithm for processing skyline queries),is proposed to return m issued different dimensional—space skyline quereis {SQ1,…,SQ )using prestoring skyline sets{PRl,…,PR ).The PAPSQ algorithm adequately considers the characteristics of the storage mechanism of prestoring skyline sets,and adopts the concept of contribution margin in economics.Thus it can efficiently achieve the optimal state for distribution of Tr/skyline queries between prestoring skyline sets.which can markedly improve the performance for processing skyline queries.Moreover,detailed theoretical analyses and extensive experiments demonstrate that our algorithm iS both efficient and effective. Key words skyline;query processing;relational table;contribution margin;query optimization 摘要skyline查询是近年来数据库领域的一个研究重点和热点.当系统中存在多个不同维空间上的 skyline查询时,现有的工作均直接从底层关系表中获取这些skyline查询的结果集.显然,当底层关系 表的基数较大且skyline查询的个数较多时,现有方法的处理效率极其低下.基于此,提出一种使用预存 储的 个skyline集合{PR ,…,PR }来回答用户提交的 个不同维空间上的skyline查询{SQ ,…, SQ }的有效方法EAPSQ(efficient algorithm for processing skyline queries).算法充分考虑预存储的 收稿日期:2008 12 22;修回日期:2010~04 22 基金项目:国家自然科学基金项目(60903032,70771077);教育部博士学科点专项科研基金项目(20090072120056);国家“八六三”高技术研 究发展计划基金项目(2008AA04Z106);上海市科委科研计划基金项目(08DZl122300);上海市信息委专项基金项目(200901015); 福建省自然科学基金项目(A0310008);同济大学青年优秀人才培养行动计划基金项目(0800219093) 1948 计算机研究与发展2010,47(1I) skyline集合的编码机制,采用经济学中边际贡献(contribution margin)的概念,使得m个用户提交的 skyline查询在 个预存储的skyline集合间的分配达到最佳状态,从而显著提高了处理用户m个 skyline查询的效率.实验评估表明,EAPSQ算法具有有效性和实用性. 关键词skyline查询;查询处理;关系表;边际贡献;查询优化 中图法分类号TP311.132.3 0 引 言 skyline查询处理是近年来数据库学科的一个 研究重点.该查询最早由Borzsonyi等人[=1 引进到 数据库领域中.随后,Chomicki等人 。 在BNL算 法的基础上提出一种先进行对象排序,再进行比较 的查询方法SFS.基于索引的方法最早由Kossmann 等人l4 提出.而Papadias等人 。 指出NN算法的 缺陷,并提出一种基于排序R一树节点的方法BBS, BBS算法克服了NN算法冗余比较节点的不足,且 比NN算法具有更强的剪枝能力.Sharifzadeh等 人_7 首次在空间数据库上研究skyline查询,并给出 空间skyline查询的概念.Li等人l8 将skyline查询 技术引进到时间序列研究邻域 来克服维度危机问 题¨1 .Pei等人l=1 等人考虑如何在不确定的数据集 上进行有效的skyline查询计算,并给出一种新颖的 概率skyline模型来解决对象出现概率不确定的情 况.Tao等人 首次考虑当数据动态更新时,如何 高效维护skyline查询结果集.而Wu等人 研究 在具有CAN体系结构的分布式网络ll副中如何进行 有效的skyline查询.值得注意的是,文献[1—13]所 研究的是单个固定维空间上的skyline查询效率,并 且均直接从底层关系表中获取查询结果集.因此,当 底层关系表的基数较大且skyline查询的个数较多 时,这些文献所给方法的处理效率极其低下. 与本文研究较为接近的是文献[15 2o]中的工 作,它们均是考虑多个不同维空间上的skyline查询 效率.Pei等人_】 借鉴()LAP应用领域的立方体 格,研究了不同维空间上skyline查询的语义.与文 献[15—16]不同,Tao等人_1 首次提出SUBSKY 算法来获取任意数量的维空间skyline查询结果集. Bartolini等人口 在2008年的ToDS国际期刊上针 对SUBSKY算法的3个性能缺陷,基于内存R一树 索引给出一个有效算法SaLSa.在文献I-2o]中,Jin 等人提出了3个新颖的概念,即最大支配维空间、最 大受支配维空间和最大等价空间,并基于这3个概 念给出一个随机采样算法WAMZ,来快速返回任意 维空间上skyline对象集合.然而,这些方法虽然解 决了文献[1 13]不能处理多个维空间skyline查询 的问题,但是这些方法至少需要一次将底层关系表 从磁盘调入内存中,因此当底层关系表较大且查询 个数较多时,这些方法的处理效率也将变得低下. 随着大容量廉价磁盘的出现,使得采用预存储 的 个skyline集合{PR ,…,P尺 }来有效回答用户 提交的Ⅲ个不同维空间上的skyline查询{SQ1,…, 5Q },成为克服现有方法低效率的首选技术.另一 方面,Huang等人[ u给出的两阶段方法(incremental maintenance algorithm for SkyCube based on identify and refresh,IMASCIR)能够高效地维护预 存储的skyline集合,从而为本文方法的可行性提供 了保证.为了便于描述,在下面的章节中,我们将“预 存储的skyline集合”简称为“skyline快照”. 基于以上2个事实,本文从优化m个skyline 查询在n个skyline快照间的分组出发,提出了一种 新颖的处理skyline查询的有效算法EAPSQ (efficient algorithm for processing skyline queries). EAPSQ算法充分考虑 个skyline快照的编码机 制,采用经济学中边际贡献的概念,使得m个用户 提交的skyline查询在 个skyline快照间的分配达 到最佳状态,从而显著提高了处理用户 个skyline 查询的效率.实验评估表明,EAPSQ算法具有有效 性和实用性. 1 问题描述 不失一般性,本文假定外部磁盘上存储有n (n≤2 一1)个skyline快照MV={PRl,…,PR }, 每个skyline快照对应某一维空间上的skyline集 合.同时,我们假定用户提交的 ( ≤2 一1)个维 空间上skyline查询为Q一{S Q】,…,SQ ).根据文 献[22]可知,skyline快照PR (1≤i≤72)能够用于 回答用户查询SQ,(1≤j_≤m),当且仅当PR所对 应的维空问 是SQ 所对应的维空间 的超集, 黄震华等:一种处理Skyline查询的有效方法 即 V .显然,当V 一V,时,PR 恰为查询SQ, 所返回的结果.另一方面,当V V 成立时,使用 PR 回答查询SQ 的时间代价由2部分组成:第1 部分将skyline快照PR 文件HCS 调入内存的开 销 Mv(PR );第2部分由HCS 产生查询SQ,结果 集的CPU开销t。(SQ,,P R,). 第1部分时间代价 w(PR )比较容易获得,如 式(1)所示: PR 啪 , (1) 其中size(HCS )为文件HCS 的大小,block—size为 内存块大小,而tb…loc 为传输一个内存块的时间开销. 下面,我们给出第2部分的代价t。(sQ,PR ). 不失一般性,令 一{ ,{. 定理1l2 .假定skyline快照PR 在维空间 上满足联合分布函数F( )和联合密度函数厂( ), 其中lz一(3c “, ),那么SQ,结果集基数的期望 值E({PR l, )可表示为  lPR I x I f( )(1一F(Jc)) 职r。。 dE.(2) 定理2 .假定skyline快照PR 在维空间V, 上满足联合分布函数F( )和联合密度函数厂( ), 其中 一(or ,…, ),那么第2部分的时间代价t。 (SQ ,PR)可表示为 I PR I ’ ’一E( l, )×E( 一1, +1) 一1. (3) x=2 基于上面的分析,我们接下来给出本文的问题 定义. 问题定义.假定M M 为用来回答用户提 交的m个skyline查询Q一{SQ ,…,SQ }的 skyline快照集合,且查询SQ,(1≤ ≤ )的结果集 从skyline快照my(SQ )( (SQ,)∈M )的文件 hcs(SQ)中获取,那么这 个skyline查询的总时 间代价由2部分组成:其中第1部分为将M 中所 有skyline快照从磁盘调入内存的时间开销;第2部 分为由M 来获取 个skyline查询结果集的时间 开销,即总时间代价可表示为 T l(MV ,Q)一∑t ̄(PR )+ pR∈Mv ∈Q・~{sQ1 ∈^Ⅳ ∑tQ(SQ ,my(SQ )). (4) i我们的目标是将每个skyline查询sQ,分配给 最合适的skyline快照 u(sQ),使得总时间代价 T 。 最小. 2 ̄AI'SQ算法描述 由于要精确得到最优分配方案(即时间代价 T 。 取最小值)是NP—hard问题,因此在这一节中我 们给出一个多项式时间复杂度的近似算法EAPSQ. 并且我们从理论上证明EAPSQ算法具有单调性以 及(e一1)/e≈O.63的下界收益. EAPSQ算法的基本思想是:将每个 ̄kyline查 询sQ 分配给最合适的skyline快照m (sQ,),从 而使得式(4)给出的总时间代价T (M ,Q)最 小.基于边际贡献的概念,在每一次循环中,EAPSQ 算法完成如下3个方面的工作:1)获取收益最大的 skyline快照Bview;2)对于未分配给任何skyline 快照的每个查询SQ ,如果Bview所对应的维空间 V 是SQ 所对应的维空间 ,的超集,那么将SQ, 分配给Bview来回答;3)对于在之前的循环中已分 配给其他skyline快照的每个查询SQ(记该 skyline快照为fv),如果由Bview回答SQ 的代价 低于由fv回答SQ 的代价,那么将SQ重新分配给 Bview来回答.当所有m个用户提交的skyline查 询均分配完毕,则EAPSQ算法停止. EAPSQ算法伪码如下所示. 算法1.EAPSQ(M ,Q). /*MV={PR ,…,PR )为skyline快照集合; Q一{SQ ,…,SQ )为用户提交的skyline查询集 合*| ①UQ—Q; ②LM—M ; ③For 一1 to l Q l Do ④ 获取能回答SQ,的所有skyline快照构成 的集合CMV(sQ); ⑤ minT(SQ,)一 rain ( ( )+tQ(SQ,, V ∈ V【 ) )); ⑥Repeat ⑦ £P DB 一。。; ⑧ For UM中的每个skyline快照PR Do ⑨ 获取能被PR 回答的所有skyline查询 构成的集合CS—Q(PR ); ⑩ △Q—CS—Q(PR )nUQ; ⑥ ACost ̄-∑arin T(SQ,); V △。 ⑥ VCost—一T 。 ({P尺:),△Q); ⑩ B  ̄--ACost--VCost; ⑩ If B >tempB Then ⑥ fP B—B ;Bview*-PR。; ⑩ ASQ(Bview)一△Q; ⑩ UQ—UQ一△Q; ⑩ CA+一CSQ(Bview)一ASQ(Bview); ⑩ FS一{fv l fvE M ^fv UM^CA n AS—Q(_厂 )≠ }; ⑩ 调用函数尺AQV(FS,Bview,CA); ⑨ M一【 ~{Bview}; ③Until UQ一 . 注意,在算法1中,步骤⑧~⑥完成EAPSQ 算法的第一方面T作,步骤⑩完成EAPSQ算法的 第二方面_T作,而步骤⑩中的函数RAQ (FS, Bview,cA)完成EAPSQ算法的第三方面工作.下 面,我们具体给出函数RAQV(FS,Bvieze,CA)的执 行过程. 算法2.RAQ (FS,Bview,CA). /*RAQV检查CA中每个skyline查询q,如果 g已分配给skyline快照fv∈FS,但是q由Bview 回答的代价低于由fv回答的代价,那么将q重新分 配给Bview来回答*/ ①FSCost ̄-O;BviewCost ̄-O; ②For FS中每个skyline快照iv Do ③ 获取已分配给fv回答的所有skyline查 询构成的集合AS—Q(fv ̄; ④ AQ(fv)一CAnAS—Q(fv); ⑤ 1f AQ(fv)=AS—Q(fv)Then ⑥ FS—Cosf—FS—Cost+Tt l({ ),△Q); ⑦ Else ⑧ FSCo时一F5一Co +∑tQ(q, ); qEAQ( ) ⑨Bview—Cost一qE—∑AQ( ) to(g,Bview); ⑩If Bview—Cost ̄FS—Cost Then ⑩ ASQ(Bview)一ASQ(Bview)U CA; ⑥For FS中每个skyline快照-厂 Do ⑩ AS—Q(fv)+一AS—Q(fv)一AQ(/、 ); ⑩ If ASQ(fv)一 Then ⑥ UM一【 7MU{. ). EAPSQ算法具有如下3个重要性质:1)EAPSQ 算法在多项式时间复杂度内返回查询的分配方案; 2)EAPSQ算法具有单调性,即预存储的skyline快 照越多,EAPSQ算法产生的分配方案越有效; 3)EAPSQ算法产生的分配方案的下界为(e一1)/e.e 这3个性质保证了EAPSQ算法的有效性,即性质1 计算机研究与发展2010,47(11) 保证EAPSQ算法能够快速返回用户所提交查询的 分配方案;性质2确保EAPSQ算法的响应时间与 磁盘空间成正相关性;而性质3保证了在最坏情况 下,EAPSQ算法所产生分配方案的运行效率不会 低于最优运行效率的(e一1)/e ̄--63 . 接下来,我们从理论上证明EAPSQ算法这3 个性质的正确性. 定理3.EAPSQ算法的时间复杂度为o(IQI ・ l MV{),其中I Q f为用户提交的skyline查询的个 数,而{M f为skyline快照的个数. 定理4.假定M 和EP 分别为预存储的 skyline快照集合以及在M 的基础上产生的查询 分配方案,令TC(EP )为按分配方案EP 处理所 有查询的时间开销.那么有:V ,Y,M M TC(EP )≥TC(EP ). 定理5.记使用EAPSQ算法获取分配方案EP 所需的skyline快照个数为叫,而记精确得到最优分 配方案OP所需的skyline快照个数为愚,并假定 尼≤ .那么有 TC( BP )T OP C( ) ≥ e  ̄o.63~ ,’  其中方案BP为不使用任何skyline快照,而TC (XX)为按分配方案XX处理所有查询的时间开销. 3算法实验评估 实验评估用到2类数据集:综合数据集SND, 由文献[1]中的数据产生器生成;实际数据集CDS, 为Chiba医学院从1980年开始收集到1999年为止 的胶原质疾病统计数据.在实验中,我们产生w个 skyline查询,W的取值在10~9O间变化;同时,我 们产生K个skyline快照,其中K的取值在2O~6O 问变化.与EAPSQ算法比较的方法有6个:1)对于 每个skyline查询q,随机选择一个skyline快照 来回答q,我们称该方法为NAIVE算法;2)对于每 个skyline查询q,选择回答q代价最小的skyline 快照my来回答q,我们称该方法为LOFA算法;3) 文献[15—16]给出的SKYEY算法;4)文献E17一]8J 给出的SUBSKY算法;5)文献E19]中给出的SaLSa 算法;6)文献[2O]给出的WAMZ算法. 3.1综合数据集SND上的实验评估 在本节中,我们评估本文算法EAPSQ产生的 查询分配方案在综合数据集SND上的性能.实验分 为2组. 在第1组实验中,查询个数固定为70,skyline 黄震华等:一种处理Skyline查询的有效方法 快照个数在2O~60问变化.图1显示了该组的实验 结果. —斗一Naive——;I(一LOFA - ̄--EAPSQ —_.◆_一SKYEY—_-r.一SUBSKY—_|●一SaLSa —— WAMZ \ g 兰 Number of Skyline Snapshots Fig.1 Query time VS.number of skyline snapshots on SND dataset. 图1 SND上查询运行时间随skyline快照个数变化实验 从图1中,我们可以看出,本文算法EAPSQ产 生的查询分配方案的性能在各种情况下均优于其余 6个算法.这主要是因为:EAPSQ算法充分考虑了 数据对象的存储机制,并且能够使得这70个维 空间上skyline查询在多个skyline快照间的分配达 到最佳状态;对于Naive和I OFA算法来说,它们 虽然考虑了使用skyline快照,但没有考虑其优化分 配策略;而对于SKYEY,SUBSKY,SaI Sa和wAMZ 算法来说,它们需要将底层关系表从硬盘调入内存 中.另外,我们注意到,SKYEY,SUBSKY,SaI Sa和 WAMZ这4个算法的运行时间与skyline快照的个 数无关,这是显然的.因为这些算法的实施不涉及到 skyline快照.此外,我们还发现当skyline快照个数 逐渐增多时,EAPSQ算法的优越程度越来越高. 在第2组实验中skyline快照个数固定为50, 查询个数在l0b90间变化.图2显示了该组的实验 结果. —}一Na ̄'ve—-) 一LOFA - ̄--EAPSQ —_. 一SKYEY—■广SUBSKY—| —SaLSa —{ ~WAⅣ【Z 呐 \ g 兰 Fig.2 Query time vs.the number of skyline queries 图2查询运行时间随skyline查询个数变化实验 与第1组实验结果类似,在图2中,我们可以看 出,本文算法EAPSQ产生的查询分配方案的性能 在查询个数的各种取值下均优于其余6个算法.另 外,我们注意到,在这组实验中,SKYEY算法的运 行时间与查询个数无关,而其余5个算法的运行时 间均与查询个数有关.这主要是因为SKYEY算法 返回全部255个维空间上的skyline查询结果集,而 其他5个算法确切返回实验参数所指定的维空间 skyline查询结果集.此外,我们还发现,当查询个数 逐渐增大时,EAPSQ算法的优越程度越来越高.这 主要是因为EAPSQ算法产生的查询分配方案只需 要调入层次联合代理文件进内存即可,而不需要调 入skyline快照本身,因此,EAPSQ算法产生的查 询分配方案能够节省大量的i/o开销. 3.2 实际数据集CDS上的实验评估 在本节中,我们评估本文算法EAPSQ产生的 查询分配方案在实际数据集SND上的性能.为了简 单,我们主要评估当skyline快照个数变化时,EAPSQ 算法和Naive,LOFA算法产生的查询分配方案的 运行时间.与3.1节的第1组实验设置相同,我们固 定查询个数为7O,并让skyline快照个数在20~6O 间变化.图3显示了该组的实验结果. —+一Naive— LoFA—l×一EAPSQ ——◆一SKYEY—1 一SUBSKY—--._一SaLSa —_E 一WAMZ \ g 芒. 兰 Fig.3 Query time VN.number of skyline snapshots on CDS dataset. 图3 CDS上查询运行时间随skyline快照个数变化实验 从图3中,我们同样可以看出,本文算法EAPSQ 产生的查询分配方案的性能在各种情况下均优于其 他6个算法.另一方面,与图1中的曲线图相比我们 发现,在这组实验中,当skyline快照个数逐渐增多 时,EAPSQ算法的优越程度没有图1中EAPSQ算 法的优越程度高.这主要是因为,图1中实验的综合 数据集基数为5×1O ,而在这组实验中,实际数据 集的基数仅约为2 x 10 .因此,在这组实验中,层次 1952 联合代理文件所占skyline快照容量的百分比较小, 从而导致EAPSQ算法的优越程度没有图1中 EAPSQ算法的优越程度高.另一方面,我们注意到 与综合数据集SND相比,这6个算法在实际数据集 SND上平均处理一个数据块(64 KB)的时间较长. 这主要是因为实际数据集CDS的反相关性比综合 数据集SND高,即实际数据集CDS中的skyline对 象所占的百分比较综合数据集SND大,因此它需要 更多的对象比较时问. 4结论与将来工作 本文从优化m个用户skyline查询在 个skyline 快照间的分组出发,提出了一种新颖的处理skyline 查询的有效算法EAPS Q.EAPSQ算法充分考虑,2 个skyline快照的编码机制,采用经济学中边际贡献 的概念,使得 个用户提交的skyline查询在 个 skyline快照间的分配达到最佳状态,从而显著提高 了处理用户m个skyline查询的效率.实验评估表 明,EAPSQ算法具有有效性和实用性. 我们将来比较重要和感兴趣的后续T作包括: 设计比层次联合代理更有效的编码机制,从而进一 步降低算法的I/O开销和内存消耗;在构造查询分 配方案方面,引进参数因子来平衡构造查询分配方 案的时间开销与skyline查询的时问开销. 参 考 文 献 L】] Borzsonyi S,Kossmann D,Stocker K.The skyline operator [c]/Proc of the Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2001:421—430 [z3 Chomicki j,Godfrey P,Gryz j,et a/. Sk5 hne wixh presorting[c]/Proc of the Int Con{on Data Engineering. Los Alamitos,CA,IEEE Computer Society,2003:71 7-719 [3] Huang Zhenhua,Wang Wei.An algebra for skyline query processing data cube口].Journal of Computer Research and Development,2007,44(6):990-999(in Chinese) (黄震华,汪卫.Skyline查询处理数据立方体代数[J].计算 机研究与发展,2007,44(6):990—999) E43 Kossmann D,Ramsak F,Rost S.Shooting stars in the sky: An online algorithm for skyline queries[c]//Proc of the Int Conf on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann,2002:290—302 [5] Papadias D,Tao Y,Fu G,et a1.Progressive skyline computation in data systems[J].ACM Trans on Database Systems,2005,30(1):4l一82 计算机研究与发展2010,47(11) [6] Papadias D,Tao Y,Fu G,et a1.An optimal and progressive algorithm for skyline queries[c]/[Proe of the ACM SIGMOD Int Conf on Management of Data.New York: ACM,2003:467-478 [7] Sharifzadeh M,Shahahi C.The spatial skyline queries[c]// Proc of the Int Conf on Very Large Data Bases.New York: ACM,2006:751—762 [8] Li Q.Lopez I ,Moon B.Skyline index for time series data [J].IEEE Trans on Knowledge and Data Engineering, 2004,1 6(6):669-684 [9] Duan Jiangjiao,Xuc Yongsheng,Lin Ziyu,et a1.A novel hidden Markov model—based hierarchical time-series clustering algorithm[J].Journal of Computer Research and Development,2006,43(1):61—67(in Chinese) (段江娇,薛永生,林子雨,等.一种新的基于隐Markov模 型的分层时间序列聚类算法EJ].计算机研究与发展,2006, 43(1):6i-67) [iO] Papadimitriou S,Yu P.Optimal multi scale patterns in time series streams[c]/Proc of the ACM SIGMOD Int Conf on Management of Data.New York:AGM,2006:647—658 [11] Pei J,Jiang B,Lin X,et a1.Probahilistic skylines on uncertain data[c]/Proc of the Int Conf on Very Large Data Bases.New York:ACM,2007:641—652 [12] Tao Y,Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Trans on Knowledge and Data Engineering。2006,18(3):377—391 [i3] Wu P,Zhang C,Feng Y,et a1.Parallelizing skyline queries for scalable distribution[c]/[Proc of the Int Conf on Extending Datahase Technology.Berlin:Springer,2006: 11 2-I 30 [I4] Campbell B.Amortised memory analysis using the depth of data structures[c]/Proc of the 18th Int Conf on European Symp on Programming.Los Alamitos,CA:[EEE Computer Society,2009:190—204 [15] Pei J,Jin W,Ester M,et a1.Catching the best views of skyline:A semantic approach based on decisive subspaces [c]fWroe of the Int Coal out Very Large Data Bases.New York:ACM,2005:315-326 [16] Pei J,Yuan Y,Lin X,et a1.Towards multidimensional subspace skyline analysis EJ].ACM Trans on Database Systems,2006,31(4):643—697 [17] Tao Y,Xiao X,Pei J.Subsky:Efficient computation of skylines in subspaces EC]//Proc of the lnt Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society, 2006:65-74 [18] Ta。Y,Xiao X.Efficient skyline and top—k retrievel in subspaces[J]. IEEE Trans on Knowledge and Data Engineering.2007,19(8):1072—1088 [19] Bartolini I,Ciaccia P,Patdla M.Efficient sort-based skyline evaluation[J].ACM Trans on Database Systems,2008,33 (4):1632—1695 黄震华等:一种处理Skyline查询的有效方法 Uo] Jin W,Tung A,Ester M,et a1.()n efficient processing of subspace skyline queries on high dimensional data[q/Proc of the Int Conf on Scientific and Statistical Database Management.1.os Alamitos,CA:IEEE Computer Society, 2007:1 2-2l l 953 [2I] Huang Z,Wang W.A novel incremental maintenance algorithm of skycube[C]//Proc of the Int Conf on Database and Expert Systems Applications.Berlin:Springer,2006: 781—790 [22] Huang Z.Guo J,Sun S,et a1.Efficient optimization of multiple subspace skyline queries[J].Journal of Computer Science and Technology,2008,23(1):103—111  S,Dalvi N。Kaushik R.Rohust cardinality and [23] Chaudhuricost estimation for skyline operator Ec]//Proc of the Int Conf on Data Engineering.I os Alamitos,CA:IEEE Computer Society,2006:64 75 Huang Zhenhua,born in 1 980.PhD and lecturer. Member of China Computer Federation.His current research interests include data warehouse,data mining, query optimization,data stream and skyline computation. 刘啸岭,1979年生,博士研究生,计算机学会学生会员,主要 研究方向为数据库、数据流和商业智能. 黄震华,1980年生,博士,讲师,中国计算机学会会员,手要研 究方向为数据仓库、数据挖掘、查询优化、数据流和skyline 计算. Research Background Skyline query processing has recently received a lot of attention in the database and decision making communities.In the 2001 International Conference on Data Engineering,skyline query processing technology is first introduced into the database communities.From 2005,the researchers have tackled with the problem of multiple different subspace skyline quereis.The representative one is the SUBSKY algorithm which is proposed by Tao Y.Based on the data distribution,the SUBSKY algorithm creates an anchor point for each cluster,and builds a B tree on the L。。distance between each obj ect to its corresponding anchor.We observe that all these existing algorithms obtain the skyline sets from the original relational table from scratch,and are inapplicable to the applications of huge data set.In this paper,we focus on the efficiency and time cost of multiple different subspace skyline quereis.Our solution adequately considers the characteristics of the storage mechanism of prestoring skyline sets,and adopts the concept of contribution margin in economics.Our work is supported by the National Natural Science Foundation of China under grant Nos.60903032 and 70771077,the Doctoral Fund of the Ministry of Education of China under grant No.20090072120056,the National 863 High Technology Research and Development Plan of China under grant No.2008AA04Z106,and the Outstanding Young Foundation of Tongji University under grant No.0800219093. 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务