GPU-based computation of distance functions on road networks with applications

ABSTRACT

We present a GPU-based algorithm for computing discretized distance functions on road networks. As applications, we provide algorithms for computing discrete Order-k Network Voronoi diagrams and for approximately solving k-Nearest Neighbor queries and Aggregate k-Nearest Neighbor queries on road networks. Finally, we present experimental results obtained with the implementation of our algorithms.

REFERENCES

• 1: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Victor Teixeira de Almeida , Ralf Hartmut Güting, Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141291]
• 3: E. Dijkstra. A note on two problems in connection with graphs. Numeriche Mathematik, 1: 269--271, 1959.
• 4: I. Fischer and C. Gotsman. Fast approximation of high-order Voronoi diagrams and distance transforms on the GPU. J. of Graphics Tools, 11(4): 39--60, 2006.
• 5: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007594]
• 6: S. L. Hakimi, M. Labbé and E. Schmeichel. The Voronoi partition of a network and its implications in location theory. ORSA Journal on Computing, 4: 412--417, 1992.
• 7: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 8: X. Huang, C. S. Jensen and S. Saltenis. The islands approach to nearest neighbor querying in spatial networks. In SSTD'05, pp 73--90, 2005.
• 9: Christian S. Jensen , Jan Kolářvr , Torben Bach Pedersen , Igor Timko, Nearest neighbor queries in road networks, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.1-8, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956677]
• 10: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 11: Mohammad R. Kolahdouzan , Cyrus Shahabi, Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases, Geoinformatica, v.9 n.4, p.321-341, December 2005 [doi>10.1007/s10707-005-4575-8]
• 12: M. D. Lieberman, J. Sankaranarayanan and H. Samet. A fast similarity join algorithm using graphics processing units. In ICDE'08, pp 1111--1120, 2008.
• 13: E. Martin. The graph voronoi diagram with applications. Networks, 36(3): 156--163, 2000.
• 14: A. Okabe, B. Boots, K. Sugihara and S. N. Chiu. Spatial tessellations: Concepts and applications of Voronoi diagrams. Probability and Statistics. Wiley, NYC, 2nd edition, 2000.
• 15: J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krger, A. E. Lefohn and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1): 80--113, 2007.
• 16: Dimitris Papadias , Jun Zhang , Nikos Mamoulis , Yufei Tao, Query processing in spatial network databases, Proceedings of the 29th international conference on Very large data bases, p.802-813, September 09-12, 2003, Berlin, Germany
• 17: P. Sanders and D. Schultes. Engineering fast route planning algorithms. In WEA'07, pp 23--36, 2007.
• 18: M. Segal and K. Akeley. The design of the OpenGL graphics interface, 1994.
• 19: D. Wagner and T. Willhalm. Speed-up techniques for shortest-path computations. In STACS'07, pp 23--36, 2007.
• 20: Man Lung Yiu , Nikos Mamoulis , Dimitris Papadias, Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.820-833, June 2005 [doi>10.1109/TKDE.2005.87]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
graphics hardware, proximity queries, road networks