Path oracles for spatial networks

The advent of location-based services has led to an increased de- mand for performing operations on spatial networks in real time. The challenge lies in being able to cast operations on spatial net- works 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 n2 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 relat ional database and enables finding shortest paths by repeated appl ication of a single SQL SELECT operator. The construction of the path oracle is based on the observed coherence between the spatial posi- tions of both source and destination vertices and the shorte st paths between them which facilitates the aggregation of source and desti- nation 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(sdn) 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 con- struct termed the path-distance oracle of size O(nmax(sd, 1 ε d ))