Computer Science ›› 2017, Vol. 44 ›› Issue (2): 1-16.doi: 10.11896/j.issn.1002-137X.2017.02.001

    Next Articles

Spatial Skyline Queries:Applications,Research and Challenges

YU Wei, ZHENG Ji-ping, WANG Hai-xiang, WANG Yong-ge, CHEN Jia-liang and JIANG Shun-qing   

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

Abstract: Spatial Skyline queries combined with dynamic attributes have been applied in many areas.This survey first introduced definitions of spatial Skylines as well as traditional Skylines and reviewed the development of Skyline queries in the latest 15 years.Then,the survey put emphasis on introducing applications of spatial Skylines in various areas.Key methods and techniques were summarized based on the applications.Finally,the survey put forward some challenges and gave general research directions for spatial Skyline processing in the future.

Key words: Spatial Skyline queries,Voronoi diagrams,Manhattan distance,Wireless sensor networks,Road networks

[1] Big data:Science in the petabyte era[J].Nature,2008,455:1-136.
[2] KUNG H T,LUCCIO F,PREPARATE F P.On finding themaxima of a set of vectors[J].J.ACM.,1975,22(4):469-476.
[3] BORZSONY S,KOSSMANN D,STOCKER K,et al.The Skyline operator[C]∥Proceedings of the 17th International Confe-rence on Data Engineering.2001:421-430.
[4] TAN K L,ENG P K,BENG C O,et al.Efficient ProgressiveSkyline Computation[C]∥Proceedings of the 27th International Conference on Very Large Data Bases.2001:301-310.
[5] CHOMICKI J,GODFREY P,GRZY J,et al.Skyline with Presorting[C]∥Proceeding of the 19th International Conference on Data Engineering.2003:717-719.
[6] GODFREY P,SHIPLEY R,GRYZ J.Maximal Vector Computation in Large Data Sets[C]∥VLDB.2005:229-240.
[7] KOSSMANN D,RAMSAK F,ROST S.Shooting Stars in the sky:An online algorithm for skyline queries[C]∥Proceeding of the 28nd International Conference on Very Large Data Bases.2002:275-286.
[8] PAPADIAS D,TAO Y F,FU G,et al.Progressive skyline computation in database systems[J].ACM Transactions on Database Systems,2005,30(1):41-82.
[9] PAPADIAS D,TAO Y F,FU G,et al.An Optimal and Progressive Algorithm for Skyline Queries[C]∥Proceeding of SIGMOD.2003:467-478.
[10] CHAN C Y,JAGADISH H V,TAN K L,et al.On high dimensional skyline[M]∥Advances in Database Technology-EDBT 2006.Springer Berlin Heidelberg,2006:478-495.
[11] CHAN C Y,JAGADISH H V,TAN K L,et al.Finding k-dominant skyline in high dimentional space[C]∥Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data.ACM,2006:503-514.
[12] LIN X,YUAN Y,ZHANG Q,et al.Selecting stars:The k most respresentative skyline operator[C]∥IEEE 23rd International Conference on Data Engineering,2007(ICDE 2007).IEEE,2007:86-95.
[13] SHARIFZADEH M,SHAHABI C.The spatial skyline queries[C]∥Proceeding of the International Conference on Very Large Data Bases(VLDB’06).Seoul,Korea,2006:751-762.
[14] SHARIFZADEH M,SHAHABI C,KAZEMI L.Processing spatial skyline queries in both vector spaces and spatial network databases[J].ACM Trans.Database Syst,2009,34(3):1-45.
[15] SON W,LEE M W,AHN H K,et al.Spatial skyline queries:an efficient geometric algorithm[M]∥Advanced in Spatial and Temporal Databases.Springer Berlin Heidelberg,2009:247-264.
[16] LEE M W,SON W,AHN H K,et al.Spatial skyline queries:exact and approximation algorithms[J].GeoInformatica,2011,15(4):665-697.
[17] SON W B,HWANG S W,AHN H K.MSSQ:Manhattan Spatial Skyline Queries[M]∥ Advances in Spatial and Temporal Databases.Springer Berlin Heidelbering, 2011:313-329.
[18] SON W B,HWANG S W,AHN H K.MSSQ:Manhattan Spatial Skyline Queries[J].Inf.Syst.,2014,40:67-83.
[19] DENG K,ZHOU X,SHEN H T.Multi-source skyline queryprocessing in road networks[C]∥Proceedings of the 23th International Conference on Data Engineering.2007:796-805.
[20] HUANG X,JENSEN C S.In-route skyline querying for laca-tion-based services[M]∥Web and Wireless Geographical Information Systems.Springer Berlin Heidelberg,2005:120-135.
[21] KODAMA K,IIJIMA Y,GUO X,et al.Skyline queries based onuser locations and preferences for making location-based recommendations[C]∥Proceedings of the 2009 International Workshop on Location Based Social Networks.ACM,2009:9-16.
[22] GUO X,ISHIKAWA Y,GAO Y.Direction-based spatial skyline[C]∥Proceedings of the Ninth ACM International Workshop on Data Engineering for Wireless and Mobile Access.ACM,2010:73-80.
[23] LEE K C,ZHENG B,LU H,et al.Approaching the Skyline in ZOrder[C]∥Proceeding of VLDB.2007:279-290.
[24] LEE K C K,ZHENG B,LEE W C,et al.Z-SKY:An Efficient Skyline Query Processing Framework Based on Z-Order[J].VLDB Journal,2010,19(2):333-362.
[25] SURAJIT C,NILESH D,RAGHAV K.Robust Cardinality and Cost Estimation for the Skyline Operator[C]∥Proceedings of the 22nd International Conference on Data Engineering (ICDE’06).2006:1-10.
[26] ZHANG Z J,YANG Y,CAI R C,et al.Kernel-based skyline cardinality estimation[C]∥Proceedings of the 2009 ACM SIGMOD International Conference on Management of data (SIGMOD).2009:509-522.
[27] HUANG Y K,CHANG C H,LEE C.Continuous distance-based skyline queries in road networks[J].Information Systems,2012,37(7):611-633.
[28] WU P,ZHANG C J,FENG Y,et al.Parallelizing skyline queriesfor scalable distribution[C]∥Proceedings of EDBT.2006:112-130.
[29] VALKANAS G,PAPADOPOULOS A N.Efficient and adaptive distributed skyline computation[C]∥International Conference on Scientific and Statistical Database Management.Springer Berlin Heidelberg,2010:24-41.
[30] CHEN H,ZHOU S,GUAN J.Towards energy-efficient skyline monitoring in wireless sensor networks[M]∥Wireless Sensor Networks.Springer Berlin Heidelberg,2007:101-116.
[31] CUI B,LU H,XU Q,et al.Parallel distributed processing ofconstrained skyline queries by filtering[C]∥IEEE 24th International Conference on Data Engineering,2008(ICDE 2008).IEEE,2008:546-555.
[32] KHALEFA M E,MOKBEL M F,L eEVANDOSKI J J.Skyline query processing for incomplete data[C]∥IEEE 24th International Conference on Data Engineering,2008(ICDE 2008).IEEE,2008:556-565.
[33] VLACHOU A,DOULKERIDIS C,KOTIDIS Y,et al.SKYPEER:Efficient subspace skyline computation over distributed data[C]∥IEEE 23rd International Conference on Data Engineering,2007(ICDE 2007).IEEE,2007:416-425.
[34] SIDDIQUE M A,TIAN H,MORIMOTO Y.Distributed skyline computation of vertically splitted databases by using mapreduce[C]∥International Conference on Database Systems for Advanced Applications.Springer Berlin Heidelberg,2014:33-45.
[35] HOSE K,VLACHOU A.A survey of skyline processing inhighly distributed environments[J].The VLDB Journal,2012,21(3):359-384.
[36] CHEN L J,CUI B,LU H,et al.iSky:Efficient and Progressive Skyline Computing in a Structured P2P Network[C]∥Procee-ding of The 28th International Conference on Distributed Computing Systems.2008:160-167.
[37] WANG S Y,QUANG H V,BENG C O,et al.Skyframe:aframework for skyline query processing in peer-to-peer systems[J].The VLDB Journal,2009,18:345-362.
[38] TAO Y F,PAPADIAS D.Maintaining Sliding Window Skylines on Data Streams[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(3):377-391.
[39] BALKE W T,GNTZER U,ZHENG J X.Efficient distributed skylining for web information systems[M]∥ Advances in Databases Technology-EDBT 2004.Springer-Verlag Berlin Heidelberg,2004:256-273.
[40] PEI J,JIANG B,LIN X N,et al.Probabilistic skylines on uncertain data[C]∥Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB’07).2007:15-26.
[41] LIAN X,CHEN L.Reverse skyline search in uncertain databa-ses[J].ACM Transactions on Database Systems,2010,35(1):177-185.
[42] KHALEFA MOHAMED E,MOKBEL MOHAMED F,LE-VANDOSKI JUSTIN J.Skyline Query Processing for Incomplete Data[C]∥Proceedings of the 2008 IEEE 24th International Conference on Data Engineering (ICDE’08).IEEE Computer Society,Washington,DC,USA.2008:556-565.
[43] DENG K,ZHOU X,SHEN H T.Multi-source skyline queryprocessing in road networks[C]∥Proceedings of the 23th International Conference on Data Engineering.2007:796-805.
[44] CUI B,LU H,XU Q,et al.Parallel distributed processing ofconstrained skyline queries by filtering[C]∥IEEE 24th International Conference on Data Engineering,2008(ICDE 2008).IEEE,2008:546-555.
[45] ZHU L,TAO Y,ZHOU S.Efficient distributed skyline retrieval[C]∥TKDE.2008.
[46] HUANG Z Y,JENSEN C S,LU H,et al.Skyline Queries Against Mobile Lightweight Devices in MANETs[C]∥International Conference on Data Engineering.2006.
[47] CHEN H,ZHOU S,GUAN J.Towards energy-efficient skyline monitoring in wireless sensor networks[M]∥Wireless Sensor Networks.Springer Berlin Heidelberg,2007:101-116.
[48] YOON S H,SHAHABI C.Distributed spatial skyline query pro-cessing in wireless sensor networks[C]∥International Workshop on Sensor Webs,Databases,and Mining in Networked Sensing Systems(SWDMNSS) in conjunction with International Conference on Networked Sensor Systems(INSS).2009:1-8.
[49] LIN Q,XIAO C,CHEEMA M A,et al.Finding the sites with best accessibilities to amenities[C]∥Database System for Advanced Applications.Springer Berlin Heidelberg,2011:58-72.
[50] LIN Q,ZHANG Y,ZHANG W,et al.General spatial skylineoperator[C]∥Database Systems for Advanced Applications.Springer Berlin Heidelberg,2012:494-508.
[51] LIN Q,ZHANG Y,ZHANG W,et al.Efficient general spatial skyline computation[J].World Wide Web,2013,16(3):247-270.
[52] MADDEN S,FRANKLIN M J,HELLERSTEIN J M,et al.TAG:A tiny aggregation service for ad-hoc sensor networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.
[53] YOU G,LEE M W,IM H,et al.The farthest spatial skyline queries[J].Information Systems,2013,38(3):286-301.
[54] BALKE W T,GUNTZER U,XHENG J X.Efficient distributed skylining for Web information systems[M]∥Advances in Database Technology-EDBT 2004.Springer Berlin Heidelberg,2004:256-273.
[55] CHEEMA M A,LIN X,ZHANG W,et al.A safe zone based approach for monitoring moving skyline queries[C]∥Proceedings of the 16th International Conference on Extending Database Technology.ACM,2013:275-286.
[56] HUANG Z,LU H,OOI B C,et al.Continuous skyline queries for moving objects[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(12):1645-1658.
[57] EVANS W,KIRKPATRICK D,LOFFLER M,et al.Competitive query strategies for minimizing the ply of the potential locations of moving point[C]∥Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry.ACM,2013:155-164.
[58] CHENG L,WONG RAYMOND C W,ZHANG Bin,et al.Hypersphere dominance:an optimal approach[C]∥International Conference on Management of Data.SIGMOD,2014:111-122.
[59] GROZ B,MILO T.Skyline Queries with Noisy Comparisons[C]∥Proceedings of the 34th ACM Symposium on Principles of Database Systems(PODS 2015).2015:185-198.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .