Efficient shortest distance query processing and indexing on large road network
- Publication Type:
- Thesis
- Issue Date:
- 2019
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Computing the shortest distance between two vertices is a fundamental problem on road networks. State-of-the-art indexing-based solutions can be categorized into hierarchy-based solutions and hop-based solutions. However, the hierarchy-based solutions require a large search space for long-distance queries while the hop-based solutions result in a high computational waste for short-distance queries. Moreover, in real life, the weight of edges changes frequently. For example, building a road need several months, but the travel time of road changes frequently such as traffic jam in the morning peak. We model this problem as the shortest path problem on a dynamic road network. The existing solutions are not efficient to update the index for the dynamic condition. Shor-test path query on bicriteria road network is another important and practical problem in real life. To compute shortest path between any two vertices, we can get the shortest path set which is called path skyline. We propose an efficient exploring strategy to accelerate path skyline computing.
We propose a novel hierarchical 2-hop index (H2H-Index) which assigns a label for each vertex and at the same time preserves a hierarchy among all vertices. With the H2H-Index, we design an efficient query processing algorithm with performance guarantees by visiting part of the labels for the source and destination based on the vertex hierarchy. We also propose an algorithm to construct the H2H-Index based on distance preserved graphs. The algorithm is further optimized by computing the labels based on the partially computed labels of other vertices.
We use dynamic road network to define the graph model whose topological structure is stable and weight of edges changes frequently. In this model, we have two processing, shortest path query and road update processing, to do on road network. We use Contraction Hierarchies which is one of art-of-the-state index algorithm for shortest path problem to answer queries. And propose an efficient index updating algorithm to update CH index for road updating processing. In contrast to vertex centric algorithm, our shortcut centric algorithm has better theoretical bound.
In the literature, PSQ is a fundamental algorithm for path skyline query and is also used as a building block for the afterwards proposed algorithms. In PSQ, a key operation is to record the skyline paths for each node 𝜐 that is possible on the skyline paths from 𝑠 to 𝑡. However, to obtain the skyline paths for 𝜐, PSQ has to maintain other paths that are not skyline paths for 𝜐, which makes PSQ inefficient. Motivated by this, in this chapter, we propose a new algorithm PSQ⁺ for the path skyline query. By adopting an ordered path exploring strategy, our algorithm can totally avoid the fruitless path maintenance problem in PSQ.
We conducted extensive performance studies using large real road networks including the whole USA road network. The experimental results demonstrate that our approach can make significant improvement to every problem.
Please use this identifier to cite or link to this item: