research-article

A general and parallel platform for mining co-movement patterns over large-scale trajectories

Authors:

Dongxiang Zhang,

Kian-Lee TanAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 10, Issue 4

Pages 313 - 324

https://doi.org/10.14778/3025111.3025114

Published: 01 November 2016 Publication History

Abstract

Discovering co-movement patterns from large-scale trajectory databases is an important mining task and has a wide spectrum of applications. Previous studies have identified several types of interesting co-movement patterns and show-cased their usefulness. In this paper, we make two key contributions to this research field. First, we propose a more general co-movement pattern to unify those defined in the past literature. Second, we propose two types of parallel and scalable frameworks and deploy them on Apache Spark. To the best of our knowledge, this is the first work to mine co-movement patterns in real life trajectory databases with hundreds of millions of points. Experiments on three real life large-scale trajectory datasets have verified the efficiency and scalability of our proposed solutions.

References

[1]

R. Agrawal, R. Srikant, et al. Fast algorithms for mining association rules. In VLDB, pages 487--499, 1994.

Digital Library

[2]

H. H. Aung and K.-L. Tan. Discovery of evolving convoys. In SSDM, pages 196--213, 2010.

Digital Library

[3]

J. Bao, Y. Zheng, D. Wilkie, and M. F. Mokbel. A survey on recommendations in location based social networks. In Geoinformatica, pages 525--543, 2015.

Digital Library

[4]

D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. In Cartographica, pages 112--122, 1973.

[5]

M. Ester, H.-P. Kriegel, J. Sander, X. Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pages 226--231, 1996.

Digital Library

[6]

J. Gudmundsson and M. van Kreveld. Computing longest duration flocks in trajectory data. In GIS, pages 35--42, 2006.

Digital Library

[7]

L. Guo, D. Zhang, G. Cong, W. Wu, and K.-L. Tan. Influence maximization in trajectory databases. In TKDE, page 1, 2016.

[8]

H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen. Discovery of convoys in trajectory databases. In VLDB, pages 1068--1080, 2008.

Digital Library

[9]

R. Jinno, K. Seki, and K. Uehara. Parallel distributed trajectory pattern mining using mapreduce. In CloudCom, pages 269--273, 2012.

Digital Library

[10]

P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In SSTD, pages 364--381, 2005.

Digital Library

[11]

Y. Kwon, M. Balazinska, B. Howe, and J. Rolia. Skewtune: mitigating skew in mapreduce applications. In SIGMOD, pages 25--36, 2012.

Digital Library

[12]

P. Laube, M. van Kreveld, and S. Imfeld. Finding remodetecting relative motion patterns in geospatial lifelines. In DSDH, pages 201--215. 2005.

[13]

X. Li, V. Ceikute, C. S. Jensen, and K.-L. Tan. Effective online group discovery in trajectory databases. In TKDE, pages 2752--2766, 2013.

Digital Library

[14]

X. Li, V. Ceikute, S. Jensen, Christian, and K.-L. Tan. Effective online group discovery in trajectory databases. 2013.

[15]

Y. Li, J. Bailey, and L. Kulik. Efficient mining of platoon patterns in trajectory databases. In DKE, pages 167--187, 2015.

Digital Library

[16]

Z. Li, B. Ding, J. Han, and R. Kays. Swarm: Mining relaxed temporal moving object clusters. In VLDB, pages 723--734, 2010.

Digital Library

[17]

Z. Li, B. Ding, J. Han, R. Kays, and P. Nye. Mining periodic behaviors for moving objects. In SIGKDD, pages 1099--1108, 2010.

Digital Library

[18]

J. Pei, J. Han, R. Mao, et al. Closet: An efficient algorithm for mining frequent closed itemsets. In DMKD, pages 21--30, 2000.

[19]

J. Wang, J. Han, and J. Pei. Closet+: Searching for the best strategies for mining frequent closed itemsets. In SIGKDD, pages 236--245, 2003.

Digital Library

[20]

Y. Wang, E.-P. Lim, and S.-Y. Hwang. Efficient mining of group patterns from user movement data. In DKE, pages 240--282, 2006.

Digital Library

[21]

J. S. Yoo and S. Shekhar. A joinless approach for mining spatial colocation patterns. In TKDE, pages 1323--1337, 2006.

Digital Library

[22]

M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In USENIX, pages 15--28, 2012.

Digital Library

[23]

K. Zheng, Y. Zheng, N. J. Yuan, and S. Shang. On discovery of gathering patterns from trajectories. In ICDE, pages 242--253, 2013.

Digital Library

[24]

Y. Zheng. Trajectory data mining: an overview. In TIST, pages 1--41, 2015.

Digital Library

[25]

Y. Zheng, Y. Liu, J. Yuan, and X. Xie. Urban computing with taxicabs. In UbiComp, pages 89--98, 2011.

Digital Library

Cited By

Francia MGallinucci EGolfarelli M(2024)Colossal Trajectory MiningExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.122055238:PDOnline publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.122055
Li PDai HZhou QChen YZhou QLi BYang G(2024)ECEQ: efficient multi-source contact event query processing for moving objectsWorld Wide Web10.1007/s11280-024-01309-927:6Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11280-024-01309-9
Tritsarolis AChondrodima ETampakis PPikrakis ATheodoridis Y(2024)Predicting Co-movement patterns in mobility dataGeoinformatica10.1007/s10707-022-00478-x28:2(221-243)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10707-022-00478-x
Show More Cited By

Recommendations

Efficient mining of regional movement patterns in semantic trajectories
Proceedings of the 43rd International Conference on Very Large Data Bases, Munich, Germany

Semantic trajectory pattern mining is becoming more and more important with the rapidly growing volumes of semantically rich trajectory data. Extracting sequential patterns in semantic trajectories plays a key role in understanding semantic behaviour of ...
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 ...
Mining Regular Patterns in Transactional Databases

The frequency of a pattern may not be a sufficient criterion for identifying meaningful patterns in a database. The temporal regularity of a pattern can be another key criterion for assessing the importance of a pattern in several applications. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 10, Issue 4

November 2016

180 pages

ISSN:2150-8097

Editors:
Peter Boncz
CWI
,
Ken Salem
University of Waterloo

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 November 2016

Published in PVLDB Volume 10, Issue 4

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
218
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Francia MGallinucci EGolfarelli M(2024)Colossal Trajectory MiningExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.122055238:PDOnline publication date: 15-Mar-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.122055
Li PDai HZhou QChen YZhou QLi BYang G(2024)ECEQ: efficient multi-source contact event query processing for moving objectsWorld Wide Web10.1007/s11280-024-01309-927:6Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s11280-024-01309-9
Tritsarolis AChondrodima ETampakis PPikrakis ATheodoridis Y(2024)Predicting Co-movement patterns in mobility dataGeoinformatica10.1007/s10707-022-00478-x28:2(221-243)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10707-022-00478-x
Zhao WYang PWang LChen H(2024)Meeting Pattern Detection from Trajectories in Road NetworkWeb and Big Data10.1007/978-981-97-7235-3_27(405-420)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7235-3_27
Zhang DMa THu JBei YTan KChen G(2023)Co-Movement Pattern Mining from VideosProceedings of the VLDB Endowment10.14778/3632093.363211917:3(604-616)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632119
Li KWang HChen ZChen L(2023)Relaxed group pattern detection over massive-scale trajectoriesFuture Generation Computer Systems10.1016/j.future.2023.02.028144:C(131-139)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.future.2023.02.028
Tian RZhang WWang FPolat KAlenezi F(2023)TinbaAdvanced Engineering Informatics10.1016/j.aei.2023.10206457:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.aei.2023.102064
Zhang DChang ZYang DLi DTan KChen KChen G(2023)SQUID: subtrajectory query in trillion-scale GPS databaseThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-022-00777-732:4(887-904)Online publication date: 19-Jan-2023
https://dl.acm.org/doi/10.1007/s00778-022-00777-7
Wang YButhpitiya SFabrikant ARenz MSarwat M(2022)Zebra regressionProceedings of the 30th International Conference on Advances in Geographic Information Systems10.1145/3557915.3561002(1-12)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1145/3557915.3561002
Tritsarolis AKontoulis YPelekis NTheodoridis Y(2021)MaSEC: Discovering Anchorages and Co-movement Patterns on Streaming Vessel TrajectoriesProceedings of the 17th International Symposium on Spatial and Temporal Databases10.1145/3469830.3470909(170-173)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1145/3469830.3470909
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents