基于预计算的路网k路径近邻查询研究
|
摘要
随着卫星全球定位系统和无线通讯技术等科学技术的快速发展,已经能够跟踪并记录移动对象的位置信息。移动对象在地理信息系统、移动计算和基于位置的电子商务等方面发挥着重要应用,各种查询方法不断提出。k路径近邻查询(k-PNN)作为一种新的查询方法,对用户的实时查询要准确快速的给出回答,因此,降低查询代价成为该查询方法的关键问题。Zaiben Chen等人提出了最优路网扩展(BNE)方法。本文中,运用预计算思想减少路网扩展代价,旨在进一步提高查询效率。
首先,运用预计算思想提出了基于NN lists的BNNL算法,运用双向Dijkstra算法向在获得用户当前位置和目的地节点之间最短路径的基础上,预计算路网节点的m近邻信息,运用优先队列进行优化处理。对于路口节点的近邻不需要路网扩展得到,只需进行简单读取,从而提高了BNNL算法对路网k路径近邻的查询效率。
其次,Voronoi图不仅对路网进行了简化处理,还预计算了路网中部分节点之间的最短距离,减少节点扩展次数,从而提高近邻查找效率。本文提出的基于Voronoi图的路网k路径近邻查询方法(VBk-PNN)。将相同的路网Voronoi多边形在用户当前位置和目的地节点之间最短路径上的路口节点作为一个集合来进行扩展。并运用优先队列进行优化处理,最终得到正确的k路径近邻。
最后,通过实验将上述提出的两种方法和已有的最优路网扩展方法(BNE)进行实验比较,结果表明BNNL算法和VBk-PNN算法的执行效率均优于BNE算法。
With the rapid development of global positioning system and communica- tion technology, we can record the positions of moving objects. Various queries of moving objects are provided for applications of GIS, location-based commerce and mobile computing. The k-Path Nearest Neighbor query (k-PNN) as a new query require efficiently answer user’s requirements. Thus, algorithms for improving search speed become important; Best-first Network Expansion (BNE) algorithm is proposed by Zaiben Chen et al. In this paper, we employ the idea of pre-computation to enhance the k-PNN query speed.
Firstly, the Based on NN lists (BNNL) algorithm based on the precomp- uted NN lists is proposed depending on the pre-computation idea, using a bi-directional Dijkstra search scheme to acquire the current shortest path to destination, then, the nodes in the shortest path are got. At last, these nodes' m nearest neighbors are optimized by a priority queue in order to get the correct k-PNN. Because these nodes' nearest neighbors don’t need to search and read from a list quickly, the query speed of BNNL algorithm can be more efficient about k-PNN query.
Secondly, Voronoi diagram not only simplize the road network, but also pre-compute some nodes' shortest path. In order to improve the query speed by decline the number of node search nearest neighbors. Thus, the Voronoi-Based k-Path Nearest Neighbor (VBk-PNN) algorithm based on the pre-computed. At last, some nodes in same NVP as a set to search these nodes' nearest neighbor, then these nodes' nearest neighbors are optimized by a priority queue in order to get the correct k-PNN.
Finally, those based on pre-computation methods of k-PNN proposed above are compared with the existing method of BNE. As a result, the performance of BNNL and VBk-PNN algorithms are more efficient about k-PNN query speed than BNE.
首先,运用预计算思想提出了基于NN lists的BNNL算法,运用双向Dijkstra算法向在获得用户当前位置和目的地节点之间最短路径的基础上,预计算路网节点的m近邻信息,运用优先队列进行优化处理。对于路口节点的近邻不需要路网扩展得到,只需进行简单读取,从而提高了BNNL算法对路网k路径近邻的查询效率。
其次,Voronoi图不仅对路网进行了简化处理,还预计算了路网中部分节点之间的最短距离,减少节点扩展次数,从而提高近邻查找效率。本文提出的基于Voronoi图的路网k路径近邻查询方法(VBk-PNN)。将相同的路网Voronoi多边形在用户当前位置和目的地节点之间最短路径上的路口节点作为一个集合来进行扩展。并运用优先队列进行优化处理,最终得到正确的k路径近邻。
最后,通过实验将上述提出的两种方法和已有的最优路网扩展方法(BNE)进行实验比较,结果表明BNNL算法和VBk-PNN算法的执行效率均优于BNE算法。
With the rapid development of global positioning system and communica- tion technology, we can record the positions of moving objects. Various queries of moving objects are provided for applications of GIS, location-based commerce and mobile computing. The k-Path Nearest Neighbor query (k-PNN) as a new query require efficiently answer user’s requirements. Thus, algorithms for improving search speed become important; Best-first Network Expansion (BNE) algorithm is proposed by Zaiben Chen et al. In this paper, we employ the idea of pre-computation to enhance the k-PNN query speed.
Firstly, the Based on NN lists (BNNL) algorithm based on the precomp- uted NN lists is proposed depending on the pre-computation idea, using a bi-directional Dijkstra search scheme to acquire the current shortest path to destination, then, the nodes in the shortest path are got. At last, these nodes' m nearest neighbors are optimized by a priority queue in order to get the correct k-PNN. Because these nodes' nearest neighbors don’t need to search and read from a list quickly, the query speed of BNNL algorithm can be more efficient about k-PNN query.
Secondly, Voronoi diagram not only simplize the road network, but also pre-compute some nodes' shortest path. In order to improve the query speed by decline the number of node search nearest neighbors. Thus, the Voronoi-Based k-Path Nearest Neighbor (VBk-PNN) algorithm based on the pre-computed. At last, some nodes in same NVP as a set to search these nodes' nearest neighbor, then these nodes' nearest neighbors are optimized by a priority queue in order to get the correct k-PNN.
Finally, those based on pre-computation methods of k-PNN proposed above are compared with the existing method of BNE. As a result, the performance of BNNL and VBk-PNN algorithms are more efficient about k-PNN query speed than BNE.
引文
1 O. Wolfson, B. Xu, L. Jiang, S. Chamberlam. Moving Objects Databases: Issues and Solutions. Proceedings of the 1998 10th International Conference on Scientific and Statistical Database Management, Capri, Italy. 1998:111-122
2 O. Wolfson, L. Jiang, A. P. Sistla, S. Chamberlain, N. Rishe, M. Deng. Databases for Tracking Mobile Units in Real Time. Proceedings of the 7th International Conference on Database Theory, Jerusalem, Israel. 1999:169-186
3 O. Wolson. Moving Objects Information Management: The Database Challenge. Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems, Caesarea, Israel. 2002:75-89
4 O. Wolfson, S. Chamberlain, S. Dao, L. Jiang. Location Management in Moving Objects Databases. Proceedings of the 2nd International Workshop on Satellite-based Information Services, Budapest, Hungary. 1997:7-14
5 A. P. Sistla, O. Wolfson, S. Chamberlain, S. Dao. Modeling and Querying Moving Objects. Proceedings of the 13th International Conference on Date Engineering, Budapest, Hungary. 1997:422-432
6孟晓峰,周龙骥,王珊.数据库技术发展趋势.软件学报. 2004, 15(12):1822-1835
7卢炎生,陈刚.基于公路网的移动对象数据库数据模型.计算机工程. 2007, 33(5): 36-40
8邰滢滢,邰刚.基于拓扑算子的多尺度GIS显示方法.计算机工程. 2009, 22(35): 281-282
9 F. Korn, S. Muthukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. Proceedings of the 2000 ACM SIGMOD, Texas, USA. 2000:201-212
10 W. Wu, F. Yang, C. Y. Chan, K. l. Tan. Continuous Reverse k-Nearest-Neighbour Monitoring. Proceedings of MDM, Beijing, China.2008:1-8
11 M. L. Yiu, N. Mamoulis, D. Papadias. Aggregatenearest Neighbor Queries in Road Networks. IEEE Trans. on Knowl. and Data Eng.. 2005. 17(6):820-833.
12 D. Papadias, Q. Shen, Y. Tao, K. Mouratidis.Group Nearest Neighbor Queries. Proc- eedings of the 20th International Conference on Data Engineering. Boston, Massachusetts. 2004: 301-311.
13 Z. Song,N. Roussopoulos. k-Nearest Neighbor Search for Moving Query Point. Proceedings of the SSTD, Redondo Beach, CA, USA. 2001: 79-96
14 Y. Tao, D. Papadias. Time-Parameterized Queries in Spatio-Temporal Databases. Proceedings of the ACM SIGMOD, Madison, Wisconsin, USA. 2002: 334-345
15 J. Zhang, D. Papadias. Location-Based Spatial Queries. 2003 ACM SIGMOD Intemational Conference on Management of Data, San Diego, CA, United States. 2003: 443-454
16 K. H. Ng, H. W. Leong. Multi Point Queries in Large Spatial Databases. Proceedings of the Third IASTED Intemational Conference, Phuket, Thailand, 2007: 408-413
17 Y. Tao, D. Papadias. Q. Shen. Continuous Nearest Neighbor Search. In VLDB, Hong Kong, China. 2002: 287-298
18 G. S. Iwerks, H. Samet and K. Smith. Continuous k-Nearest Neighbor Queries for Continuously Moving Points with Updates. Proceedings of VLDB, Berlin, Germany, September 2003: 512-523
19 C. Shahabi, M. Kolffdouzan, M. Sharifzadeh. A Road Network Embedding Technique for k-Nearest Neighbor Search in Moving Object Databases. Geolnformatica, 2003, 7(3): 255-273
20 D. Papadias, J. Zhang, N. Mamoulis and Y. Tao. Query Processing in Spatial Network Databases. Proceedings of VLDB, Berlin, Germany, 2003: 802-813
21 M. Kolahdouzan, C.Shahabi.Voronoi-based k Nearest Neighbor Search for Spatial Network Databases. Proceedings of the Thirtieth International Conference on Very Large Data Bases.Toronto, Canada. 2004: 840-851
22 M. Kolahdouzan, C. Shahabi. Continuous k Nearest Neighbor Queries in Spatial Network Databases. Proceedings of the Second Workshop on Spatio-Temporal Database Management. Toronto, Canada. 2004: 33-40
23王淼.基于Voronoi图的最近邻查询的研究.软件时空. 2008, (24)11-3: 259-263
24李晓丽,何云斌.基于网络Voronoi图的道路网络连续k近邻查询.信息技术.2007, 12 : 103-105
25王淼,郝忠孝.基于动态创建局部Voronoi图的连续近邻查询.计算机应用研究。2008, (25) 9: 2771-2774
26王晓东,廖士中.基于Voronoi图的定性路径.计算机工程与应用. 2009, 45(20):193-196
27 X. Huang, C.S. Jensen and S. Saltenis. The Islands Approach to Nearest Neighbor Querying in Spatial Networks. Proceedings of SSTD, Heidelberg. 2005.LNCS,3633: 73-90
28 F. Mohamed. Continuous Query Processing in Spatio-temporal Databases. Proceedings of EDBT. 2004: 100-111
29 K. Mourtidis, M. Hadjieleftheriou, D. Papadias. Conceptual Partitioning:An Efficient Method for Continuous Nearest Neighbor Monitoring. Proceedings of SlGMOD, Baltimore, Maryland, USA.2005: 634-645
30 K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis. Continuous Nearest Neighbor Monitoring in Road Networks. Proceedings of VLDB, 2006: 43-54
31廖威,熊伟,王钧,景宁,钟志农.可伸缩的增量连续k近邻查询处理.软件学报. 2007,18(2): 268-278
32 X. Huang, C.S. Jensen, L. Hua and S. Saltenis. S-grid: A Versatile Approach to Effcient Query Processings of Spatial Networks. In SSTD, 2007:93-111
33 J. Feng, L. Y. WU, Y. L. Zhu. Continuous k-Nearest Neighbor Search under Mobile Environment. AIWeb/WAIM 2007, LNCS 4505: 566-573
34 Y. J. Gao, Gencai Chen, Qing Li, Chun Li and Chun Chen.Constrained k-Nearest Neighbor Query Processing over Moving Object Trajectories. Verlag Berlin Heidelberg. Processings of DASFAA 2008, LNCS 4947: 635-643
35 S. Nutanong, R. Zhang, E. Tanin, and L. Kulik. The V*-Diagram: A Query Dependent Approach to Moving kNN Queries. Proceedings of VLDB, 2008: 1095-1106.
36 L. Kulik and E. Tanin. Incremental Rank Updates for Moving Query Points. In GIScience, Berlin Heidelberg 2006: 251-268
37 J. Zhang, M. Zhu, D. Papadias, Y. Tao and D. L. Lee.Location-based Spatial Queries. Processings of SIGMOD.San Diego, California, USA. 2003. 443-454
38 H. Samet. k-Nearest Neighbor Finding Using MaxNearestDist. IEEE Transactions On Pattern Analysis And Machine Interllogence. 2008, (30)2:243-252
39 G. R. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. Processings of ACM Trans. Database Syst.. 1999, 24(2): 265-318
40 N. Roussopoulos, S. Kelley, and F. Vincent. Nearest Neighbor Queries. Proceedings of SIGMOD, Califina, USA. 1995: 71-79
41 C.Ken, K. Lee, W. C. Lee and B. Zheng. Fast Object Search on Road Networks. Processings of ACM.EDBT. Russia, Saint Petersburg. 2009: 187-203
42 Y. J. Gao, B. Zheng, W. C. Lee and G. Chen.Continuous Visible Nearest Neighbor Queries. Processings of ACM.EDBT. Saint Petersburg, Russia.2009: 144-155
43 Y. K. Huang, Z.W. Chen and C. Lee. Continuous k-Nearest Neighbor Query over Moving Objects in Road Networks. Processings of APWeb/WAIM 2009, LNCS 5446, Berlin Heidelberg 2009:27-38
44 U. Demiryurek, B. K. Farnoush and C. Shahabi. Efficient Continuous Nearest Neighbor Query in Spatial Networks using Euclidean Restriction. Processings of SSTD, Aalborg, Denmark. 2009:1-18
45 G. Li, P. Fan, Y. H. Li and J. Du. An Efficient Technique for Continuous k-Nearest Neighbor Query Processing on Moving Objects in a Road Network. Processings of The 10th IEEE CIT 2010:627-634
46 K. Zheng, P. C. Fung and Xiaofang Zhou. K-Nearest Neighbor Search for Fuzzy Objects. Processings of SIGMOD. Indianapolis, Indiana, USA.2010:699-710
47 S. Shekhar and J. S. Yoo. Processing In-route Nearest Neighbor Queries: a comparison of alternative approaches. Proceedings of GIS, New Orleans, Louisiana, USA. 2003: 9-16
48 J. S. Yoo and S. Shekhar. In-route Nearest Neighbor Queries. Geo Informatica, 2005, 9(2): 117-137
49 Zaiben Chen, Tao Heng, Xiaofang Shen etal.Monitoring Path Nearest Neighbor inRoad Networks. Proceedings of the 35th SIGMOD international conference on Management of data. Rhode Island, USA. 2009:591-602
50 E. W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerische Math, 1959.1:269-271
51埃克尔. Java编程思想.北京:机械工业出版社, 2007:46-59
52霍斯特曼. Java2核心技术卷.北京:机械工业出版社, 2008:534-588
2 O. Wolfson, L. Jiang, A. P. Sistla, S. Chamberlain, N. Rishe, M. Deng. Databases for Tracking Mobile Units in Real Time. Proceedings of the 7th International Conference on Database Theory, Jerusalem, Israel. 1999:169-186
3 O. Wolson. Moving Objects Information Management: The Database Challenge. Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems, Caesarea, Israel. 2002:75-89
4 O. Wolfson, S. Chamberlain, S. Dao, L. Jiang. Location Management in Moving Objects Databases. Proceedings of the 2nd International Workshop on Satellite-based Information Services, Budapest, Hungary. 1997:7-14
5 A. P. Sistla, O. Wolfson, S. Chamberlain, S. Dao. Modeling and Querying Moving Objects. Proceedings of the 13th International Conference on Date Engineering, Budapest, Hungary. 1997:422-432
6孟晓峰,周龙骥,王珊.数据库技术发展趋势.软件学报. 2004, 15(12):1822-1835
7卢炎生,陈刚.基于公路网的移动对象数据库数据模型.计算机工程. 2007, 33(5): 36-40
8邰滢滢,邰刚.基于拓扑算子的多尺度GIS显示方法.计算机工程. 2009, 22(35): 281-282
9 F. Korn, S. Muthukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. Proceedings of the 2000 ACM SIGMOD, Texas, USA. 2000:201-212
10 W. Wu, F. Yang, C. Y. Chan, K. l. Tan. Continuous Reverse k-Nearest-Neighbour Monitoring. Proceedings of MDM, Beijing, China.2008:1-8
11 M. L. Yiu, N. Mamoulis, D. Papadias. Aggregatenearest Neighbor Queries in Road Networks. IEEE Trans. on Knowl. and Data Eng.. 2005. 17(6):820-833.
12 D. Papadias, Q. Shen, Y. Tao, K. Mouratidis.Group Nearest Neighbor Queries. Proc- eedings of the 20th International Conference on Data Engineering. Boston, Massachusetts. 2004: 301-311.
13 Z. Song,N. Roussopoulos. k-Nearest Neighbor Search for Moving Query Point. Proceedings of the SSTD, Redondo Beach, CA, USA. 2001: 79-96
14 Y. Tao, D. Papadias. Time-Parameterized Queries in Spatio-Temporal Databases. Proceedings of the ACM SIGMOD, Madison, Wisconsin, USA. 2002: 334-345
15 J. Zhang, D. Papadias. Location-Based Spatial Queries. 2003 ACM SIGMOD Intemational Conference on Management of Data, San Diego, CA, United States. 2003: 443-454
16 K. H. Ng, H. W. Leong. Multi Point Queries in Large Spatial Databases. Proceedings of the Third IASTED Intemational Conference, Phuket, Thailand, 2007: 408-413
17 Y. Tao, D. Papadias. Q. Shen. Continuous Nearest Neighbor Search. In VLDB, Hong Kong, China. 2002: 287-298
18 G. S. Iwerks, H. Samet and K. Smith. Continuous k-Nearest Neighbor Queries for Continuously Moving Points with Updates. Proceedings of VLDB, Berlin, Germany, September 2003: 512-523
19 C. Shahabi, M. Kolffdouzan, M. Sharifzadeh. A Road Network Embedding Technique for k-Nearest Neighbor Search in Moving Object Databases. Geolnformatica, 2003, 7(3): 255-273
20 D. Papadias, J. Zhang, N. Mamoulis and Y. Tao. Query Processing in Spatial Network Databases. Proceedings of VLDB, Berlin, Germany, 2003: 802-813
21 M. Kolahdouzan, C.Shahabi.Voronoi-based k Nearest Neighbor Search for Spatial Network Databases. Proceedings of the Thirtieth International Conference on Very Large Data Bases.Toronto, Canada. 2004: 840-851
22 M. Kolahdouzan, C. Shahabi. Continuous k Nearest Neighbor Queries in Spatial Network Databases. Proceedings of the Second Workshop on Spatio-Temporal Database Management. Toronto, Canada. 2004: 33-40
23王淼.基于Voronoi图的最近邻查询的研究.软件时空. 2008, (24)11-3: 259-263
24李晓丽,何云斌.基于网络Voronoi图的道路网络连续k近邻查询.信息技术.2007, 12 : 103-105
25王淼,郝忠孝.基于动态创建局部Voronoi图的连续近邻查询.计算机应用研究。2008, (25) 9: 2771-2774
26王晓东,廖士中.基于Voronoi图的定性路径.计算机工程与应用. 2009, 45(20):193-196
27 X. Huang, C.S. Jensen and S. Saltenis. The Islands Approach to Nearest Neighbor Querying in Spatial Networks. Proceedings of SSTD, Heidelberg. 2005.LNCS,3633: 73-90
28 F. Mohamed. Continuous Query Processing in Spatio-temporal Databases. Proceedings of EDBT. 2004: 100-111
29 K. Mourtidis, M. Hadjieleftheriou, D. Papadias. Conceptual Partitioning:An Efficient Method for Continuous Nearest Neighbor Monitoring. Proceedings of SlGMOD, Baltimore, Maryland, USA.2005: 634-645
30 K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis. Continuous Nearest Neighbor Monitoring in Road Networks. Proceedings of VLDB, 2006: 43-54
31廖威,熊伟,王钧,景宁,钟志农.可伸缩的增量连续k近邻查询处理.软件学报. 2007,18(2): 268-278
32 X. Huang, C.S. Jensen, L. Hua and S. Saltenis. S-grid: A Versatile Approach to Effcient Query Processings of Spatial Networks. In SSTD, 2007:93-111
33 J. Feng, L. Y. WU, Y. L. Zhu. Continuous k-Nearest Neighbor Search under Mobile Environment. AIWeb/WAIM 2007, LNCS 4505: 566-573
34 Y. J. Gao, Gencai Chen, Qing Li, Chun Li and Chun Chen.Constrained k-Nearest Neighbor Query Processing over Moving Object Trajectories. Verlag Berlin Heidelberg. Processings of DASFAA 2008, LNCS 4947: 635-643
35 S. Nutanong, R. Zhang, E. Tanin, and L. Kulik. The V*-Diagram: A Query Dependent Approach to Moving kNN Queries. Proceedings of VLDB, 2008: 1095-1106.
36 L. Kulik and E. Tanin. Incremental Rank Updates for Moving Query Points. In GIScience, Berlin Heidelberg 2006: 251-268
37 J. Zhang, M. Zhu, D. Papadias, Y. Tao and D. L. Lee.Location-based Spatial Queries. Processings of SIGMOD.San Diego, California, USA. 2003. 443-454
38 H. Samet. k-Nearest Neighbor Finding Using MaxNearestDist. IEEE Transactions On Pattern Analysis And Machine Interllogence. 2008, (30)2:243-252
39 G. R. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. Processings of ACM Trans. Database Syst.. 1999, 24(2): 265-318
40 N. Roussopoulos, S. Kelley, and F. Vincent. Nearest Neighbor Queries. Proceedings of SIGMOD, Califina, USA. 1995: 71-79
41 C.Ken, K. Lee, W. C. Lee and B. Zheng. Fast Object Search on Road Networks. Processings of ACM.EDBT. Russia, Saint Petersburg. 2009: 187-203
42 Y. J. Gao, B. Zheng, W. C. Lee and G. Chen.Continuous Visible Nearest Neighbor Queries. Processings of ACM.EDBT. Saint Petersburg, Russia.2009: 144-155
43 Y. K. Huang, Z.W. Chen and C. Lee. Continuous k-Nearest Neighbor Query over Moving Objects in Road Networks. Processings of APWeb/WAIM 2009, LNCS 5446, Berlin Heidelberg 2009:27-38
44 U. Demiryurek, B. K. Farnoush and C. Shahabi. Efficient Continuous Nearest Neighbor Query in Spatial Networks using Euclidean Restriction. Processings of SSTD, Aalborg, Denmark. 2009:1-18
45 G. Li, P. Fan, Y. H. Li and J. Du. An Efficient Technique for Continuous k-Nearest Neighbor Query Processing on Moving Objects in a Road Network. Processings of The 10th IEEE CIT 2010:627-634
46 K. Zheng, P. C. Fung and Xiaofang Zhou. K-Nearest Neighbor Search for Fuzzy Objects. Processings of SIGMOD. Indianapolis, Indiana, USA.2010:699-710
47 S. Shekhar and J. S. Yoo. Processing In-route Nearest Neighbor Queries: a comparison of alternative approaches. Proceedings of GIS, New Orleans, Louisiana, USA. 2003: 9-16
48 J. S. Yoo and S. Shekhar. In-route Nearest Neighbor Queries. Geo Informatica, 2005, 9(2): 117-137
49 Zaiben Chen, Tao Heng, Xiaofang Shen etal.Monitoring Path Nearest Neighbor inRoad Networks. Proceedings of the 35th SIGMOD international conference on Management of data. Rhode Island, USA. 2009:591-602
50 E. W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerische Math, 1959.1:269-271
51埃克尔. Java编程思想.北京:机械工业出版社, 2007:46-59
52霍斯特曼. Java2核心技术卷.北京:机械工业出版社, 2008:534-588