More Web Proxy on the site http://driver.im/

research-article

Of motifs and goals: mining trajectory data

Authors:

Joachim Gudmundsson,

Jan VahrenholdAuthors Info & Claims

SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

Pages 129 - 138

https://doi.org/10.1145/2424321.2424339

Published: 06 November 2012 Publication History

Abstract

In response to the increasing volume of trajectory data obtained, e.g., from tracking athletes, animals, or meteorological phenomena, we present a new space-efficient algorithm for the analysis of trajectory data. The algorithm combines techniques from computational geometry, data mining, and string processing and offers a modular design that allows for a user-guided exploration of trajectory data incorporating domain-specific constraints and objectives.

References

[1]

M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch. Replacing suffix trees with enhanced suffix arrays. Journal of Discrete Algorithms, 2:53--86, 2004.

Digital Library

[2]

H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. International Journal on Computational Geometry and Applications, 5:75--91, 1995.

[3]

Amisco. www.sport-universal.com.

[4]

K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, and J. Luo. Detecting commuting patterns by clustering subtrajectories. International Journal of Computational Geometry and Applications, 21(3):253--282, 2011.

[5]

M. Buchin, A. Driemel, M. J. van Kreveld, and V. Sacristan. An algorithmic framework for segmenting trajectories based on spatio-temporal criteria. In Proc. 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, pp. 202--211, 2010.

Digital Library

[6]

F. Chazal, D. Chen, L. J. Guibas, X. Jiang, and C. Sommer. Data-driven trajectory smoothing. In Proc. 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, pp. 251--260, 2011.

Digital Library

[7]

D. Z. Chen and O. Daescu. Space-efficient algorithms for approximating polygonal curves in two dimensional space. In Proc. 4th Annual International Conference on Computing and Combinatorics, pp. 45--54, 1998.

Digital Library

[8]

K. Chu and M. Wong. Fast time-series searching with scaling and shifting. In Proc. 18th ACM Symposium on Principles of Database Systems, pp. 237--248, 1999.

Digital Library

[9]

A. Efrat, S. Venkatasubramanian, and Q. Fan. Curve matching, time warping, and light fields: New algorithms for computing similarity between curves. Journal on Mathematic Imaging and Vision, 27(3):203--216, 2007.

Digital Library

[10]

M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. Second International Conference on Knowledge Discovery and Data Mining, pp. 226--231, 1996.

Digital Library

[11]

A. U. Frank. Socio-economic units: Their life and motion. In A. U. Frank, J. Raper, and J. P. Cheylan, editors, Life and motion of socio-economic units, pp. 21--34. Taylor & Francis, London, 2001.

[12]

S. Gaffney, A. Robertson, P. Smyth, S. Camargo, and M. Ghil. Probabilistic clustering of extratropical cyclones using regression mixture models. Climate Dynamic, 29(4):423--440, 2007.

[13]

S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In Proc. 5th ACM International Conference on Knowledge Discovery and Data Mining, pp. 63--72, 1999.

Digital Library

[14]

J. Gudmundsson, P. Laube, and T. Wolle. Computational movement analysis. In W. Kresse and D. Danko, editors, Springer Handbook of Geographic Information, pp. 725--741. Springer, 2012.

[15]

J. Gudmundsson and N. Valladares. A GPU approach to subtrajectory clustering using the Fréchet distance. Proc. 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, to appear, 2012.

Digital Library

[16]

J. Gudmundsson and T. Wolle. Football analysis using spatio-temporal tools. Proc. 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, to appear, 2012.

Digital Library

[17]

J. Harguess and J. K. Aggarwal. Semantic labeling of track events using time series segmentation and shape analysis. In 16th IEEE International Conference on Image Processing, pp. 4317--4320, 2009.

Digital Library

[18]

J. Hershberger and J. Snoeyink. Cartographic line simplification and polygon CSG formulae in O(n log* n) time. Computational Geometry: Theory and Applications, 11(3-4):93--103, 1998.

Digital Library

[19]

J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In Proc. 30th International Colloquium on Automata, Languages and Programming, pp. 943--955, 2003.

Digital Library

[20]

E. J. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and Information Systems, pp. 358--386, 2005.

Digital Library

[21]

M. P. Kwan. Interactive geovisualization of activity-travel patterns using three dimensional geographical information systems: A methodological exploration with a large data set. Transportation Research Part C, 8(1-6):185--203, 2000.

[22]

J. Larson, E. Bradlow, and P. Fader. An exploratory look at supermarket shopping paths. Intl. Journal of Research in Marketing, 22(4):395--414, 2005.

[23]

J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: A partition-and-group framework. In Proc. ACM International Conference on Management of Data, pp. 593--604, 2007.

Digital Library

[24]

J. Lin, E. J. Keogh, S. Lonardi, and B. Y.-C. Chiu. A symbolic representation of time series, with implications for streaming algorithms. In Proc. 8th ACM Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 2--11, 2003.

Digital Library

[25]

N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao, and D. Cheung. Mining, indexing, and querying historical spatiotemporal data. In Proc. 10th International ACM Conference On Knowledge Discovery and Data Mining, pp. 236--245, 2004.

Digital Library

[26]

H. Messel, A. Wells, and W. J. Green. The alligator region river systems. Pergamon Press, 1979.

[27]

R. Nathan. An emerging movement ecology paradigm. PNAS, 105(49):19050--1, 2008.

[28]

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

[29]

S. Rasetic, J. Sander, J. Elding, and M. A. Nascimento. A trajectory splitting model for efficient spatio-temporal indexing. In Proc. 31st International Conference on Very Large Data Bases, pp. 934--945, 2005.

Digital Library

[30]

C. Rutz and G. C. Hays. New frontiers in biologging science. Biology letters, 5(3):289--292, 2009.

[31]

Y. Sakurai, M. Yoshikawa, and C. Faloutsos. FTW: fast similarity search under the time warping distance. In Proc. 24th ACM Symposium on Principles of Database Systems, pp. 326--337, 2005.

Digital Library

[32]

G. K. Sandve and F. Drabløs. A survey of motif discovery methods in an integrated framework. Biology Direct, 11(1), 2006.

[33]

J. Shamoun-Baranes, E. van Loon, R. Purves, B. Speckmann, D. Weiskopf, and C. Camphuysen. Analysis and visualization of animal movement. Biology Letters, 8(1):6--9, 2012.

[34]

J. J. Thomas and K. A. Cook. A visual analytics agenda. IEEE Computer Graphics and Applications, 26(1):10--13, 2006.

Digital Library

[35]

M. Vlachos, D. Gunopoulos, and G. Kollios. Discovering similar multidimensional trajectories. In Proc. 18th International Conference on Data Engineering, pp. 673--682, 2002.

Digital Library

[36]

G. J. W. Webb and H. Messel. Movement and dispersal patterns of crocodylus porosus in some rivers of arnhem land, northern australia. Australian Wildlife Research, 5(2):263--283, 1978.

[37]

G. Welch and G. Bishop. An introduction to the Kalman filter. Technical Report TR 95-041, Dept. of Computer Science, UNC Chapel Hill, 1995. Updated June 2006, http://www.cs.unc.edu/~welch/kalman.

Digital Library

[38]

Y. Zhou and T. S. Huang. 'Bag of Segments' for motion trajectory analysis. In 15th IEEE International Conference on Image Processing, pp. 757--760, 2008.

Cited By

Zygouras NTroupiotis-Kapeliaris AZissis D(2024)EnvClus*: Extracting Common Pathways for Effective Vessel Trajectory ForecastingIEEE Access10.1109/ACCESS.2023.334908112(3860-3873)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3349081
Seep J(2023)Analyzing Semantically Enriched TrajectoriesKI - Künstliche Intelligenz10.1007/s13218-023-00818-538:3(127-131)Online publication date: 14-Nov-2023
https://doi.org/10.1007/s13218-023-00818-5
Seep JVahrenhold J(2021)K-means for semantically enriched trajectoriesProceedings of the 1st ACM SIGSPATIAL International Workshop on Animal Movement Ecology and Human Mobility10.1145/3486637.3489495(38-47)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3486637.3489495
Show More Cited By

Index Terms

Of motifs and goals: mining trajectory data
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Trajectory clustering: a partition-and-group framework
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories. Discovering common sub-trajectories ...
Clustering and aggregating clues of trajectories for mining trajectory patterns and routes

In this paper, we propose a new trajectory pattern mining framework, namely Clustering and Aggregating Clues of Trajectories (CACT), for discovering trajectory routes that represent the frequent movement behaviors of a user. In addition to spatial and ...
Cloud-assisted trajectory data management and analysis: a case study
CAN '17: Proceedings of the 2nd Workshop on Cloud-Assisted Networking

Massive trajectory data with spatio-temporal information are generated from various devices everyday. Due to a wide variety of devices and data collection methods, these data differ in terms of frequency and precision, which brings challenges to data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

November 2012

642 pages

ISBN:9781450316910

DOI:10.1145/2424321

General Chairs:
Isabel Cruz
University of Illinois at Chicago
,
Craig Knoblock
University of Southern California
,
Program Chairs:
Peer Kröger
Ludwig-Maximilians-Universität München, Germany
,
Egemen Tanin
University of Melbourne, Australia
,
Peter Widmayer
ETH Zürich, Switzerland

Copyright © 2012 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 ACM 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

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council

Conference

SIGSPATIAL'12

Sponsor:

SIGSPATIAL

SIGSPATIAL'12: SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems

November 6 - 9, 2012

Redondo Beach, California

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
611
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zygouras NTroupiotis-Kapeliaris AZissis D(2024)EnvClus*: Extracting Common Pathways for Effective Vessel Trajectory ForecastingIEEE Access10.1109/ACCESS.2023.334908112(3860-3873)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2023.3349081
Seep J(2023)Analyzing Semantically Enriched TrajectoriesKI - Künstliche Intelligenz10.1007/s13218-023-00818-538:3(127-131)Online publication date: 14-Nov-2023
https://doi.org/10.1007/s13218-023-00818-5
Seep JVahrenhold J(2021)K-means for semantically enriched trajectoriesProceedings of the 1st ACM SIGSPATIAL International Workshop on Animal Movement Ecology and Human Mobility10.1145/3486637.3489495(38-47)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3486637.3489495
Zygouras NSpiliopoulos GZissis D(2021)Detecting representative trajectories from global AIS datasets2021 IEEE International Intelligent Transportation Systems Conference (ITSC)10.1109/ITSC48978.2021.9564657(2278-2285)Online publication date: 19-Sep-2021
https://doi.org/10.1109/ITSC48978.2021.9564657
Tang BYiu MMouratidis KZhang JWang K(2021)On discovering motifs and frequent patterns in spatial trajectories with discrete Fréchet distanceGeoInformatica10.1007/s10707-021-00438-xOnline publication date: 26-Jun-2021
https://doi.org/10.1007/s10707-021-00438-x
Li LErfani SChan CLeckie C(2020)Discovery of contrast corridors from trajectory data in heterogeneous dynamic cellular networks2020 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN48605.2020.9207060(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/IJCNN48605.2020.9207060
Seep JVahrenhold J(2019)Inferring Semantically Enriched Representative TrajectoriesProceedings of the 1st ACM SIGSPATIAL International Workshop on Computing with Multifaceted Movement Data10.1145/3356392.3365220(1-4)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3356392.3365220
Agarwal PFox KMunagala KNath APan JTaylor EVan den Bussche JArenas M(2018)Subtrajectory ClusteringProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196972(75-87)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196972
Abdelaal MReichelt DDürr FRothermel KRunceanu LBecker SFritsch D(2018)ComNSenseProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31917332:1(1-26)Online publication date: 26-Mar-2018
https://dl.acm.org/doi/10.1145/3191733
Wan LWang ZLu ZFeng YQi HZhou WCao Q(2018)Approximate and Sublinear Spatial Queries for Large-Scale Vehicle NetworksIEEE Transactions on Vehicular Technology10.1109/TVT.2017.276174567:2(1561-1569)Online publication date: Feb-2018
https://doi.org/10.1109/TVT.2017.2761745
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