计算机科学 ›› 2018, Vol. 45 ›› Issue (1): 267-272.doi: 10.11896/j.issn.1002-137X.2018.01.047

• 软件与数据库技术 • 上一篇    下一篇

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

摘要: c-skyline技术能针对数据集获得以组为单位的查询结果,非常适用于多标准决策。现有算法采用迭代方式求解,不仅运算过程冗余,而且对无效数据的过滤效果不理想。基于此,设计了一种PPQ(Partition-Prune-Query)算法,首次提出了支配区的概念,并在此基础上对整个数据集区域进行划分;然后根据高效的剪枝策略过滤大部分“无用”的组合,快速获得查询结果。通过实验验证了所提算法的正确性和高效性。

关键词: c-skyline,多标准决策,支配区,剪枝策略

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.

Key words: C-skyline,Multi-criteria decision,Dominant region,Pruning strategies

[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 .