Solving Reverse k-Nearest Queries on Road Networks with the GPU

• Yago Diez ^[1] ; Marta Fort ^[1] ; J. Antoni Sellarès ^[1]
  1. [1] Universitat de Girona

     Universitat de Girona

     Gerona, España

     
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 117-124
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • We present a GPU-based approach for computing discretized distance functions on road networks. As applications, we provide algorithms for computing discrete Order-k Nearest Neighbor diagrams and for approximately solving (Bichromatic) Reverse k-Nearest Neighbor queries on road networks. Finally, we present experimental results obtained with the implementation of our algorithms that demonstrate the effectiveness and efficiency of our approach