Using space-time grid for efficient management of moving objects

ABSTRACT

Efficient storage and retrieval of moving objects in DBMS have received significant interest recently. There are applications that would benefit from the management of dynamically changing information about moving objects. In this paper, we develop a system that manages such information interacting with moving objects. We model the space-time domain space as a grid (Space-Time Grid) and model the trajectory of a moving object as a polyline in the Space-Time Grid. The polyline is the result of the interactions among other moving objects. In this paper, the insertion algorithm and several other query processing algorithms are presented.

REFERENCES

• 1: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 2: CalTrans. Advanced Transportation Systems program Plan. http://www.dot.ca.gov/hq/newtech, 1996.
• 3: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Storage and Retrieval of Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.173-184, January 08-10, 2001
• 4: R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
• 5: Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Approximate Nearest Neighbor Searching in Multimedia Databases, Proceedings of the 17th International Conference on Data Engineering, p.503-511, April 02-06, 2001
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: S. Handley, P. Langley, and F. Rauscher. Learning to predict the duration of an automobile trip. In Proceedings of the Int. Conf. on Knowledge Discovery and Data Mining, pages 219-223, 1998.
• 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: Randal C. Nelson , Hanan Samet, A consistent hierarchical representation for vector data, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.197-206, August 1986
• 10: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 11: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 12: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 13: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 14: J. Tayeb, O. Ulusoy, and O. Wolfson. A Quadtree Based Dynamic Attribute Indexing Method. In Proceedings of ACM Symp. on Principles of Database Systems, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Management