Authors: Sandeep Gupta, Swastik Kopparty, Chinya Ravishankar

Title: Roads, Codes, and Spatiotemporal Queries

Conference: Proceedings of the Twenty-third ACM Symposium on Principles of Database Systems (PODS)

Year: 2004

Abstract: We present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane such as many road networks. We handle join, range, intercept, and other spatial and spatiotemporal queries under these assumptions, with distances being measured along the trajectories. Most work to date has studied the significantly simpler case of objects moving in straight lines on the plane. Our work is an advance toward solving the problem in its more general form. Central to our approach is an efficient coding technique, based on hypercube embedding, for assigning labels to nodes in the network. The Hamming distance between codes corresponds to the physical distance between nodes, so that we can determine shortest distances in the network extremely quickly. The coding method also efficiently captures many properties of the network relevant to spatial and spatiotemporal queries. Our approach also yields a very effective spatial hashing method for this domain. Our analytical results demonstrate that our methods are space- and time-efficient. We have studied the performance of our method for large planar graphs designed to represent road networks. Experiments show that our methods are efficient and practical.

[Download]

Back