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