Efficient Evaluation of Path Queries on Dynamic Route Collections

Abstract — Traversal is a key process in searching. In a network, there are sequence of points that connects source and destination. In such circumstances, we use path queries that return a path for processing the information through the sequence of points. Nowadays, vast amount of routing data, like sequences of points of interests, landmarks, etc., are available due to the proliferation of geo data services. We refer to these sequences as routes and the involved points simply as nodes. The recent advances in the infrastructure of Geographic Information Systems (GIS) have resulted in abundance of geo data in the form of sequence of points of interest, waypoints, etc. We refer to sets of such sequences as route collections. Given the availability of large route collections, there exists the problem of identifying paths frequently and evaluating the queries on the paths. In this project, the problem of evaluating path queries on frequently updated route collections is considered. The current work presents (i) identifying a path between two nodes of the collection, and (ii) identifying a constrained shortest path for two path queries. Hence, the proposed methodology is less efficient in evaluating the path queries, but, is significantly cheaper to construct and maintain. Also, the methodology is designed such that it can cope up with frequent updates on the route collections. Key words—Route collections, path queries, frequen