Local network Voronoi diagrams

ABSTRACT

Continuous queries in road networks have gained significant research interests due to advances in GIS and mobile computing. Consider the following scenario: "A driver uses a networked GPS navigator to monitor five nearest gas stations in a road network." The main challenge of processing such a moving query is how to efficiently monitor network distances of the k nearest and possible resultant objects. To enable result monitoring in real-time, researchers have devised techniques which utilize precomputed distances and results, e.g., the network Voronoi diagram (NVD). However, the main drawback of preprocessing is that it requires access to all data objects and network nodes, which means that it is not suitable for large datasets in many real life situations. The best existing method to monitor kNN results without precomputation relies on executions of snapshot queries at network nodes encountered by the query point. This method results in repetitive distance evaluation over the same or similar sets of nodes. In this paper, we propose a method called the local network Voronoi diagram (LNVD) to compute query answers for a small area around the query point. As a result, our method requires neither precomputation nor distance evaluation at every intersection. According to our extensive analysis and experimental results, our method significantly outperforms the best existing method in terms of data access and computation costs.

References

1. H.-J. Cho and C.-W. Chung. An efficient and scalable approach to CNN queries in a road network. In VLDB, pages 865--876, 2005.
2. U. Demiryurek, F. B. Kashani, and C. Shahabi. Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction. In SSTD, pages 25--43, 2009.
3. K. Deng, X. Zhou, H. T. Shen, S. W. Sadiq, and X. Li. Instance optimal query processing in spatial networks. VLDB J., 18(3):675--693, 2009.
4. E. W. Dijkstra. A note on two problems in connection with graphs. Numeriche Mathematik, 1:269--271, 1959.
5. M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596--615, 1987.
6. G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265--318, 1999.
7. M. R. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In VLDB, pages 840--851, 2004.
8. M. R. Kolahdouzan and C. Shahabi. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica, 9(4):321--341, 2005.
9. K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis. Continuous nearest neighbor monitoring in road networks. In VLDB, pages 43--54, 2006.
10. A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, Chichester, second edition, 2000.
11. A. Okabe, T. Satoh, T. Furuta, A. Suzuki, and K. Okano. Generalized network Voronoi diagrams: Concepts, computational methods, and applications. International Journal of Geographical Information Science, 22(9):965--994, 2008.
12. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In VLDB, pages 802--813, 2003.
13. S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, second edition, 2003.
14. H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In SIGMOD, pages 43--54, 2008.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms