G*-Tree: An Efficient Spatial Index on Road Networks
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 268-279
Abstract
In this paper, we propose an efficient hierarchical index, G*-tree, to optimize spatial queries on road networks. Most existing graph indexes can only support one kind of query, and thus we need to build multiple indexes on a road network to handle various kinds of spatial queries, which is inefficient and unscalable for real-world applications. To address the problem, a recent study proposes G-tree to support multiple types of spatial queries on road networks within one framework. However, the assembly-based method on G-tree is not efficient enough to handle spatial queries when vertices, which are close in a road network, are distant in G-tree. To address the inefficiency problem of G-tree, in this paper, we propose a novel index structure on road networks, namely G*-tree, whose key idea is to build shortcuts between selected leaf nodes. Based on G*-tree, we propose three shortcut-based algorithms to answer distance queries, k-nearest neighbor queries and range queries, respectively, which are more efficient than the existing assembly-based algorithms on G-tree. Moreover, we propose a shortcut selection algorithm to optimize the performance of spatial queries on G*-tree. We conduct extensive experiments to compare our G*-tree and the state-of-the-art indexing methods on various large-scale road networks, where the results demonstrate that our G*-tree has better efficiency and scalability than the competitors to handle spatial queries.Keywords
This publication has 16 references indexed in Scilit:
- Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling2013
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks2008
- Fast Routing in Road Networks with Transit NodesScience, 2007
- Computing Many-to-Many Shortest Paths Using Highway Hierarchies2007
- Introduction to NP-Completeness of Knapsack Problems2004
- Query Processing in Spatial Network Databases2003
- On the Problem of Partitioning Planar GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974
- A note on two problems in connexion with graphsNumerische Mathematik, 1959