障碍环境中空间Skyline查询方法
|
摘要
为了弥补现有的研究成果对处理障碍环境下空间Skyline查询问题的不足,提出了在障碍环境下基于Voronoi图的空间Skyline查询方法。该方法在实际应用中可以用来解决多目标决策问题。依据查询点集合是否发生变化提出了两种情况下的障碍环境中空间Skyline查询(spatial Skyline queries in obstacle space,OSSQ)方法:一种是静态查询点的障碍环境中空间Skyline查询(static query points of Skyline query in obstacle space,STA_OSSQ)方法,该查询方法主要包括约剪数据集和支配检查两个过程,最后得到Skyline集合;另一种是动态查询点状态下的障碍环境中Skyline查询(dynamic query points of Skyline query in obstacle space,DYN_OSSQ)方法,该方法主要处理了查询点动态增加和减少情况下障碍环境中空间Skyline查询问题。理论研究和实验表明所提出的方法具有较高的效率。
In order to make up for the shortcomings of the existing research results in dealing with the space Skyline query problem in the obstacle environment,this paper proposes a spatial Skyline query method based on Voronoi diagram in the obstacle environment.This method can be used to solve multi-objective decision problems in practical applications.According to the change of the query point set,the spatial Skyline queries in obstacle space(OSSQ query) method is proposed in two cases.One method is a static query points of Skyline query in obstacle space(STA_OSSQ query) method.This query method mainly includes two processes:a cut data set and a dominance check,and finally a Skyline set is obtained.The other is the dynamic query points of Skyline query in obstacle space(DYN_OSSQ query) method in the dynamic query point state.The method mainly deals with the space Skyline in the obstacle environment when the query point is dynamically increased and decreased.Finally,it is shown that the proposed method has higher efficiency through theoretical research and experiments.
In order to make up for the shortcomings of the existing research results in dealing with the space Skyline query problem in the obstacle environment,this paper proposes a spatial Skyline query method based on Voronoi diagram in the obstacle environment.This method can be used to solve multi-objective decision problems in practical applications.According to the change of the query point set,the spatial Skyline queries in obstacle space(OSSQ query) method is proposed in two cases.One method is a static query points of Skyline query in obstacle space(STA_OSSQ query) method.This query method mainly includes two processes:a cut data set and a dominance check,and finally a Skyline set is obtained.The other is the dynamic query points of Skyline query in obstacle space(DYN_OSSQ query) method in the dynamic query point state.The method mainly deals with the space Skyline in the obstacle environment when the query point is dynamically increased and decreased.Finally,it is shown that the proposed method has higher efficiency through theoretical research and experiments.
引文
[1]B?rzs?nyi S,Kossmann D,Stocker K.The Skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Apr 2-6,2001.Washington:IEEE Computer Society,2002:421-430.
[2]Han Xixian,Wang Bailing,Lai Guojun.Dynamic Skyline computation on massive data[J].Knowledge&Information Systems,2018,7:1-29.
[3]Liu Chuanming,Tang S W.An effective probabilistic Skyline query process on uncertain data streams[J].Procedia Computer Science,2015,63(2):40-47.
[4]Awasthi A,Bhattacharya A,Gupta S,et al.K-dominant Skyline join queries:extending the join paradigm to K-dominant Skylines[C]//Proceedings of the 33rd IEEE International Conference on Data Engineering,San Diego,Apr 19-22,2017.Washington:IEEE Computer Society,2017:99-102.
[5]Banaei-Kashani F,Ghaemi P,Movaqar B,et al.Efficient maximal reverse Skyline query processing[J].Geoinformatica,2017,21(3):1-24.
[6]Taguchi N,Amagata D,Hara T,et al.Geo-social keyword Skyline queries[C]//LNCS 10438:Proceedings of the 28th International Conference on Database and Expert Systems Applications,Lyon,Aug 28-31,2017.Berlin,Heidelberg:Springer,2017:425-435.
[7]Banafaa K M,Li Ruixuan.Efficient algorithms for constrained subspace Skyline query in structured peer-to-peer systems[C]//LNCS 7418:Proceedings of the 13th International Conference on Web-Age Information Management,Harbin,Aug 18-20,2012.Berlin,Heidelberg:Springer,2012:334-345.
[8]Meng Yi,Liu Yubao,Li Qinrui.A compression method based algorithm for subspace skyline computation in high dimensional space[J].Journal of Computer Research and Development,2013,50(S1):101-108.
[9]Wang Xiaoyi,Qin Xiaolin,Wang Ning,et al.Efficient algorithm for multiple subspace Skyline queries processing[J].Journal of Frontiers of Computer Science and Technology,2016,10(5):623-634.
[10]Fu Xiaoyi,Miao Xiaoye,Xu Jianliang,et al.Continuous range-based Skyline queries in road networks[J].World Wide Web-Internet&Web Information Systems,2017,20(6):1443-1467.
[11]Park Y,Min J K,Shim K.Processing of probabilistic Skyline queries using MapReduce[J].VLDB Endowment,2015,8(12):1406-1417.
[12]Yang Linqing,Li Zhan,Mou Yanchao,et al.Algorithm of parallel top-k Skyline queries for large data set[J].Journal of Frontiers of Computer Science and Technology,2015,9(8):897-905.
[13]Sharifzadeh M,Shahabi C.The spatial Skyline queries[C]//Proceedings of the 32nd International Conference on Very Large Data Bases,Seoul,Sep 12-15,2006.New York:ACM,2006:751-762.
[14]Lin Qianlu,Zhang Ying,Zhang Wenjie,et al.General spatial Skyline operator[C]//LNCS 7238:Proceedings of the 17th International Conference on Database Systems for Advanced Applications,Busan,Apr 15-19,2012.Berlin,Heidelberg:Springer,2012:494-508.
[15]Chen Zhiming,Arefin M S,Morimoto Y.Skyline queries for spatial objects:a method for selecting spatial objects based on surrounding environments[C]//Proceedings of the3rd International Conference on Networking and Computing,Okinawa,Dec 5-7,2012.Washington:IEEE Computer Society,2012:215-220.
[16]You G W,Lee M W,Im H,et al.The farthest spatial Skyline queries[J].Information Systems,2013,38(3):286-301.
[17]Li Song,Li Shuang,Zhang Liping,et al.Spatial Skyline query method based on R+-tree for obstructed space[J].Journal of Frontiers of Computer Science and Technology,2017,11(12):1886-1896.
[18]Zhang Liping,Liu Lei,Hao Xiaohong,et al.Voronoi-based group reverse k nearest neighbor query in obstruct space[J].Journal of Computer Research and Development,2017,54(4):861-871.
[8]孟熠,刘玉葆,李启睿.一种基于压缩策略的高维空间子空间Skyline查询算法[J].计算机研究与发展,2013,50(S1):101-108.
[9]王潇逸,秦小麟,王宁,等.高效多子空间Skyline查询处理算法[J].计算机科学与探索,2016,10(5):623-634.
[12]杨林青,李湛,牟雁超,等.面向大规模数据集的并行化Top-k Skyline查询算法[J].计算机科学与探索,2015,9(8):897-905.
[17]李松,李爽,张丽平,等.障碍空间中基于R+树的空间Skyline查询方法[J].计算机科学与探索,2017,11(12):1886-1896.
[18]张丽平,刘蕾,郝晓红,等.障碍空间中基于Voronoi图的组反k最近邻查询研究[J].计算机研究与发展,2017,54(4):861-871.
[2]Han Xixian,Wang Bailing,Lai Guojun.Dynamic Skyline computation on massive data[J].Knowledge&Information Systems,2018,7:1-29.
[3]Liu Chuanming,Tang S W.An effective probabilistic Skyline query process on uncertain data streams[J].Procedia Computer Science,2015,63(2):40-47.
[4]Awasthi A,Bhattacharya A,Gupta S,et al.K-dominant Skyline join queries:extending the join paradigm to K-dominant Skylines[C]//Proceedings of the 33rd IEEE International Conference on Data Engineering,San Diego,Apr 19-22,2017.Washington:IEEE Computer Society,2017:99-102.
[5]Banaei-Kashani F,Ghaemi P,Movaqar B,et al.Efficient maximal reverse Skyline query processing[J].Geoinformatica,2017,21(3):1-24.
[6]Taguchi N,Amagata D,Hara T,et al.Geo-social keyword Skyline queries[C]//LNCS 10438:Proceedings of the 28th International Conference on Database and Expert Systems Applications,Lyon,Aug 28-31,2017.Berlin,Heidelberg:Springer,2017:425-435.
[7]Banafaa K M,Li Ruixuan.Efficient algorithms for constrained subspace Skyline query in structured peer-to-peer systems[C]//LNCS 7418:Proceedings of the 13th International Conference on Web-Age Information Management,Harbin,Aug 18-20,2012.Berlin,Heidelberg:Springer,2012:334-345.
[8]Meng Yi,Liu Yubao,Li Qinrui.A compression method based algorithm for subspace skyline computation in high dimensional space[J].Journal of Computer Research and Development,2013,50(S1):101-108.
[9]Wang Xiaoyi,Qin Xiaolin,Wang Ning,et al.Efficient algorithm for multiple subspace Skyline queries processing[J].Journal of Frontiers of Computer Science and Technology,2016,10(5):623-634.
[10]Fu Xiaoyi,Miao Xiaoye,Xu Jianliang,et al.Continuous range-based Skyline queries in road networks[J].World Wide Web-Internet&Web Information Systems,2017,20(6):1443-1467.
[11]Park Y,Min J K,Shim K.Processing of probabilistic Skyline queries using MapReduce[J].VLDB Endowment,2015,8(12):1406-1417.
[12]Yang Linqing,Li Zhan,Mou Yanchao,et al.Algorithm of parallel top-k Skyline queries for large data set[J].Journal of Frontiers of Computer Science and Technology,2015,9(8):897-905.
[13]Sharifzadeh M,Shahabi C.The spatial Skyline queries[C]//Proceedings of the 32nd International Conference on Very Large Data Bases,Seoul,Sep 12-15,2006.New York:ACM,2006:751-762.
[14]Lin Qianlu,Zhang Ying,Zhang Wenjie,et al.General spatial Skyline operator[C]//LNCS 7238:Proceedings of the 17th International Conference on Database Systems for Advanced Applications,Busan,Apr 15-19,2012.Berlin,Heidelberg:Springer,2012:494-508.
[15]Chen Zhiming,Arefin M S,Morimoto Y.Skyline queries for spatial objects:a method for selecting spatial objects based on surrounding environments[C]//Proceedings of the3rd International Conference on Networking and Computing,Okinawa,Dec 5-7,2012.Washington:IEEE Computer Society,2012:215-220.
[16]You G W,Lee M W,Im H,et al.The farthest spatial Skyline queries[J].Information Systems,2013,38(3):286-301.
[17]Li Song,Li Shuang,Zhang Liping,et al.Spatial Skyline query method based on R+-tree for obstructed space[J].Journal of Frontiers of Computer Science and Technology,2017,11(12):1886-1896.
[18]Zhang Liping,Liu Lei,Hao Xiaohong,et al.Voronoi-based group reverse k nearest neighbor query in obstruct space[J].Journal of Computer Research and Development,2017,54(4):861-871.
[8]孟熠,刘玉葆,李启睿.一种基于压缩策略的高维空间子空间Skyline查询算法[J].计算机研究与发展,2013,50(S1):101-108.
[9]王潇逸,秦小麟,王宁,等.高效多子空间Skyline查询处理算法[J].计算机科学与探索,2016,10(5):623-634.
[12]杨林青,李湛,牟雁超,等.面向大规模数据集的并行化Top-k Skyline查询算法[J].计算机科学与探索,2015,9(8):897-905.
[17]李松,李爽,张丽平,等.障碍空间中基于R+树的空间Skyline查询方法[J].计算机科学与探索,2017,11(12):1886-1896.
[18]张丽平,刘蕾,郝晓红,等.障碍空间中基于Voronoi图的组反k最近邻查询研究[J].计算机研究与发展,2017,54(4):861-871.