research-article

Index-supported pattern matching on symbolic trajectories

Authors:

Ralf Hartmut GütingAuthors Info & Claims

SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 53 - 62

https://doi.org/10.1145/2666310.2666402

Published: 04 November 2014 Publication History

Abstract

Recording mobility data with GPS-enabled devices, e.g., smart phones or vehicles, has become a common issue for private persons, companies, and institutions. Consequently, the requirements for managing these enormous datasets have increased drastically, so trajectory management has become an active research field. In order to avoid querying raw trajectories, which is neither convenient nor efficient, a symbolic representation of the geometric data has been introduced.

A comprehensive framework for describing and querying symbolic trajectories including an expressive pattern language as well as an efficient matching algorithm was presented lately. A symbolic trajectory, basically being a time-dependent symbolic value (e.g., a label), can contain names of traversed roads, a speed profile, transportation modes, behaviors of animals, or cells inside a cellular network. The quality and efficiency of transportation systems, targeted advertising, animal research, crime investigation, etc. may be improved by analyzing such data.

The main contribution of this paper is an improvement of our previous approach, featuring algorithms and data structures optimizing the matching of symbolic trajectories for any kind of pattern with the help of two indexes. More specifically, a trie is applied for the symbolic values (i.e., labels or places), while the time intervals are stored in a one-dimensional R-tree. Hence, we avoid the linear scan of every trajectory, being necessary without index support. As a result, the computation cost for the pattern matching is nearly independent from the trajectory size. Our work details the concept and the implementation of the new approach, followed by an experimental evaluation.

References

[1]

G. L. Andrienko, N. V. Andrienko, and M. Heurich. An event-based conceptual model for context-aware movement analysis. International Journal of Geographical Information Science, 25(9):1347--1370, 2011.

Digital Library

[2]

J.-W. Chang, M.-S. Song, and J.-H. Um. Tmn-tree: New trajectory index structure for moving objects in spatial networks. In CIT, pages 1633--1638, 2010.

Digital Library

[3]

V. T. de Almeida, R. H. Güting, and T. Behr. Querying moving objects in Secondo. In MDM, pages 47--51, 2006.

Digital Library

[4]

R. De La Briandais. File searching using variable length keys. In Papers Presented at the the March 3--5, 1959, Western Joint Computer Conference, IRE-AIEE-ACM '59 (Western), pages 295--298, 1959.

Digital Library

[5]

C. du Mouza and P. Rigaux. Multi-scale classification of moving objects trajectories. In Proc. of the 16th Conference on SSDBM, pages 307--316, 2004.

Digital Library

[6]

C. du Mouza and P. Rigaux. Mobility patterns. GeoInformatica, 9(4):297--319, 2005.

Digital Library

[7]

C. Düntgen, T. Behr, and R. H. Güting. BerlinMOD: a benchmark for moving object databases. VLDB J., 18(6):1335--1368, 2009.

Digital Library

[8]

R. H. Güting, T. Behr, and C. Düntgen. Secondo: A platform for moving objects database research and for publishing and integrating research implementations. IEEE Data Eng. Bull., 33(2):56--63, 2010.

[9]

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 querying moving objects. ACM Trans. Database Syst., 25(1):1--42, 2000.

Digital Library

[10]

R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.

[11]

R. H. Güting, F. Valdés, and M. L. Damiani. Symbolic trajectories. FernUniversität in Hagen, Technical Report 369, 2013. http://dna.fernuni-hagen.de/papers/SymbolicTrajectories369.pdf.

[12]

A. Guttman. R-trees: A dynamic index structure for spatial searching, volume 14. ACM, 1984.

Digital Library

[13]

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation - (2. ed.). Addison-Wesley series in computer science. Addison-Wesley-Longman, 2001.

Digital Library

[14]

J. Lu and R. H. Güting. Parallel Secondo: Boosting database engines with hadoop. In ICPADS, pages 738--743, 2012.

Digital Library

[15]

J. Lu and R. H. Güting. Parallel Secondo: Practical and efficient mobility data processing in the cloud. In BigData Conference, pages 17--25, 2013.

[16]

G. Navarro and M. Raffinot. Flexible pattern matching in strings - practical on-line search algorithms for texts and biological sequences. Cambridge University Press, 2002.

Digital Library

[17]

C. Parent, S. Spaccapietra, C. Renso, G. L. Andrienko, N. V. Andrienko, V. Bogorny, M. L. Damiani, A. Gkoulalas-Divanis, J. A. F. de Macêdo, N. Pelekis, Y. Theodoridis, and Z. Yan. Semantic trajectories modeling and analysis. ACM Comput. Surv., 45(4):42, 2013.

Digital Library

[18]

N. Pelekis and Y. Theodoridis. Mobility Data Management and Exploration. Springer, 2014.

Digital Library

[19]

D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving object trajectories. In VLDB, pages 395--406, 2000.

Digital Library

[20]

S. Spaccapietra, C. Parent, M. L. Damiani, J. A. F. de Macêdo, F. Porto, and C. Vangenot. A conceptual view on trajectories. Data Knowl. Eng., 65(1):126--146, 2008.

Digital Library

[21]

F. Valdés, M. L. Damiani, and R. H. Güting. Symbolic trajectories in Secondo: Pattern matching and rewriting. In DASFAA (2), pages 450--453, 2013.

[22]

M. Vazirgiannis, Y. Theodoridis, and T. K. Sellis. Spatio-temporal composition and indexing for large multimedia applications. Multimedia Syst., 6(4):284--298, 1998.

Digital Library

[23]

M. R. Vieira, P. Bakalov, and V. J. Tsotras. Querying trajectories using flexible patterns. In Proc. of the Conference on EDBT, pages 406--417, 2010.

Digital Library

[24]

M. R. Vieira, P. Bakalov, and V. J. Tsotras. Flextrack: A system for querying flexible patterns in trajectory databases. In 12th International Symposium, SSTD, pages 475--480, 2011.

Digital Library

[25]

M. R. Vieira and V. J. Tsotras. Complex motion pattern queries for trajectories. In ICDE Workshops, pages 280--283, Hannover, Germany, 2011.

Digital Library

[26]

M. Vlachos, D. Gunopulos, and G. Kollios. Discovering similar multidimensional trajectories. In ICDE, pages 673--684, 2002.

Digital Library

[27]

Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. Semantic trajectories: Mobility data computation and annotation. ACM TIST, 4(3):49, 2013.

Digital Library

[28]

C. Zhang, J. Han, L. Shou, J. Lu, and T. F. L. Porta. Splitter: Mining fine-grained sequential patterns in semantic trajectories. PVLDB, 7(9):769--780, 2014.

Digital Library

[29]

Y. Zheng and X. Zhou, editors. Computing with Spatial Trajectories. Springer, 2011.

Digital Library

Cited By

Gryllakis FPelekis NDoulkeridis CVarlamis ITheodoridis Y(2022)Social Spatio-temporal Keyword Pattern (S²KP) Queries in Multiple Aspect Trajectories DatabasesProceedings of the 34th International Conference on Scientific and Statistical Database Management10.1145/3538712.3538716(1-12)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3538712.3538716
Valdes F(2022)MFPMiner: Mining Meaningful Frequent Patterns from Spatio-textual TrajectoriesACM Transactions on Spatial Algorithms and Systems10.1145/34987288:1(1-30)Online publication date: 9-Mar-2022
https://dl.acm.org/doi/10.1145/3498728
Körber MGlombiewski NSeeger BLi GLi ZIdreos SSrivastava D(2021)Index-Accelerated Pattern Matching in Event StoresProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457245(1023-1036)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457245
Show More Cited By

Index Terms

Index-supported pattern matching on symbolic trajectories

Recommendations

Index-Accelerated Pattern Matching in Event Stores
SIGMOD '21: Proceedings of the 2021 International Conference on Management of Data

IoT applications require a new type of database systems termed event stores for ingesting fast arriving event streams and efficiently supporting analytical ad-hoc queries over time. One of the most important operations in this regard is sequential ...
Symbolic Trajectories

Due to the proliferation of GPS-enabled devices in vehicles or with people, large amounts of position data are recorded every day and the management of such mobility data, also called trajectories, is a very active research field. A lot of effort has ...
An Optimization Algorithm for Spatial Index Structure Based on Spatial Clustering
BCGIN '11: Proceedings of the 2011 International Conference on Business Computing and Global Informatization

Spatial index has been one of the active focus areas in recent database research. The R-tree proposed by Guttman is probably the most popular dynamic index structure for efficiently retrieving objects from a spatial database according to their spatial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2014

651 pages

ISBN:9781450331319

DOI:10.1145/2666310

General Chairs:
Yan Huang
University of North Texas
,
Markus Schneider
University of Florida
,
Program Chairs:
Michael Gertz
Heidelberg University, Germany
,
John Krumm
Microsoft Research
,
Jagan Sankaranarayanan
NEC Labs

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

ESRI
Yandex
Google Inc.
NVIDIA
University of North Texas: University of North Texas
Microsoft: Microsoft
ORACLE: ORACLE
Facebook: Facebook
SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSPATIAL '14

Sponsor:

University of North Texas
Microsoft
ORACLE
Facebook
SIGSPATIAL

SIGSPATIAL '14: 22nd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 4 - 7, 2014

Texas, Dallas

Acceptance Rates

SIGSPATIAL '14 Paper Acceptance Rate 39 of 184 submissions, 21%;

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
196
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gryllakis FPelekis NDoulkeridis CVarlamis ITheodoridis Y(2022)Social Spatio-temporal Keyword Pattern (S²KP) Queries in Multiple Aspect Trajectories DatabasesProceedings of the 34th International Conference on Scientific and Statistical Database Management10.1145/3538712.3538716(1-12)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3538712.3538716
Valdes F(2022)MFPMiner: Mining Meaningful Frequent Patterns from Spatio-textual TrajectoriesACM Transactions on Spatial Algorithms and Systems10.1145/34987288:1(1-30)Online publication date: 9-Mar-2022
https://dl.acm.org/doi/10.1145/3498728
Körber MGlombiewski NSeeger BLi GLi ZIdreos SSrivastava D(2021)Index-Accelerated Pattern Matching in Event StoresProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457245(1023-1036)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457245
Zhou FWu HTrajcevski GKhokhar AZhang K(2020)Semi-supervised Trajectory Understanding with POI Attention for End-to-End Trip RecommendationACM Transactions on Spatial Algorithms and Systems10.1145/33788906:2(1-25)Online publication date: 7-Feb-2020
https://dl.acm.org/doi/10.1145/3378890
Xu J(2020)Multi-attribute Trajectory Data ManagementHandbook of Big Geospatial Data10.1007/978-3-030-55462-0_9(199-240)Online publication date: 17-Dec-2020
https://doi.org/10.1007/978-3-030-55462-0_9
Xu JGüting RZheng YWolfson O(2019)Moving Objects with Transportation Modes: A SurveyJournal of Computer Science and Technology10.1007/s11390-019-1938-434:4(709-726)Online publication date: 19-Jul-2019
https://doi.org/10.1007/s11390-019-1938-4
Lu QWang RYang BWang Z(2019)Trajectory splicingKnowledge and Information Systems10.1007/s10115-019-01382-xOnline publication date: 18-Jul-2019
https://doi.org/10.1007/s10115-019-01382-x
Valdés FGüting R(2018)A framework for efficient multi-attribute movement data analysisThe VLDB Journal10.1007/s00778-018-0525-6Online publication date: 31-Oct-2018
https://doi.org/10.1007/s00778-018-0525-6
Valdés FGüting R(2017)Efficient Multi-Attribute Analysis for TrajectoriesProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139977(1-4)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139977
Valdés FGüting R(2017)Index-supported pattern matching on tuples of time-dependent valuesGeoinformatica10.1007/s10707-016-0286-621:3(429-458)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10707-016-0286-6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents