Efficient Approximation of Spatial Network Queries using the M-Tree with Road Network Embedding

Abstract

Spatial networks, such as road systems, operate differently from normal geospatial systems because objects are constrained to locations on the network. Performing queries on spatial networks demands entirely different solutions. Most spatial queries make use of an R-Tree to process them efficiently. The M-Tree is a data tree index which is capable of indexing data in any metric space. The M-Tree index can replace the R-Tree index for spatial network queries, such as range and KNN queries. The difficulty is that the M-Tree is only as efficient as the distance algorithm used on the underlying objects. Most network distance algorithms, such as A*, are too slow to allow the M-Tree to operate efficiently on spatial networks. The truncated road network embedding (tRNE) maps the network into a higher dimensional space where any LP metric can be used to efficiently compute an accurate approximation of network distance. The M-Tree combined with tRNE creates an efficient index structure for computing spatial network queries. The M-Tree substantially outperforms network expansion, the most popular method of computing spatial network queries, when performing spatial network KNN and range queries.