Marcos R. Vieira
Petko Bakalov
Vassilis J. Tsotras
ABSTRACT
The wide adaptation of GPS and cellular technologies has created many applications that collect and maintain large repositories of data in the form of trajectories. Previous work on querying/analyzing trajectorial data typically falls into methods that either address spatial range and NN queries, or, similarity based queries. Nevertheless, trajectories are complex objects whose behavior over time and space can be better captured as a sequence of interesting events. We thus facilitate the use of motion "pattern" queries which allow the user to select trajectories based on specific motion patterns. Such patterns are described as regular expressions over a spatial alphabet that can be implicitly or explicitly anchored to the time domain. Moreover, we are interested in "flexible" patterns that allow the user to include "variables" in the query pattern and thus greatly increase its expressive power. In this paper we introduce a framework for efficient processing of flexible pattern queries. The framework includes an underlying indexing structure and algorithms for query processing using different evaluation strategies. An extensive performance evaluation of this framework shows significant performance improvement when compared to existing solutions.
- http://www.rtreeportal.org.Google Scholar
- J. Agrawal and et al. Efficient pattern matching over event streams. SIGMOD, pages 147--159, 2008. Google ScholarDigital Library
- A. Anagnostopoulos and et al. Global distance-based segmentation of trajectories. In ACM KDD, 2006. Google ScholarDigital Library
- Y. Cai and R. Ng. Indexing spatio-temporal trajectories with Chebyshev polynomials. In ACM SIGMOD, pages 599--610, 2004. Google ScholarDigital Library
- C. du Mouza, P. Rigaux, and M. Scholl. Efficient evaluation of parameterized pattern queries. In CIKM, pages 728--735, 2005. Google ScholarDigital Library
- M. Erwig and M. Schneider. Spatio-temporal predicates. IEEE TKDE, pages 881--901, 2002. Google ScholarDigital Library
- ESRI. ArcGIS. www.esri.com.Google Scholar
- R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, pages 102--113, 2001. Google ScholarDigital Library
- M. Hadjieleftheriou, G. Kollios, P. Bakalov, and V. Tsotras. Complex spatio-temporal pattern queries. In VLDB, pages 877--888, 2005. Google ScholarDigital Library
- M. Hadjieleftheriou, G. Kollios, V. Tsotras, and D. Gunopulos. Indexing spatiotemporal archives. VLDB J., pages 143--164, 2006. Google ScholarDigital Library
- D. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J. on Computing, 1977.Google Scholar
- G. Kollios, D. Papadopoulos, D. Gunopulos, and V. Tsotras. Indexing mobile objects using dual transformations. VLDB J., pages 238--256, 2005. Google ScholarDigital Library
- J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: a partition-and-group framework. In SIGMOD, pages 593--604, 2007. Google ScholarDigital Library
- N. Mamoulis and et al. Mining, indexing, and querying historical spatiotemporal data. In ACM SIGKDD, pages 236--245, 2004. Google ScholarDigital Library
- M. Mokbel and W. Aref. SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams. In VLDB J., pages 971--995, 2008. Google ScholarDigital Library
- H. Mokhtar, J. Su, and O. Ibarra. On moving object queries. In ACM PODS, pages 188--198, 2002. Google ScholarDigital Library
- M. Pelanis, S. Saltenis, and C. Jensen. Indexing the past, present, and anticipated future positions of moving objects. ACM TODS, pages 255--298, 2006. Google ScholarDigital Library
- D. Pfoser, C. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving object trajectories. In VLDB, pages 395--406, 2000. Google ScholarDigital Library
- R. Sadri and et al. Expressing and optimizing sequence queries in database systems. ACM TODS, 2004. Google ScholarDigital Library
- M. A. Sakr and R. H. Güting. Spatiotemporal pattern queries in SECONDO. In SSTD, pages 422--426, 2009. Google ScholarDigital Library
- P. Seshadri, M. Livny, and R. Ramakrishnan. SEQ: A model for sequence databases. In IEEE ICDE, 1995. Google ScholarDigital Library
- Y. Tao and D. Papadias. MV3R-Tree: A spatio-temporal access method for timestamp and interval queries. In VLDB, pages 431--440, 2001. Google ScholarDigital Library
- Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In VLDB, pages 287--298, 2002. Google ScholarDigital Library
Recommendations
Querying graph patterns
PODS '11: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsGraph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, i.e., graph patterns. While queries need to be posed against such data,...
Improving XML Querying with Maximal Frequent Query Patterns
ICCS '07: Proceedings of the 7th international conference on Computational Science, Part I: ICCS 2007Querying on XML data is a computational-expensive process due to the complex nature of both the XML data and the query. In this paper, we propose an approach to expedite XML query processing by caching the results of a specific class of queries, namely ...
Querying the trajectories of on-line mobile objects
MobiDe '01: Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile accessPosition 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 ...
Comments