Journal of Applied Information Science

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Transport Optimized Nearest Neighbor Query for Location Based Services


Affiliations
1 NIIT University, Neemrana, Rajasthan, India
     

   Subscribe/Renew Journal


Location Based Services are increasingly becoming popular due to increased usage of mobile devices by citizens seeking information on points-of-interest, travel routes, traffic conditions etc. We consider practical variants of the nearest neighbor problem on road networks, wherein the goal is to find the nearest point-of-interest from a query location. Here the notion of proximity is determined by the ease of reaching the point of interest via public transport. Using graphs modeling the road network and transport connectivity, efficient algorithms are presented.

Keywords

Nearest Neighbor Search, Computational Geometry, Road Networks, Shortest Path Problem, Location Based Services.
Subscription Login to verify subscription
User
Notifications
Font Size


  • Preparata, F. P., & Shamos, M. (1993). Computational Geometry: An Introduction, (1sted). Springer.

  • Knuth, D. E. (1998). The Art of Computer Programming, (2nded.), Vol. 3. Addison Wesley.

  • Berg, de. M., Cheong, O., Kreveld, van. M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications. Springer.

  • Ilarri, S., Mena, E., & Illarramendi, A. (2010). Location- Dependent query processing: Where we are and where we are heading. ACM Computing Surveys, March, 42(3), 1-67.

  • Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numeriche Mathematik, 1, 269-271.

  • Ahuja, R. K., Mehlhorn, K., Orlin, J. B., & Tarjan, R. E. (1990). Faster algorithms for the shortest path problem. Journal of the ACM, 37(2), 213-223.

  • Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, July, 34(3), 596-615.

  • Goldberg, A. V. (2001). A simple shortest path algorithm with linear average time. In 9th European Symposium on Algorithms (ESA), vol. 2161 of LNCS, (pp.230-241), Springer.

  • Holzer, M., Schulz, F., & Willhalm, T. (2004). Combining speed-up techniques for shortest-path computations. In 3rd International Workshop on Experimental and Efficient Algorithms (WEA), vol. 3059 of LNCS, (pp. 269-284). Springer.

  • Klein, P., Rao, S., Rauch, M., & Subramanian, S. (1994). Faster shortest-path algorithms for planar graphs. In 26th ACM Symposium on Theory of Computing, (pp. 27-37).

  • Wagner, D., & Willhalm, T. (2005). Drawing graphs to speed up shortest-path computations. In Workshop on Algorithm Engineering and Experiments (ALENEX).

  • Denardo, E. V., & Fox, B. L. (1979). ShortestRoute Methods: Reaching, Pruning, and Buckets.

  • Operation Research, 27, 161-186.

  • Schultes, D. (2008). Route Planning in Road Networks. PhD thesis, Universit at Karlsruhe (TH), Fakultat fur Informatik (2008).

  • Gallo, G., & Pallottino, S. (1984). Shortest path methods: Complexity, interrelations and new propositions. Networks, 14(2), 257-267.

  • Glover, F., Glover, R., & Klingman, D. (1984). Computational Study of an Improved Shortest Path Algorithm. Networks, 14, 25-36.

  • Zhan, F. B., & Noon, C. E. (1998). Shortest Path Algorithms: An Evaluation using Real Road Networks. Transportation Science, 32, 65-73.

  • Knuth, D. E. (1977). A Generalization of Dijkstra’s Algorithm. Information Processing Letters, 6(1), 1-5.

  • Yen, J. Y. (1970). An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics, July, 27(4), 526-530.

  • Lee, K. C. K., & Zheng, B. (2009). Fast object search on road networks. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, (pp. 1018-1029), ACM New York.

  • Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A. D., & Zhou, S. (2012). Shortest path and distance queries on road networks: An experimental evaluation. Proceedings of the VLDB Endowment, 5(5), 406-417.

  • Bast, H., Funke, S., Sanders, P., & Schultes, D. (2007). Fast routing in road networks with transit nodes. Science, 316(5824), 566.

  • Hilger, M., Kohler, E., Mhring, R. H., & Schilling, H. (2006). Fast point-to-point shortest path computations with Arc-Flags. 9th DIMACS Implementation Challenge.

  • Lauther, U. (2004). An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In IfGIprints 22, Institut fuer Geoinformatik, Universitaet Muenster, (pp. 219-230).

  • Sanders, P., & Schultes, D. (2005). Highway hierarchies hasten exact shortest path queries. ESA 2005, LNCS 3669, 568-579.

  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1972). Correction to a Formal Basis for the Heuristic Determination of Minimum Cost Paths. SIGART Newsletter. 37, 28-29.

  • Nilsson, N. J. (2014). Principles of Artificial Intelligence, Springer, reprint..

  • Akiba, T., Iwata, Y., Kawarabayashi, K., & Kawata, Y. (2014). Fast shortest-path distance queries on road networks by pruned highway labeling. Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX).

  • Akiba, T., Hayashi, T., Nori, N., Iwata, Y., & Yoshid, Y. (2015). Efficient Top-k Shortest-Path Distance Queries on Large Networks. Pruned Landmark Labeling. Association for the Advancement of Artificial Intelligence.

  • Bast, H., Funke, S., Matijevic, D., Sanders, P., & Schultes, D. (2007). In transit to constant time shortest-path queries in road networks. In ALENEX, 2007.

  • Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., & Wagner, D. (2008). Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. Journal of Experimental Algorithmics, 15, 303-318, .

  • Goldberg, A. V., & Harrelson, C. (2005). Computing the shortest path: A* search meets graph theory. In SODA: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, (pp.156-165).

  • Johnson, E. L. (1972). On shortest paths and sorting. Proceedings 25th ACM Annual Conference, (pp. 510-517).

  • Hung, M. S., & Divoky, J. J. (1988). A computational study of efficient shortest path algorithms. Computers and Operations Research, 15(6), 567-576.

  • Bertsekas, D. P. (1993). A simple and fast label correcting algorithm for shortest paths. Networks, December, 23(8), 703-709.

  • Cormen, T. H., Leiserson, C. E., Stein, C., & Rivest, R. (2009). Introduction to Algorithms (3rded.) MIT Press.

  • Zhan, F. B., & Noon, C. E. (1998). Shortest Path Algorithms: An Evaluation using Real Road Networks. Transportation Science, February, 32(1), 65-73.

  • Wagner, D., & Willhalm, T. (2005). Drawing graphs to speed up shortest-path computations. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments.

  • Sankaranarayanan, J., Alborzi, H., & Samet, H. (2005). Efficient Query Processing on Spatial Networks. In Proceedings of the 13th ACM International Symposium on Advances in Geographic Information Systems, (pp. 200-209), Bremen, Germany, November.

  • Hjaltason, G. R., & Samet, H. (1991). Ranking in spatial databases. In Proceedings of the 4th International Symposium on Large Spatial Databases, (pp. 83-95).

  • Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. (1994). An optimal algorithm for approximate nearest neighbor searching. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, (pp. 573-582).

  • Broder, A. J. (1990). Strategies for efficient incremental nearest neighbor search. Pattern Recognition, 23(1-2), 171-178.

  • Hjaltason, G. R., & Samet, H. (1999). Distance Browsing in Spatial Databases. In TODS, 24(2), 265-318.

  • Roussopoulos, N., Kelley, S., & Vincent, F. (1995). Nearest Neighbor Queries. In Proceedings SIGMOD, (pp. 71-79).

  • Ailon, N., & Chazelle, B. (2006). Approximate nearest neighbors and the Fast Johnson-Lindenstrauss Transform. Proceedings of the Symposium on Theory of Computing (STOC).

  • Panigrahy, R. (2008). An Improved Algorithm Finding Nearest Neighbor using KD-Trees. In 8th Latin American conference on Theoretical informatics, Bzios, Brazil, (pp. 387-398).

  • Kolahdouzan, M., & Shahabi, C. (2004). VoronoiBased Nearest Neighbor Search for Spatial Network Databases. In Proceedings of VLDB, (pp.840-851).

  • Huang, X., Jensen, C. S., & Saltenis, S. (2005). The Islands Approach to Nearest Neighbor Querying in Spatial Networks, DB Tech Report TR-12. Department of Computer Science, Aalborg University.

  • Jensen, C. S., Kolarvr, J., Pedersen, T. B., & Timko, I. (2003). Nearest Neighbor Queries in Road Networks. In Proceedings 11th ACM International Symposium on Advances in Geographic Information Systems, (pp. 1-8).

  • Yianilos, P. N. (1993). Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, USA, (pp. 311-321).

  • Bajramovic, F., Mattern, F., Butko, N., & Denzler, J. (2006). A comparison of nearest neighbor search algorithms for generic object recognition. In 8th International Conference on Advanced Concepts for Intelligent Vision Systems, Antwerp, Belgium, (pp. 1186-1197).

  • Beyer, K. S., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1998). When is nearest neighbour meaningful? In Proceedings of the 7th International Conference on Database Theory (ICDT’99).

  • Andoni, A. (2009). Nearest Neighbor Search - The Old, the New, and the Impossible, Ph.D. dissertation, Electrical Engineering and Computer Science, Massachusetts Institute of Technology.

  • Yoo, J. S., & Shekhar, S. (2005). In-route nearest neighbor queries. Geo Informatica, 9(2), 117-137.

  • Schiller, J., & Voisard, A. (2004). Location based services, Elsevier.

  • Ferraro, R., & Aktihanoglu, M. (2011). Location aware applications, Manning Publishers.


Abstract Views: 292

PDF Views: 1




  • Transport Optimized Nearest Neighbor Query for Location Based Services

Abstract Views: 292  |  PDF Views: 1

Authors

Debajyoti Ghosh
NIIT University, Neemrana, Rajasthan, India
Prosenjit Gupta
NIIT University, Neemrana, Rajasthan, India

Abstract


Location Based Services are increasingly becoming popular due to increased usage of mobile devices by citizens seeking information on points-of-interest, travel routes, traffic conditions etc. We consider practical variants of the nearest neighbor problem on road networks, wherein the goal is to find the nearest point-of-interest from a query location. Here the notion of proximity is determined by the ease of reaching the point of interest via public transport. Using graphs modeling the road network and transport connectivity, efficient algorithms are presented.

Keywords


Nearest Neighbor Search, Computational Geometry, Road Networks, Shortest Path Problem, Location Based Services.

References