Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient shortest distance query processing and indexing on large road network
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ouyang, Dian |
| Copyright Year | 2019 |
| Abstract | 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 shortdistance 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. Shortest 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 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://opus.lib.uts.edu.au/bitstream/10453/137106/1/01front.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
