Querying the trajectories of on-line mobile objects

ABSTRACT

Position data is expected to play a central role in a wide range of mobile computing applications, including advertising, leisure, safety, security, tourist, and traffic applications. Applications such as these are characterized by large quantities of wirelessly Internet-worked, position-aware mobile objects that receive services where the objects' position is essential. The movement of an object is captured via sampling, resulting in a trajectory consisting of a sequence of connected line segments for each moving object. This paper presents a technique for querying these trajectories. The technique uses indices for the processing of spatiotemporal range queries on trajectories. If object movement is constrained by the presence of infrastructure, e.g., lakes, park areas, etc., the technique is capable of exploiting this to reduce the range query, the purpose being to obtain better query performance. Specifically, an algorithm is proposed that segments the original range query based on the infrastructure contained in its range. The applicability and limitations of the proposal are assessed via empirical performance studies with varying datasets and parameter settings.

REFERENCES

• 1: Daniel Barbará, Mobile Computing and Databases-A Survey, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.108-117, January 1999 [doi>10.1109/69.755619]
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 4: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 6: Karppinen, J.: Wireless Multimedia Communications: a Nokia View. In Proceedings of the Wireless Information Multimedia Communications Symposium, Aalborg University, 1999.
• 7: Scott T. Leutenegger , Mario A. Lopez, The Effect of Buffering on the Performance of R-Trees, Proceedings of the Fourteenth International Conference on Data Engineering, p.164-171, February 23-27, 1998
• 8: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 9: Moore, D.: Fast Hilbert Curve Generation, Sorting, and Range Queries. www.caam.rice.edu/~dougm/twiddle/Hilbert/, current as of April 12, 2001.
• 10: Mario A. Nascimento , Jefferson R. O. Silva , Yannis Theodoridis, Evaluation of Access Structures for Discretely Moving Points, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.171-188, September 10-11, 1999
• 11: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
• 12: Apostolos Papadopoulos , Yannis Manolopoulos, Multiple Range Query Optimization in Spatial Databases, Proceedings of the Second East European Symposium on Advances in Databases and Information Systems, p.71-82, September 07-10, 1998
• 13: Dieter Pfoser , Christian S. Jensen, Capturing the Uncertainty of Moving-Object Representations, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.111-132, July 20-23, 1999
• 14: Pfoser, D. and Jensen, C. S.: Querying the Trajectories of On- Line Mobile Objects. TimeCenter Technical Report TR-55, www.cs.auc.dk/TimeCenter, current as of April 12, 2001.
• 15: Pfoser, D. and Theodoridis, Y.: Generating Semantics-Based Trajectories of Moving Objects. In Proceedings of the International Workshop on Emerging Technologies for Geo-Based Applications, pp. 59-76, 2000.
• 16: 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
• 17: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 18: Theodoros Tzouramanis , Michael Vassilakopoulos , Yannis Manolopoulos, Overlapping linear quadtrees: a spatio-temporal access method, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.1-7, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288695]
• 19: Michael Vazirgiannis , Yannis Theodoridis , Timos Sellis, Spatio-temporal composition and indexing for large multimedia applications, Multimedia Systems, v.6 n.4, p.284-298, July 1998 [doi>10.1007/s005300050094]

INDEX TERMS

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

General Terms:
Performance, Reliability

Keywords:
constrained movement, moving objects, query processin, query window segmentation, trajectory