TY - CONF
T1 - Scalable network distance browsing in spatial databases
T2 - Proceedings of the 2008 ACM SIGMOD international conference on Management of data
Y1 - 2008
A1 - Samet, Hanan
A1 - Sankaranarayanan,Jagan
A1 - Alborzi,Houman
KW - decoupling
KW - nearest neighbor
KW - scalability
KW - shortest path quadtree
KW - spatial networks
AB - An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N3) to O(N1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.
JA - Proceedings of the 2008 ACM SIGMOD international conference on Management of data
T3 - SIGMOD '08
PB - ACM
CY - New York, NY, USA
SN - 978-1-60558-102-6
UR - http://doi.acm.org/10.1145/1376616.1376623
M3 - 10.1145/1376616.1376623
ER -