Distance indexing on road networks

Abstract

The processing of kNN and continuous kNN queries on spa-tial network databases (SNDB) has been intensively studied recently. However, there is a lack of systematic study on the computation of network distances, which is the most funda-mental difference between a road network and a Euclidean space. Since the online Dijkstra’s algorithm has been shown to be efficient only for short distances, we propose an effi-cient index, called distance signature, for distance computa-tion and query processing over long distances. Distance sig-nature discretizes the distances between objects and network nodes into categories and then encodes these categories. To minimize the storage and search costs, we present the opti-mal category partition, and the encoding and compression algorithms for the signatures, based on a simplified net-work topology. By mathematical analysis and experimen-tal study, we showed that the signature index is efficient and robust for various data distributions, query workloads, parameter settings and network updates. 1.