Similarity measures for trajectory of moving objects in cellular space

ABSTRACT

While most GIS (Geographical Information System) are based on Euclidean space, cellular space can be used as an alternative type of space for a large number of GIS applications. In order to analyze the pattern of moving objects in cellular space, we need new definitions of similarity between their trajectories since the trajectories in cellular space significantly differ from those in Euclidean space. In this paper, we study the properties of moving object in cellular space. Based on these observations, we propose several similarity measures between trajectories in cellular space. We analyze the differences of the proposed measures by experiments.

References

1. R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity search in sequence databases. In Proceedings of the 18th International Conference on Foundations of Data Organization and Algorithms, pages 69--84, October 1993.
2. C. Becker and F. Dürr. On location models for ubiquitous computing. Personal and Ubiquitous Computing, 9(1): 20--31, January 2005.
3. L. Becker, H. Blunck, K. Hinrichs, and J. Vahrenhold. A framework for representing moving objects. In Proceedings of the 15th International Conference on Database and Expert Systems Applications, pages 854--863, August 2004.
4. L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In Proceedings of the 7th International Symposium on String Processing Information Retrieval, pages 39--48, September 2000.
5. R. H. Güting, M. H. Böhlen, M. Erwig, C. S. Jensen, N. A. Lorentzos, M. Schneider, and M. Vazirgiannis. A foundation for representing and quering moving objects. ACM Trans. Database Syst., 25(1): 1--42, March 2000.
6. D. S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of ACM, 24(4): 664--675, December 1977.
7. E. J. Keogh and M. J. Pazzani. Scaling up dynamic time warping for datamining applications. In Proceedings of the 6th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 285--289, 2000.
8. B. Lin and J. S. One way distance:for shape based similarity search of moving object trajectories. GeoInformatica, 12(2): 117--142, June 2008.
9. N. Meratnia and R. A. de By. Trajectory representation in location-based services: Problems & solution. In Proceedings of the 3th International Workshop on Web and Wireless Geographical Information Systems, pages 18--24, December 2003.
10. N. Pelekis, I. Kopanakis, G. Marketos, I. Ntoutsi, G. Andrienko, and Y. Theodorids. Similarity search in trajectory databases. In Proceedings of the 14th International Symposium on Temporal Representation and Reasoning, pages 854--863, August 2007.
11. K. pong Chan and A. W.-C. Fu. Efficient time series matching by wavelets. In Proceedings of the 15th International Conference on Data Engineering, pages 126--133, March 1999.
12. Y. Sakurai, M. Yoshikawa, and C. Faloutsos. Ftw: fast similarity search under the time warping distance. In Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 326--337, June 2005.
13. E. Tiakas, A. N. Papadopoulos, A. Nanopoulos, Y. Manolopoulos, D. Stojanovic, and S. Djordjevic-Kajan. Trajectory similarity search in spatial networks. In Proceedings of the 13th ISPE International Conference on Concurrent Engineering, pages 185--192, December 2006.
14. M. Vazirgiannis and O. Wolfson. A spatiotemporal model and language for moving objects on road networks. In Proceedings of the 7th International Symposium on Spatial and Temporal Databases, pages 20--35, July 2001.
15. M. Vlachos, M. Hadjieleftheriou, D. Gunopulos, and E. J. Keogh. Indexing multi-dimensional time-series with support for multiple distance measures. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 216--225, August 2003.
16. R. Want, A. Hopper, V. Falcao, and H. Gibbons. The active badge location system. ACM Transactions on Information Systems, 10(1): 91--102, January 1992.
17. Y. Yanagisawa, J. ichi Akahani, and T. Satoh. Shape-based similarity query for trajectory of mobile objects. In Proceedings of the 4th International Conference on Mobile Data Management, pages 63--77, January 2003.
18. M. A. N. Yannis Theodoridis. Generating spatiotemporal datasets on the www. ACM SIGMOD Record, 29(3): 39--43, September 2000.
19. P. Zezula, G. Amato, V. Dohanl, and M. Batko. Similarity Search The Metric Space Approach. Springer Science+Business Media, 233 Spring street, New York, 2005.

Index Terms

• Information systems

  • Information systems applications