Abstract:

Although efficient geographical query processing on spatial network databases has been studied extensively, existing approaches cannot take advantage of additional information about points on such a network. This information could, for example, include the wait time for a service at a point of interest, or a monetary cost of utilizing that point of interest. Our running example in this paper is that of finding an optimal gas station -- the gas station such that the price of refueling is minimal. We propose S-Tree, a novel index for such augmented spatial networks that models additional information as vertex weights. In addition to facilitating query processing in augmented spatial networks, S-Tree works well with current spatial query processing algorithms. In this paper, we also propose an efficient algorithm for the insertion of points in our proposed index structure and the efficient update of point data or vertex weights on such a network. We provide theoretical as well as experimental results that uphold the correctness and expected runtime of each algorithm. To evaluate our proposed index we measure the performance of nearest neighbor queries on real and synthetic data sets.