移动对象连续k近邻查询处理技术研究
|
摘要
基于位置的服务(LBS)是指通过移动终端和无线通讯网络的配合,确定用户具体所在的空间位置,从而为用户提供与空间位置相关的信息服务,如导航服务、交通调度、物流管理、紧急呼叫、位置广告等。基于位置的服务通常涉及到对大量移动对象的查询,k近邻(KNN)查询就是其中最为重要的查询之。
k近邻查询在解决实际应用中的需求越来越明显,引起了相关研究领域的广泛关注。目前,针对欧式空间中静态对象的k近邻查询技术已发展成熟,对于道路网环境,且考虑移动对象的连续k近邻(CkNN)查询处理技术的研究还很少,且已有的查询处理技术在面对大量并发查询时,效果并不太理想。
本文是针对道路网环境下的移动对象连续k近邻查询处理技术展开的研究,目的在于尽可能地提高服务器端的查询处理效率,从而缩短查询响应时间。所做的工作主要体现在以下几个方面：
(1)深入剖析了已有的基于欧式空间的和道路网环境下的移动对象连续k近邻查询处理的经典算法,对其一般性技术思路进行了概括,并讨论了各种查询处理方法的优缺点。比较了道路网环境和欧式空间查询处理的不同,总结了道路网环境下k近邻查询处理的难点。
(2)经分析道路网环境下k近邻查询的特点,设计了一种共享计算的初始结果计算算法,在查询处理中,充分复用其他查询的计算成果,从而避免了对道路网的冗余搜索。实验验证了该算法在查询密集型道路网中的高效性。
(3)面向高度动态的道路网环境,提出了一种基于扩展树的连续k近邻查询处理方法(TL-CkNN),该方法周期性地对系统中的查询进行结果维护,通过应用数据更新进行扩展树剪枝,然后基于剪枝后扩展树中剩余的有效部分继续进行结果重计算,从而减少了对道路网的重复扩展。实验证明了算法在高度动态的道路网环境下的优越性。
Location based service(LBS) provides users with information services related to their positions which can be obtained through mobile devices and wireless networks infrastructure, such as navigation services, traffic scheduling, logistics management, emergency call, location advertising, etc. Location based services generally related to queries over a large number of moving objects, k nearest neighbor(kNN) query is one of the most important query.
The capabilities of k nearest neighbor query in addressing the needs of the practical application become more and more obvious, attracted wide attention in relevant research areas. At present, k nearest neighbor query technologies over static objects in euclidean space has been good developed, but few continuous k nearest neighbor(CkNN) query technologies considered moving objects and road networks, when face to a large number of concurrent queries, the existing query technologis made poor performance.
This paper is a study on continuous k nearest neighbor queries over moving objects based on road networks, aims to improve the query processing efficiency of the server-side as much as possible. The work of this paper is mainly reflected in the following aspects:
(1) Deeply analyzed the existing classical query algorithms which considered moving objects based on road networks or euclidean space, summarized its general technical ideas, discussed the advantages and disadvantages of these methods, compared the query processing based on road networks with that in euclidean space, and summed the difficulty of processing k nearest neighbor queries which based on road networks.
(2) By analyzed the characteristic of k nearest neighbor queries which based on road networks, this paper proposed a shared computation method named initial result computing algorithm, the algorithm sufficiently reused other queries'computation result in the query processing, thus avoided redundant search of road networks.
(3) This paper presented an expansion tree based continuous k nearest neighbor query algorithm for the highly dynamic road networks(TL-CkNN), which maintain the reuslt periodically for all the queries registerd in the system, use data updates to prune the expansion tree, then based on the pruned expansion tree continue to result recompuation, thereby reduced the duplication of road network expansion. Experiment results show this algorithm has better performance than other algorithms in the highly dynamic road networks.
k近邻查询在解决实际应用中的需求越来越明显,引起了相关研究领域的广泛关注。目前,针对欧式空间中静态对象的k近邻查询技术已发展成熟,对于道路网环境,且考虑移动对象的连续k近邻(CkNN)查询处理技术的研究还很少,且已有的查询处理技术在面对大量并发查询时,效果并不太理想。
本文是针对道路网环境下的移动对象连续k近邻查询处理技术展开的研究,目的在于尽可能地提高服务器端的查询处理效率,从而缩短查询响应时间。所做的工作主要体现在以下几个方面：
(1)深入剖析了已有的基于欧式空间的和道路网环境下的移动对象连续k近邻查询处理的经典算法,对其一般性技术思路进行了概括,并讨论了各种查询处理方法的优缺点。比较了道路网环境和欧式空间查询处理的不同,总结了道路网环境下k近邻查询处理的难点。
(2)经分析道路网环境下k近邻查询的特点,设计了一种共享计算的初始结果计算算法,在查询处理中,充分复用其他查询的计算成果,从而避免了对道路网的冗余搜索。实验验证了该算法在查询密集型道路网中的高效性。
(3)面向高度动态的道路网环境,提出了一种基于扩展树的连续k近邻查询处理方法(TL-CkNN),该方法周期性地对系统中的查询进行结果维护,通过应用数据更新进行扩展树剪枝,然后基于剪枝后扩展树中剩余的有效部分继续进行结果重计算,从而减少了对道路网的重复扩展。实验证明了算法在高度动态的道路网环境下的优越性。
Location based service(LBS) provides users with information services related to their positions which can be obtained through mobile devices and wireless networks infrastructure, such as navigation services, traffic scheduling, logistics management, emergency call, location advertising, etc. Location based services generally related to queries over a large number of moving objects, k nearest neighbor(kNN) query is one of the most important query.
The capabilities of k nearest neighbor query in addressing the needs of the practical application become more and more obvious, attracted wide attention in relevant research areas. At present, k nearest neighbor query technologies over static objects in euclidean space has been good developed, but few continuous k nearest neighbor(CkNN) query technologies considered moving objects and road networks, when face to a large number of concurrent queries, the existing query technologis made poor performance.
This paper is a study on continuous k nearest neighbor queries over moving objects based on road networks, aims to improve the query processing efficiency of the server-side as much as possible. The work of this paper is mainly reflected in the following aspects:
(1) Deeply analyzed the existing classical query algorithms which considered moving objects based on road networks or euclidean space, summarized its general technical ideas, discussed the advantages and disadvantages of these methods, compared the query processing based on road networks with that in euclidean space, and summed the difficulty of processing k nearest neighbor queries which based on road networks.
(2) By analyzed the characteristic of k nearest neighbor queries which based on road networks, this paper proposed a shared computation method named initial result computing algorithm, the algorithm sufficiently reused other queries'computation result in the query processing, thus avoided redundant search of road networks.
(3) This paper presented an expansion tree based continuous k nearest neighbor query algorithm for the highly dynamic road networks(TL-CkNN), which maintain the reuslt periodically for all the queries registerd in the system, use data updates to prune the expansion tree, then based on the pruned expansion tree continue to result recompuation, thereby reduced the duplication of road network expansion. Experiment results show this algorithm has better performance than other algorithms in the highly dynamic road networks.
引文
[1]徐明,曹建农,彭伟.移动计算技术[M].清华大学出版社,2008.
[2]周傲英,杨彬,金澈清,等.基于位置的服务：架构与进展[J].计算机学报,2011,34(7)：1155-1171.
[3]Fischer C, Gellersen H. Location and navigation support for emergency responders:A survey[J]. IEEE Pervasive Computing,2010,9(1):38-47.
[4]谢幸,孟小峰.基于位置的服务[J].中国计算机学会通讯,2010,6(6)：7-10.
[5]Zhang J, Zhu M, Papadias D, Tao Y, and Lee D L. Location-based spatial queries[C]//In Proc.SIGMOD,2003:255-267.
[6]Guttman. R-Trees:A Dynamic Index Structure for Spatial Searching[C]//Proceedings of the ACM Intentional Conference on Management of Data,SIGMOD,1984:47-57.
[7]Tayeb J, Ulusoy O, Wolfson O. A quadtree-based dynamic attribute indexing method[J]. The Computer Journal,1998,41(3):185-200.
[8]Saltenis S, Jensen C, Leutenegger S, et al. Indexing the positions of continuously moving objects[C]//Proceedings of the International Conference on Management of Data, SIGMOD, 2000:331-342.
[9]Tao Y, Papadias D, Sun J. The TPR*-tree:an optimized spatio-temporal access method for predictive queries[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment,2003:790-801.
[10]Yiu M L, Tao Y, Mamoulis N. The B dual-Tree:indexing moving objects by space filling curves in the dual space[J]. The VLDB Journal,2008,17(3):379-400.
[11]Jensen C S, Lin D, Ooi B C. Query and update efficient B+-tree based indexing of moving objects[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:768-779.
[12]Frentzos E. Indexing objects moving on fixed networks[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2003:289-305.
[13]De Almeida V T, Guting R H. Indexing the trajectories of moving objects in networks[J]. Geolnformatica,2005,9(1):33-60.
[14]Jian-Chao G U O J F W, Li-Hua D H Y Y A N. Indexing Scheme of Moving Objects on Fixed Networks[J]. Computer Science,2006,7:018.
[15]方颖,曹加恒,黄敏,等.支持固定网络中频繁更新的移动对象混合索引模型[J].小型微型计算机系统,2009,30(1)：50-53.
[16]Meng X, Ding Z. DSTTMOD:A future trajectory based moving objects database[C]//Database and Expert Systems Applications. Springer Berlin Heidelberg,2003: 444-453.
[17]Kolahdouzan M R, Shahabi C. Continuous k-nearest neighbor queries in spatial network databases[C]//Proc. of STDBM.2004,4.
[18]Kolahdouzan M R, Shahabi C. Alternative solutions for continuous k nearest neighbor queries in spatial network databases[J]. Geolnformatica,2005,9(4):321-341.
[19]孙冬璞,郝忠孝.局部范围受限的多类型最近邻查询[J].计算机研究与发展,2009,46(6)：1036-1042.
[20]廖巍,熊伟,王钧,等.可伸缩的增量连续k近邻查询处理[J].软件学报,2007,18(2)：268-278.
[21]廖巍,父秋云,陈宏盛,等.基于扩展时空距离度量的连续k近邻查询方法[J].国防科技大学学报,2007,29(1)：81-85.
[22]王淼,郝忠孝.基于动态创建局部Voronoi图的连续近邻查询[J].计算机应用研究,2008,25(9)：2771-2774.
[23]Kolahdouzan M, Shahabi C. Voronoi-based k nearest neighbor search for spatial network databases[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:840-851.
[24]Mouratidis K, Papadias D, Bakiras S, et al. A threshold-based algorithm for continuous monitoring of k nearest neighbors[J]. Knowledge and Data Engineering, IEEE Transactions on,2005,17(11):1451-1464.
[25]邹永贵,宋强,杨寓平.MOQ-QR:基于QR-树的连续K近邻查询算法研究[J].计算机应用研究,2010(010)：3676-3679.
[26]卢乘亮,刘娜.路网中移动对象快照k近邻查询处理[J].计算机应用,2011,31(11).
[27]Xuan K, Zhao G, Taniar D, et al. Constrained range search query processing on road networks[J]. Concurrency and Computation:Practice and Experience,2011,23(5):491-504.
[28]廖巍,吴晓平,严承华,等.多用户连续k近邻查询多线程处理技术研究[J].计算机应用,2009,29(7)：1861-1864.
[29]赵亮,陈荦,景宁,等.道路网中的移动对象连续K近邻查询[J].计算机学报,2010,8：1396-1404.
[30]Huang Y K, Chen Z W, Lee C. Continuous k-nearest neighbor query over moving objects in road networks[M]//Advances in Data and Web Management. Springer Berlin Heidelberg, 2009:27-38.
[31]郝兴,王凌,孟小峰.一种道路网络中移动对象的k近邻多查询理算法[J].计算机研究与发展,2007,44：113-118.
[32]梁茹冰,刘琼.公路网移动终端的KNN查询技术[J].华南理工大学学报(自然科学版),2012,40(1)：138-145.
[33]Khayati M, Akaichi J. Incremental approach for Continuous k-Nearest Neighbours queries on road[J]. International journal of intelligent information and database systems,2008,2(2):204-221.
[34]许林,李清泉,杨必胜.一种基于道路网的移动对象的位置索引与邻近查询方法[J].测绘学报,2010,39(3)：316-321.
[35]Shahabi C, Kolahdouzan M R, Sharifzadeh M. A road network embedding technique for k-nearest neighbor search in moving object databases[J]. Geolnformatica,2003,7(3): 255-273.
[36]Mouratidis K, Yiu M L, Papadias D, et al. Continuous nearest neighbor monitoring in road networks[C]//Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment,2006:43-54.
[37]Huang Y K, Chen Z W, Lee C. Continuous k-nearest neighbor query over moving objects in road networks[M]//Advances in Data and Web Management. Springer Berlin Heidelberg, 2009:27-38.
[38]牛剑光,陈荦,赵亮,等.高度动态环境下移动对象连续K近邻查询算法[J].计算机科学,2011,38(3)：182-186.
[39]Jensen C S, Kolarvr J, Pedersen T B, et al. Nearest neighbor queries in road networks[C]//Proceedings of the 11th ACM international symposium on Advances in geographic information systems. ACM,2003:1-8.
[40]Yiu M L, Mamoulis N, Papadias D. Aggregate nearest neighbor queries in road networks[J]. Knowledge and Data Engineering, IEEE Transactions on,2005,17(6):820-833.
[41]赵亮,景宁，陈荦,等.面向多核多线程的移动对象连续K近邻查询[J].软件学报,2011,22(8).
[42]Khayati M, Akaichi J. Incremental approach for Continuous k-Nearest Neighbours queries on road[J]. International journal of intelligent information and database systems,2008,2(2): 204-221.
[43]Hu H, Lee D L, Xu J. Fast nearest neighbor search on road networks[M]//Advances in Database Technology-EDBT 2006. Springer Berlin Heidelberg,2006:186-203.
[44]Mokbel M F, Xiong X, Aref W G. SINA:scalable incremental processing of continuous queries in spatio-temporal databases[C]//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM,2004:623-634.
[45]Xiong X, Mokbel M F, Aref W G. Sea-cnn:Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases[C]//Data Engineering,2005.ICDE 2005. Proceedings.21st International Conference on. IEEE,2005:643-654.
[46]Yu X, Pu K Q, Koudas N. Monitoring k-nearest neighbor queries over moving objects[C]//Data Engineering,2005. ICDE 2005. Proceedings.21st International Conference on. IEEE,2005:631-642.
[47]Mouratidis K, Papadias D, Hadjieleftheriou M. Conceptual partitioning:an efficient method for continuous nearest neighbor monitoring[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM,2005:634-645.
[48]Kolahdouzan M, Shahabi C. Voronoi-based k nearest neighbor search for spatial network databases[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:840-851.
[49]Huang X, Jensen C S, Saltenis S. The islands approach to nearest neighbor querying in spatial networks[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2005:73-90.
[50]De Almeida V T, Guting R H. Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases[C]//Proceedings of the 2006 ACM symposium on Applied computing. ACM,2006:58-62.
[51]Mouratidis K, Yiu M L, Papadias D, et al. Continuous nearest neighbor monitoring in road networks[C]//Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment,2006:43-54.
[52]Demiryurek U, Banaei-Kashani F, Shahabi C. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2009:25-43.
[53]Brinkhoff T. A Framework for Generating Network-Based Moving Objects[J]. Geolnformatica,2002,6(2):153-180.
[2]周傲英,杨彬,金澈清,等.基于位置的服务：架构与进展[J].计算机学报,2011,34(7)：1155-1171.
[3]Fischer C, Gellersen H. Location and navigation support for emergency responders:A survey[J]. IEEE Pervasive Computing,2010,9(1):38-47.
[4]谢幸,孟小峰.基于位置的服务[J].中国计算机学会通讯,2010,6(6)：7-10.
[5]Zhang J, Zhu M, Papadias D, Tao Y, and Lee D L. Location-based spatial queries[C]//In Proc.SIGMOD,2003:255-267.
[6]Guttman. R-Trees:A Dynamic Index Structure for Spatial Searching[C]//Proceedings of the ACM Intentional Conference on Management of Data,SIGMOD,1984:47-57.
[7]Tayeb J, Ulusoy O, Wolfson O. A quadtree-based dynamic attribute indexing method[J]. The Computer Journal,1998,41(3):185-200.
[8]Saltenis S, Jensen C, Leutenegger S, et al. Indexing the positions of continuously moving objects[C]//Proceedings of the International Conference on Management of Data, SIGMOD, 2000:331-342.
[9]Tao Y, Papadias D, Sun J. The TPR*-tree:an optimized spatio-temporal access method for predictive queries[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment,2003:790-801.
[10]Yiu M L, Tao Y, Mamoulis N. The B dual-Tree:indexing moving objects by space filling curves in the dual space[J]. The VLDB Journal,2008,17(3):379-400.
[11]Jensen C S, Lin D, Ooi B C. Query and update efficient B+-tree based indexing of moving objects[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:768-779.
[12]Frentzos E. Indexing objects moving on fixed networks[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2003:289-305.
[13]De Almeida V T, Guting R H. Indexing the trajectories of moving objects in networks[J]. Geolnformatica,2005,9(1):33-60.
[14]Jian-Chao G U O J F W, Li-Hua D H Y Y A N. Indexing Scheme of Moving Objects on Fixed Networks[J]. Computer Science,2006,7:018.
[15]方颖,曹加恒,黄敏,等.支持固定网络中频繁更新的移动对象混合索引模型[J].小型微型计算机系统,2009,30(1)：50-53.
[16]Meng X, Ding Z. DSTTMOD:A future trajectory based moving objects database[C]//Database and Expert Systems Applications. Springer Berlin Heidelberg,2003: 444-453.
[17]Kolahdouzan M R, Shahabi C. Continuous k-nearest neighbor queries in spatial network databases[C]//Proc. of STDBM.2004,4.
[18]Kolahdouzan M R, Shahabi C. Alternative solutions for continuous k nearest neighbor queries in spatial network databases[J]. Geolnformatica,2005,9(4):321-341.
[19]孙冬璞,郝忠孝.局部范围受限的多类型最近邻查询[J].计算机研究与发展,2009,46(6)：1036-1042.
[20]廖巍,熊伟,王钧,等.可伸缩的增量连续k近邻查询处理[J].软件学报,2007,18(2)：268-278.
[21]廖巍,父秋云,陈宏盛,等.基于扩展时空距离度量的连续k近邻查询方法[J].国防科技大学学报,2007,29(1)：81-85.
[22]王淼,郝忠孝.基于动态创建局部Voronoi图的连续近邻查询[J].计算机应用研究,2008,25(9)：2771-2774.
[23]Kolahdouzan M, Shahabi C. Voronoi-based k nearest neighbor search for spatial network databases[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:840-851.
[24]Mouratidis K, Papadias D, Bakiras S, et al. A threshold-based algorithm for continuous monitoring of k nearest neighbors[J]. Knowledge and Data Engineering, IEEE Transactions on,2005,17(11):1451-1464.
[25]邹永贵,宋强,杨寓平.MOQ-QR:基于QR-树的连续K近邻查询算法研究[J].计算机应用研究,2010(010)：3676-3679.
[26]卢乘亮,刘娜.路网中移动对象快照k近邻查询处理[J].计算机应用,2011,31(11).
[27]Xuan K, Zhao G, Taniar D, et al. Constrained range search query processing on road networks[J]. Concurrency and Computation:Practice and Experience,2011,23(5):491-504.
[28]廖巍,吴晓平,严承华,等.多用户连续k近邻查询多线程处理技术研究[J].计算机应用,2009,29(7)：1861-1864.
[29]赵亮,陈荦,景宁,等.道路网中的移动对象连续K近邻查询[J].计算机学报,2010,8：1396-1404.
[30]Huang Y K, Chen Z W, Lee C. Continuous k-nearest neighbor query over moving objects in road networks[M]//Advances in Data and Web Management. Springer Berlin Heidelberg, 2009:27-38.
[31]郝兴,王凌,孟小峰.一种道路网络中移动对象的k近邻多查询理算法[J].计算机研究与发展,2007,44：113-118.
[32]梁茹冰,刘琼.公路网移动终端的KNN查询技术[J].华南理工大学学报(自然科学版),2012,40(1)：138-145.
[33]Khayati M, Akaichi J. Incremental approach for Continuous k-Nearest Neighbours queries on road[J]. International journal of intelligent information and database systems,2008,2(2):204-221.
[34]许林,李清泉,杨必胜.一种基于道路网的移动对象的位置索引与邻近查询方法[J].测绘学报,2010,39(3)：316-321.
[35]Shahabi C, Kolahdouzan M R, Sharifzadeh M. A road network embedding technique for k-nearest neighbor search in moving object databases[J]. Geolnformatica,2003,7(3): 255-273.
[36]Mouratidis K, Yiu M L, Papadias D, et al. Continuous nearest neighbor monitoring in road networks[C]//Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment,2006:43-54.
[37]Huang Y K, Chen Z W, Lee C. Continuous k-nearest neighbor query over moving objects in road networks[M]//Advances in Data and Web Management. Springer Berlin Heidelberg, 2009:27-38.
[38]牛剑光,陈荦,赵亮,等.高度动态环境下移动对象连续K近邻查询算法[J].计算机科学,2011,38(3)：182-186.
[39]Jensen C S, Kolarvr J, Pedersen T B, et al. Nearest neighbor queries in road networks[C]//Proceedings of the 11th ACM international symposium on Advances in geographic information systems. ACM,2003:1-8.
[40]Yiu M L, Mamoulis N, Papadias D. Aggregate nearest neighbor queries in road networks[J]. Knowledge and Data Engineering, IEEE Transactions on,2005,17(6):820-833.
[41]赵亮,景宁，陈荦,等.面向多核多线程的移动对象连续K近邻查询[J].软件学报,2011,22(8).
[42]Khayati M, Akaichi J. Incremental approach for Continuous k-Nearest Neighbours queries on road[J]. International journal of intelligent information and database systems,2008,2(2): 204-221.
[43]Hu H, Lee D L, Xu J. Fast nearest neighbor search on road networks[M]//Advances in Database Technology-EDBT 2006. Springer Berlin Heidelberg,2006:186-203.
[44]Mokbel M F, Xiong X, Aref W G. SINA:scalable incremental processing of continuous queries in spatio-temporal databases[C]//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM,2004:623-634.
[45]Xiong X, Mokbel M F, Aref W G. Sea-cnn:Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases[C]//Data Engineering,2005.ICDE 2005. Proceedings.21st International Conference on. IEEE,2005:643-654.
[46]Yu X, Pu K Q, Koudas N. Monitoring k-nearest neighbor queries over moving objects[C]//Data Engineering,2005. ICDE 2005. Proceedings.21st International Conference on. IEEE,2005:631-642.
[47]Mouratidis K, Papadias D, Hadjieleftheriou M. Conceptual partitioning:an efficient method for continuous nearest neighbor monitoring[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM,2005:634-645.
[48]Kolahdouzan M, Shahabi C. Voronoi-based k nearest neighbor search for spatial network databases[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:840-851.
[49]Huang X, Jensen C S, Saltenis S. The islands approach to nearest neighbor querying in spatial networks[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2005:73-90.
[50]De Almeida V T, Guting R H. Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases[C]//Proceedings of the 2006 ACM symposium on Applied computing. ACM,2006:58-62.
[51]Mouratidis K, Yiu M L, Papadias D, et al. Continuous nearest neighbor monitoring in road networks[C]//Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment,2006:43-54.
[52]Demiryurek U, Banaei-Kashani F, Shahabi C. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg,2009:25-43.
[53]Brinkhoff T. A Framework for Generating Network-Based Moving Objects[J]. Geolnformatica,2002,6(2):153-180.