路网中线段反k最近邻查询研究
|
摘要
为了弥补现有的研究成果无法有效地处理路网环境下基于线段的反k最近邻问题的不足,提出了在路网环境下线段反k最近邻查询方法。该查询方法主要应用于评估查询对象的影响范围。根据路网及Voronoi图的特点提出了网络线段Voronoi图的概念。在静态数据集情况下利用网络线段Voronoi图的性质提出了STA_RVLRk NN算法,查询包括过滤过程和精炼过程两大部分。进一步,在动态数据集的情况下提出了DYN_RVLRk NN算法,查询分为空间线段对象增加和删除两种情况,并对不同的情况给出了相应的算法,得到查询结果集。理论研究和实验表明,所提算法能有效地处理路网中基于线段的反k最近邻问题。
To remedy the defects that existing methods can not deal with the line segment reverse k nearest neighbor(Rk NN) query in road network, this paper puts forward the line segment Rk NN query method in road network. The query method is mainly used to assess the scope of query object. Based on the characteristics of road network and Voronoi diagram, the network line Voronoi diagram(NLVD) concept is proposed. According to the property of NLVD, the STA_RVLRk NN is given in static line segment set environment, the query includes two parts: filtering and refining processes. Further, DYN_RVLRk NN method is given in dynamic line segment set environment, this query is divided into two parts of adding and deleting space segment objects, then the corresponding algorithm is proposed for different situations and new query result set is obtained. The theatrical study and experimental results show that the algorithm can effectively deal with the line segment Rk NN query in road network.
To remedy the defects that existing methods can not deal with the line segment reverse k nearest neighbor(Rk NN) query in road network, this paper puts forward the line segment Rk NN query method in road network. The query method is mainly used to assess the scope of query object. Based on the characteristics of road network and Voronoi diagram, the network line Voronoi diagram(NLVD) concept is proposed. According to the property of NLVD, the STA_RVLRk NN is given in static line segment set environment, the query includes two parts: filtering and refining processes. Further, DYN_RVLRk NN method is given in dynamic line segment set environment, this query is divided into two parts of adding and deleting space segment objects, then the corresponding algorithm is proposed for different situations and new query result set is obtained. The theatrical study and experimental results show that the algorithm can effectively deal with the line segment Rk NN query in road network.
引文
[1]Gong Caixia,Chen Xinjun,Gao Feng,et al.Development and application of geographic information system in marine fisheries[J].Journal of Shanghai Ocean University,2011,15(2):134-143.
[2]Mookiah M R K,Acharya U R,Koh J E W,et al.Decision support system for age-related macular degeneration using discrete wavelet transform[J].Medical&Biological Engineering&Computing,2014,52(9):781-796.
[3]Hong Zixuan,Bian Fuling.Time-space and cognition-space transformations for transportation network analysis based on multidimensional scaling and self-organizing map[C]//SPIE 7144:Proceedings of the Geoinformatics 2008 and Joint Conference on GIS and Built Environment:The Built Environment and its Dynamics,Guangzhou,China,Jun 28-29,2008.
[4]Dasarathy B V.Nearest neighbor(NN)norms:NN pattern classification techniques[M].Los Alamitos,USA:IEEE Computer Society Press,1990:217-224.
[5]Li Song,Zhang Liping,Hao Zhongxiao.Strong neighbor pair query in dynamic dataset[J].Journal of Computer Research and Development,2015,52(3):749-759.
[6]Boiman O,Shechtman E,Irani M.In defense of nearest-neighbor based image classification[C]//Proceedings of the 2008IEEE Conference on Computer Vision and Pattern Recognition,Anchorage,USA,Jun 23-28,2008.Piscataway,USA:IEEE,2008:1192-1999.
[7]Cheng R,Chen Lei,Chen Jinchuan,et al.Evaluating probability threshold k-nearest-neighbor queries over uncertain data[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology,Saint Petersburg,Russia,Mar 24-26,2009.New York:ACM,2009:672-683.
[8]Zhang Zhaoxing,Fan Xingqi,Zhao Suyun,et al.Fast reduction algorithm research based on k-nearest neighbor fuzzy rough set[J].Journal of Frontiers of Computer Science and Technology,2015,9(1):14-23.
[9]Yi Xun,Paulet R,Bertino E,et al.Practical approximate k nearest neighbor queries with location and query privacy[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(6):1546-1559.
[10]Wang Li,Qin Xiaolin,Shi Changyue.Bichromatic reverse nearest neighbor queries in indoor space[J].Journal of Frontiers of Computer Science and Technology,2015,9(3):310-320.
[11]Lin Huaizhong,Chen Fangshu,Gao Yunjun,et al.Finding optimal region for bichromatic reverse nearest neighbor in two-and three-dimensional spaces[J].Geoinformatica,2016,20(3):351-384.
[12]Tran Q T,Taniar D,Safar M.Bichromatic reverse nearestneighbor search in mobile systems[J].IEEE Systems Journal,2014,4(2):230-242.
[13]Lee K W,Choi D W,Chung C W.DART:an efficient method for direction-aware bichromatic reverse k nearest neighbor queries[C]//LNCS 8098:Proceedings of the 13th International Conference on Advances in Spatial and Temporal Databases,Munich,Germany,Aug 21-23,2013.Berlin,Heidelberg:Springer,2013:295-311.
[14]Emrich T,Kriegel H P,Ger P,et al.Reverse k-nearest neighbor monitoring on mobile objects[C]//Proceedings of the18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,San Jose,USA,Nov 2-5,2010.New York:ACM,2010:494-497.
[15]Lu Bingliang,Cui Xiaoyu,Liu Na.Bichromatic reverse nearest k neighbor query processing on road network[J].Journal of Chinese Computer Systems,2015,36(2):266-270.
[16]Yu Xiaonan.A method for reverse k-nearest-neighbor queries in obstructed spaces[J].Chinese Journal of Computers,2011,34(10):1917-1925.
[17]Zhu Huaijie,Wang Jiaying,Wang Bin,et al.Location privacy pressing obstructed nearest neighbor queries[J].Journal of Computer Research and Development,2014,51(1):115-125.
[18]Hao Zhongxiao,Wang Yudong,He Yunbin.Line segment nearest neighbor query of spatial database[J].Journal of Computer Research and Development,2008,45(9):1539-1545.
[19]Gu Yu,Zhang Hui,Wang Zhigang,et al.Efficient moving k nearest neighbor queries over line segment objects[J].World Wide Web Internet and Web Information Systems,2015,19(4):653-677.
[20]Liu Runtao,Hao Zhongxiao.Fast algorithm of nearest neighbor query for line segments of spatial database[J].Journal of Computer Research and Development,2011,48(12):2379-2384.
[21]Papadopoulou E,Zavershynskyi M.The higher-order Voronoi diagram of line segments[J].Algorithmica,2014,74(1):1-25.
[1]龚彩霞,陈新军,高峰,等.地理信息系统在海洋渔业中的应用现状及前景分析[J].上海海洋大学学报,2011,20(6):902-909.
[5]李松,张丽平,郝忠孝.动态数据集环境下的强邻近对查询[J].计算机研究与发展,2015,52(3):749-759.
[8]张照星,范星奇,赵素云,等.k-近邻模糊粗糙集的快速约简算法研究[J].计算机科学与探索,2015,9(1):14-23.
[10]王丽,秦小麟,施常月.室内双色数据集上的反向最近邻查询[J].计算机科学与探索,2015,9(3):310-320.
[15]卢秉亮,崔晓玉,刘娜.路网中双色反向k近邻查询处理[J].小型微型计算机系统,2015,36(2):266-270.
[16]于晓南.一种障碍空间中的反k最近邻查询研究[J].计算机学报,2011,34(10):1917-1925.
[17]朱怀杰,王佳英,王斌,等.障碍空间中保持位置隐私的最近邻查询方法[J].计算机研究与发展,2014,51(1):115-125.
[18]郝忠孝,王玉东,何云斌.空间数据库平面线段最近邻查询问题研究[J].计算机研究与发展,2008,45(9):1539-1545.
[20]刘润涛,郝忠孝.空间数据库平面线段快速最近邻查询算法[J].计算机研究与发展,2011,48(12):2379-2384.
[2]Mookiah M R K,Acharya U R,Koh J E W,et al.Decision support system for age-related macular degeneration using discrete wavelet transform[J].Medical&Biological Engineering&Computing,2014,52(9):781-796.
[3]Hong Zixuan,Bian Fuling.Time-space and cognition-space transformations for transportation network analysis based on multidimensional scaling and self-organizing map[C]//SPIE 7144:Proceedings of the Geoinformatics 2008 and Joint Conference on GIS and Built Environment:The Built Environment and its Dynamics,Guangzhou,China,Jun 28-29,2008.
[4]Dasarathy B V.Nearest neighbor(NN)norms:NN pattern classification techniques[M].Los Alamitos,USA:IEEE Computer Society Press,1990:217-224.
[5]Li Song,Zhang Liping,Hao Zhongxiao.Strong neighbor pair query in dynamic dataset[J].Journal of Computer Research and Development,2015,52(3):749-759.
[6]Boiman O,Shechtman E,Irani M.In defense of nearest-neighbor based image classification[C]//Proceedings of the 2008IEEE Conference on Computer Vision and Pattern Recognition,Anchorage,USA,Jun 23-28,2008.Piscataway,USA:IEEE,2008:1192-1999.
[7]Cheng R,Chen Lei,Chen Jinchuan,et al.Evaluating probability threshold k-nearest-neighbor queries over uncertain data[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology,Saint Petersburg,Russia,Mar 24-26,2009.New York:ACM,2009:672-683.
[8]Zhang Zhaoxing,Fan Xingqi,Zhao Suyun,et al.Fast reduction algorithm research based on k-nearest neighbor fuzzy rough set[J].Journal of Frontiers of Computer Science and Technology,2015,9(1):14-23.
[9]Yi Xun,Paulet R,Bertino E,et al.Practical approximate k nearest neighbor queries with location and query privacy[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(6):1546-1559.
[10]Wang Li,Qin Xiaolin,Shi Changyue.Bichromatic reverse nearest neighbor queries in indoor space[J].Journal of Frontiers of Computer Science and Technology,2015,9(3):310-320.
[11]Lin Huaizhong,Chen Fangshu,Gao Yunjun,et al.Finding optimal region for bichromatic reverse nearest neighbor in two-and three-dimensional spaces[J].Geoinformatica,2016,20(3):351-384.
[12]Tran Q T,Taniar D,Safar M.Bichromatic reverse nearestneighbor search in mobile systems[J].IEEE Systems Journal,2014,4(2):230-242.
[13]Lee K W,Choi D W,Chung C W.DART:an efficient method for direction-aware bichromatic reverse k nearest neighbor queries[C]//LNCS 8098:Proceedings of the 13th International Conference on Advances in Spatial and Temporal Databases,Munich,Germany,Aug 21-23,2013.Berlin,Heidelberg:Springer,2013:295-311.
[14]Emrich T,Kriegel H P,Ger P,et al.Reverse k-nearest neighbor monitoring on mobile objects[C]//Proceedings of the18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,San Jose,USA,Nov 2-5,2010.New York:ACM,2010:494-497.
[15]Lu Bingliang,Cui Xiaoyu,Liu Na.Bichromatic reverse nearest k neighbor query processing on road network[J].Journal of Chinese Computer Systems,2015,36(2):266-270.
[16]Yu Xiaonan.A method for reverse k-nearest-neighbor queries in obstructed spaces[J].Chinese Journal of Computers,2011,34(10):1917-1925.
[17]Zhu Huaijie,Wang Jiaying,Wang Bin,et al.Location privacy pressing obstructed nearest neighbor queries[J].Journal of Computer Research and Development,2014,51(1):115-125.
[18]Hao Zhongxiao,Wang Yudong,He Yunbin.Line segment nearest neighbor query of spatial database[J].Journal of Computer Research and Development,2008,45(9):1539-1545.
[19]Gu Yu,Zhang Hui,Wang Zhigang,et al.Efficient moving k nearest neighbor queries over line segment objects[J].World Wide Web Internet and Web Information Systems,2015,19(4):653-677.
[20]Liu Runtao,Hao Zhongxiao.Fast algorithm of nearest neighbor query for line segments of spatial database[J].Journal of Computer Research and Development,2011,48(12):2379-2384.
[21]Papadopoulou E,Zavershynskyi M.The higher-order Voronoi diagram of line segments[J].Algorithmica,2014,74(1):1-25.
[1]龚彩霞,陈新军,高峰,等.地理信息系统在海洋渔业中的应用现状及前景分析[J].上海海洋大学学报,2011,20(6):902-909.
[5]李松,张丽平,郝忠孝.动态数据集环境下的强邻近对查询[J].计算机研究与发展,2015,52(3):749-759.
[8]张照星,范星奇,赵素云,等.k-近邻模糊粗糙集的快速约简算法研究[J].计算机科学与探索,2015,9(1):14-23.
[10]王丽,秦小麟,施常月.室内双色数据集上的反向最近邻查询[J].计算机科学与探索,2015,9(3):310-320.
[15]卢秉亮,崔晓玉,刘娜.路网中双色反向k近邻查询处理[J].小型微型计算机系统,2015,36(2):266-270.
[16]于晓南.一种障碍空间中的反k最近邻查询研究[J].计算机学报,2011,34(10):1917-1925.
[17]朱怀杰,王佳英,王斌,等.障碍空间中保持位置隐私的最近邻查询方法[J].计算机研究与发展,2014,51(1):115-125.
[18]郝忠孝,王玉东,何云斌.空间数据库平面线段最近邻查询问题研究[J].计算机研究与发展,2008,45(9):1539-1545.
[20]刘润涛,郝忠孝.空间数据库平面线段快速最近邻查询算法[J].计算机研究与发展,2011,48(12):2379-2384.