Efficient executions of shortest path queries using data broadcast
Student thesis: Doctoral Thesis
Related Research Unit(s)
Data broadcast has been shown to be an efficient approach to distribute a large amount of data to a large group of clients and successfully adopted in distributing road data (road connections and traffics) to clients to support the local processing of spatial queries. However, little works focus on shortest path query, although it is one of the most commonly performed queries by mobile clients on road networks. In this thesis, we studied efficient broadcast indices under different system models. First, the CH Index was designed with the purposes of minimizing the energy consumption of query processing, by exploiting the special properties of road networks. To the best of our knowledge, it is still the most energy efficient broadcast index and consumes the lowest energy for random queries on average. Furthermore, the CHBN Index was proposed to provide a trade-off between energy consumption and response time by incorporating graph partitioning technique. Second, in order to provide effective shortest path navigation on a road network with traffic updates, the shortest path query has to be re-executed periodically until the client has arrived its destination. This kind of queries is called the shortest path continuous queries (SPCQ). Progressive approach (PA) was designed to navigate the clients of SPCQ to their destinations step-by-step. In PA, next region (NR) approach together with a hierarchical network approach are applied to formulate the local graphs at the clients. Experimental results showed that PA can reduce the size of local graphs and the energy consumption and path searching cost at the clients with just small increase in the arrival times to their destinations. Third, for clients with soft arrival deadlines, we proposed a new method called approximate path searching (APS) based on NR. By adopting an approximation technique in calculating the sets of required regions for each region pair in a road network, the index generation cost at the road server and the energy consumption and path searching cost at the clients can be reduced. Different from NR, which only provides one set of required regions containing the shortest path from a client’s current location to its destination, APS generates n-sets of required regions for a client to choose. In the experiments, the performance characteristics of APS were studied compared with NR using datasets from real road networks. At the end of this thesis, we gave future directions such as to further study broadcast index to efficiently support shortest path queries on a road network with uncertainties, e.g. on road connections and road traffics.
- Traffic estimation, Data processing, Querying (Computer science), Travel time (Traffic engineering)