Abstract
In this paper, we describe an efficient indexing method for a shape-based similarity search of the trajectory of dynamically changing locations of people and mobile objects. In order to manage trajectories in database systems, we define a data model of trajectories as directed lines in a space, and the similarity between trajectories is defined as the Euclidean distance between directed discrete lines. Our proposed similarity query can be used to find interested patterns embedded into the trajectories, for example, the trajectories of mobile cars in a city may include patterns for expecting traffic jams. Furthermore, we propose an efficient indexing method to retrieve similar trajectories for a query by combining a spatial indexing technique (R+-Tree) and a dimension reduction technique, which is called PAA (Piecewise Approximate Aggregate). T he indexing method can efficiently retrieve trajectories whose shape in a space is similar to the shape of a candidate trajectory from the database.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Chen and D. Kotz. Categorizing binary topological relations between regions, lines, and points in geographic databases.Technical Report TR2000-381, A Survey of Context-Aware Mobile Computing Research, Dept. of Computer Science, Dartmouth College, 2000.
H. Chon, D. Agrawal, and A.E. Abbadi. Query processing for moving objects with space-time grid storage model.In MDM2002 Conference Proceedings, pages 121–129, 2002.
E. Clementini and P.D. Felice. Topological invariants for lines. IEEE Transaction on Knowledge and Data Engineering, 10(1):38–54, 1998.
L.E. Elsgolc. Calculus of Variations.Pergamon Press LTD, 1961.
E.G. Hoel and H. Samet. Efficient processing of spatial queries in line segment databases. In O. Gunther and H. J. Schek, editors, SSD’91 Proceedings, volume 525, pages 237–256. Springer-Verlag, 1991.
E. Keogh, K. Chakrabarti, S. Mehrotra, and M. Pazzan. Locally adaptive dimensionality reduction for indexing large time series databases.In SIGMOD2001 Conference Proceedings, pages 151–162, 2001.
E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 3(3):263–286, 2001.
G. Kollios, D. Gunopulos, and V.J. Tsotras. On indexing mobile objects. In SIGMOD’99 Conference Proceedings, pages 261–272, 1999.
G. Kollios, V.J. Tsotras, D. Gunopulos, A. Delis, and M. Hadjieleftheriou. Indexing animated objects using spatiotemporal access methods. IEEE Transactions on Knowledge and Data Engineering, 13(5):758–777, 2001.
Y.-S. Moon, K.-Y. Whang, and W.-S. Han. General match: A subsequence matching method in time-series databases based on generalized windows.In SIGMOD 2002 Conference Proceedings, pages 382–393, 2002.
K. Porkaew, I. Lazaridis, and S. Mehrotra. Querying mobile objects in spatiotemporal databases. In C.S. Jensen, M. Schneider, B. Seeger, and V.J. Tsotras, editors, SSTD 2001, volume 2121 of Lecture Notes in Computer Science, pages 59–78. Springer-Verlag, 2001.
N. Priyantha, A. Miu, H. Balakrishnan, and S. Teller. The cricket compass for context-aware mobile applications. In MOBICOM2001 Conference Proceedings, pages 1–14, 2001.
T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multidimensional objects. In VLDB’87 Conference Proceedings, pages 3–11, 1987.
A.P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Modeling and querying moving objects.In ICDE’97 Proceedings, pages 422–432, 1997.
M. Vazirgiannis and O. Wolfson. A spatiotemporal model and language for moving objects on road networks. In C. S. Jensen, M. Schneider, B. Seeger, and V. J. Tsotras, editors, SSTD 2001, volume 2121 of Lecture Notes in Computer Science, pages 20–35. Springer-Verlag, 2001.
O. Wolfson, B. Xu, S. Chamberlain, and L. Jiang. Moving objects databases: Issues and solutions. In Statistical and Scientific Database Management (SSDM’98) Conference Proceedings, pages 111–122, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yanagisawa, Y., Akahani, Ji., Satoh, T. (2003). Shape-Based Similarity Query for Trajectory of Mobile Objects. In: Chen, MS., Chrysanthis, P.K., Sloman, M., Zaslavsky, A. (eds) Mobile Data Management. MDM 2003. Lecture Notes in Computer Science, vol 2574. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36389-0_5
Download citation
DOI: https://doi.org/10.1007/3-540-36389-0_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00393-9
Online ISBN: 978-3-540-36389-7
eBook Packages: Springer Book Archive