Computer Science ›› 2018, Vol. 45 ›› Issue (1): 267-272.doi: 10.11896/j.issn.1002-137X.2018.01.047

Previous Articles     Next Articles

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.

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   
No Suggested Reading articles found!