Path oracles for spatial networks

• Published in: Proceedings of the VLDB Endowment 2009-08, Vol.2 (1), p.1210-1221
• Main Authors: Sankaranarayanan, Jagan, Samet, Hanan, Alborzi, Houman
• Format: Article
• Language: English
• ISSN: 2150-8097; 2150-8097
• DOI: 10.14778/1687627.1687763

The advent of location-based services has led to an increased demand for performing operations on spatial networks in real time. The challenge lies in being able to cast operations on spatial networks in terms of relational operators so that they can be performed in the context of a database. A linear-sized construct termed a path oracle is introduced that compactly encodes the n 2 shortest paths between every pair of vertices in a spatial network having n vertices thereby reducing each of the paths to a single tuple in a relational database and enables finding shortest paths by repeated application of a single SQL SELECT operator. The construction of the path oracle is based on the observed coherence between the spatial positions of both source and destination vertices and the shortest paths between them which facilitates the aggregation of source and destination vertices into groups that share common vertices or edges on the shortest paths between them. With the aid of the Well-Separated Pair (WSP) technique, which has been applied to spatial networks using the network distance measure, a path oracle is proposed that takes O ( s d n ) space, where s is empirically estimated to be around 12 for road networks, but that can retrieve an intermediate link in a shortest path in O (log n ) time using a B-tree. An additional construct termed the path-distance oracle of size O ( n · max( s d , 1/ε d )) (empirically ( n · max(12 2 , 2.5/ε 2 ))) is proposed that can retrieve an intermediate vertex as well as an ε-approximation of the network distances in O (log n ) time using a B-tree. Experimental results indicate that the proposed oracles are linear in n which means that they are scalable and can enable complicated query processing scenarios on massive spatial network datasets.