• 软件与数据库技术 •

### PPQ:一种基于区域划分的c-skyline查询算法

1. 东华大学信息科学与技术学院 上海201620大庆师范学院计算机科学与信息技术学院 黑龙江 大庆163712,东华大学信息科学与技术学院 上海201620大庆师范学院计算机科学与信息技术学院 黑龙江 大庆163712,东华大学信息科学与技术学院 上海201620大庆师范学院计算机科学与信息技术学院 黑龙江 大庆163712
• 出版日期:2018-01-15 发布日期:2018-11-13
• 基金资助:
本文受大庆师范学院青年基金项目(15ZR07),大庆市指导性科技计划项目(zd-2016-054)资助

### PPQ:Finding Combinatorial Skyline Based on Partition

DONG Lei-gang, LIU Guo-hua and CUI Xiao-wei

• Online:2018-01-15 Published:2018-11-13

Abstract: C-skyline computation,aiming to return the outstanding combinations,becomes more and more useful in multi-criteria decision.The current algorithm uses a recursive method with the redundant computation and the unsatisfactory data pruning rate.So a new algorithm PPQ(Partition-Prune-Query)was proposed.The concept of the dominant region was introduced and the whole data region was divided into sub-spaces.Then most useless combinations were pruned based on pruning strategies,and the result could be returned quickly.The experiments manifest the correctness and efficiency of the proposed algorithm.

 [1] BORZONYI S,KOSSMANN D,STOCKER K.The skyline ope-rator[C]∥ ICDE 2001.Heidelberg,Germany,2001:421-430. [2] CHUNG Y C,SU I F,LEE C.Efficient computation of combinatorial skyline queries[J].Information System,2013,38(3):369-387. [3] TAN K,ENG P,OOI B.Efficient progressive skyline computation[C]∥VLDB.Rome,Italy,2001:301-310. [4] CHOMICKI J,GODFREY P,GRYZ J,et al.Skyline with presorting[C]∥ICDE.Bangolore,India,2003:717-719. [5] KOSSMANN D,RAMSAK F,ROST S.Shooting stars in the sky:an online algorithm for skyline queries[C]∥VLDB.HongKong,China,2002:275-286. [6] LEE J,HWANG S W.Toward efficient multidimensional subspace skyline computation[J].Vldb Journal,2014,3(1):129-145. [7] PEI J,JIN W,ESTER M,et al.Catching the best views of skyline:asemantic approach based on decisive subspaces[C]∥VLDB.2005:253-264. [8] LI Y Y,LI Z Y,DONG M X.Efficient subspace skyline query based on user preference using MapReduce[J].Ad Hoc Networks,2015(35):105-115. [9] XIA T,ZHANG D.Refreshing the sky:the compressed skycube with efficient support for frequent updates[C]∥SIGMOD.2006:491-502. [10] MIAO X Y,GAO Y J,CHEN G,et al.k-dominant skyline queries on incomplete data[J].Information Sciences,2016(367):990-1011. [11] CHAN C Y,JAGADISH H V,TAN K L,et al(1)Findingk-dominant skylines in high dimensional space[C]∥SIGMOD.2006:503-514. [12] JIANG T,ZHANG B,LIN D.Incremental evaluation of top-k combinatorial metric skyline query[J].Knowledge-Based Systems,2015,4:89-105. [13] LEE J,YOU G W,HWANG S W.Personalized top-k skylinequeries in high-dimensional space[J].Information Systems,2009,34(1):45-61. [14] JIANG T,ZHANG B,GAO Y J,et al.Efficient top k query processing on mutual skyline[J].Journal of Computer Research and Development,2013,50(5):986-997.(in Chinese).蒋涛,张彬,高云君,等.高效的Top k相互skyline查询算法[J].计算机研究与发展,2013,50(5):986-997. [15] ZHANG W,LIN X,ZHANG Y,et al.Thresholdbased probabilistic top k dominating query[J].The VLDB Journal,2010,19(2):283-305. [16] LE T M N,CAO J,HE Z.Answering skyline queries on probabilistic data using the dominance of probabilistic tuples[J].Information Sciences,2016,340-341(C):58-85. [17] PUJARI A K,KAGITA V R,GARG A.Efficient computation for probabilistic skyline over uncertain preferences[J].Information Sciences,2015,4(C):146-162. [18] PEI J,JIANG B,LIN X,et al(1)Probabilistic skylines on uncertain data[C]∥VLDB.2007:15-26. [19] SU I F,CHUNG Y C,LEE C.Top-k combinatorial skyline queries[C]∥Proceedings of the 15th International Conference on Database Systems for Advanced Applications (DASFAA 2010).2010. [20] LIU J F,XIONG L,PEI J.Finding Pareto Optimal Groups_ Group-based Skyline[C]∥VLDB.2015:2086-2097. [21] LIU R T,HAO Z X.Spatial index structure based on R-tree and quadtree:PQOP-tree[J].Journal of Harbin Institute of Technology,2010,2(5):323-327.(in Chinese) 刘润涛,郝忠孝.R-树和四叉树的空间索引结构:RQOP-树[J].哈尔滨工业大学学报,2010,2(5):323-327.
 No related articles found!
Viewed
Full text

Abstract

Cited

Shared
Discussed