• 软件与数据库技术 •

### 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
 [1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 . [2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 . [3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 . [4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 . [5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 . [6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 . [7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 . [8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 . [9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 . [10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .