Roads, codes, and spatiotemporal queries

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.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 3: Victor Chepoi , Michel Deza , Viatcheslav Grishukhin, Clin d'oeil on L1-embeddable planar graphs, Discrete Applied Mathematics, v.80 n.1, p.3-19, Dec. 5, 1997 [doi>10.1016/S0166-218X(97)00066-8]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 6: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 7: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 8: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 9: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.
• 10: Kurt Mehlhorn , Stefan Näher , Christian Uhrig, The LEDA Platform of Combinatorial and Geometric Computing, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.7-16, July 07-11, 1997
• 11: D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases, 2003.
• 12: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 13: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A road network embedding technique for k-nearest neighbor search in moving object databases, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585167]
• 14: Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In Proc. of the VLDB, 2003.
• 15: US Census Bureau. TIGER. http://tiger.census.gov/.
• 16: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001