article

Efficient mining of group patterns from user movement data

Authors:

San-Yih HwangAuthors Info & Claims

Data & Knowledge Engineering, Volume 57, Issue 3

Pages 240 - 282

https://doi.org/10.1016/j.datak.2005.04.006

Published: 01 June 2006 Publication History

Abstract

In this paper, we present a new approach to derive groupings of mobile users based on their movement data. We assume that the user movement data are collected by logging location data emitted from mobile devices tracking users. We formally define group pattern as a group of users that are within a distance threshold from one another for at least a minimum duration. To mine group patterns, we first propose two algorithms, namely AGP and VG-growth. In our first set of experiments, it is shown when both the number of users and logging duration are large, AGP and VG-growth are inefficient for the mining group patterns of size two. We therefore propose a framework that summarizes user movement data before group pattern mining. In the second series of experiments, we show that the methods using location summarization reduce the mining overheads for group patterns of size two significantly. We conclude that the cuboid based summarization methods give better performance when the summarized database size is small compared to the original movement database. In addition, we also evaluate the impact of parameters on the mining overhead.

References

[1]

{1} R. Agrawal, C. Faloutsos, A. Swami, Efficient similarity search in sequence databases, in: Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, Chicago, 1993.

Digital Library

[2]

{2} R. Agrawal, K.-I. Lin, H. Sawhney, K. Shim, Fast similarity search in the presence of noise, scaling, and translation in time-series databases, in: Proceedings of VLDB'95, Zurich, Switzerland, 1995.

[3]

{3} R. Agrawal, R. Srikant, Fast algorithms for mining association rules, in: Proceedings of the 20th International Conference on Very Large Databases, Santiago, Chile, 1994, pp. 487-499.

Digital Library

[4]

{4} R. Agrawal, R. Srikant, Mining sequential patterns, in: Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, 1995, pp. 3-14.

Digital Library

[5]

{5} B. Hofmann-Wellenhof, H. Lichtenegger, J. Collins, third revised ed.Global Positioning System: Theory and Practice, vol. I, Springer-Verlag Wien, New York, 1994.

[6]

{6} G. Chen, D. Kotz, A Survey of Context-Aware Mobile Computing Research, Dartmouth Computer Science Technical Report TR2000-381, Department of Computer Science, Dartmouth College, 2000.

Digital Library

[7]

{7} D. Forsyth, Group Dynamics, third ed., Wadsworth, Belmont, CA, 1999.

[8]

{8} G. Giaglis, P. Kourouthanasis, A. Tsamakos, Mobile Commerce: Technology, Theory, and Applications, Idea Group Publishing, 2002, Ch. Towards a Classification Network for Mobile Location Services.

[9]

{9} J. Han, G. Dong, Y. Yin, Efficient mining of partial periodic patterns in time series database, in: Proceedings of the 15th International Conference on Data Engineering, 1999, pp. 106-115.

Digital Library

[10]

{10} J. Han, W. Gong, Y. Yin, Mining segment-wise periodic patterns in time-related databases, in: Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, 1998, pp. 214-218.

[11]

{11} J. Han, J. Pei, Y. Yin, Mining frequent patterns without candidate generation, in: Proceedings of the International Conference on Management of Data, Dallas, TX, 2000.

[12]

{12} X. Hong, M. Gerla, Dynamic group discovery and routing in ad hoc networks, in: Proceedings of the First Annual Mediterranean Ad Hoc Networking Workshop (Med-hoc-Net 2002), Sardegna, Italy, 2002.

[13]

{13} Y. Huh, C. Kim, Group-based location management scheme in personal communications networks, :in: 16th International Conference on Information Networking (ICOIN-16), Korea, 2002.

[14]

{14} J. Kaufman, J. Myllymaki, J. Jackson, IBM Almaden Research Center. Available from: 〈http://www.alpha-works.ibm.com/tech/citysimulator〉 (December 2001).

[15]

{15} G.H.K. Lam, H.V. Leong, S.C.F. Chan, GBL: Group-based location updating in mobile wireless environment, in: 9th International Conference on Database Systems for Advanced Applications (DASFAA 2004), Korea, 2004.

[16]

{16} H. Mannila, H. Toivonen, A.I. Verkamo, Discovery of frequent episodes in event sequences, Data Mining and Knowledge Discovery 1 (3) (1997) 259-289.

[17]

{17} B. Özden, S. Ramaswamy, A. Silberschatz, Cyclic association rules, in: Proceedings of the 14th International Conference on Data Engineering, Orlando, Florida, USA, 1998, pp. 412-421.

Digital Library

[18]

{18} J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M.-C. Hsu, PrefixSpan mining sequential patterns efficiently by prefix projected pattern growth, in: Proceedings of the 17th International Conference on Data Engineering (ICDE'01), 2001, pp. 215-226. Available from: 〈citeseer.ist.psu.edu/article/pei01prefixspan.html〉.

[19]

{19} J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal, M.-C. Hsu, Mining sequential patterns by pattern-growth: the PrefixSpan approach, IEEE Transactions on Knowledge and Data Engineering 16 (11) (2004) 1424-1440.

Digital Library

[20]

{20} J. Pei, J. Han, W. Wang, Mining sequential patterns with constraints in large databases, in: Proceedings of 2002 International Conference on Information and Knowledge Management (CIKM'02), 2002.

[21]

{21} G.-C. Roman, Q. Huang, A. Hazemi, Consistent group membership in ad hoc networks, in: International Conference on Software Engineering, 2001, pp. 381-388.

[22]

{22} J. Sehafer, J. Konstan, J. Riedl, E-commerce recommendation applications, Data Mining and Knowledge Discovery 5 (1/2) (2001) 115-153.

[23]

{23} S. Shekhar, Y. Huang, Discovering spatial co-location patterns: a summary of results, Lecture Notes in Computer Science 2121 (2001) 236-256. Available from: 〈citeseer.ist.psu.edu/article/shekhar01discovering.html〉.

[24]

{24} R. Srikant, R. Agrawal, Mining sequential patterns: generalizations and performance improvements, in: P.M.G. Apers, M. Bouzeghoub, G. Gardarin (Eds.), Proceedings of the 5th International Conference on Extending Database Technology, EDBT, vol. 1057, Springer-Verlag, 1996, pp. 3-17. Available from: 〈citeseer.nj.nec.com/ article/srikant96mining.html〉.

[25]

{25} M. Vlachos, G. Kollios, D. Gunopoulos, Discovering similar multidimensional trajectories, in: Proceedings of the 18th International Conference on Data Engineering (ICDE'02), San Jose, CA, 2002.

[26]

{26} W. Wang, J. Yang, P. Yu, Infominer+: mining partial periodic patterns with gap penalties, in: Proceedings of the 2nd IEEE International Conference on Data Mining (ICDM), 2002.

[27]

{27} Y. Wang, E.-P. Lim, S.-Y. Hwang, On mining group patterns of mobile users, in: Proceedings of the 14th International Conference on Database and Expert Systems Applications--DEXA 2003, Prague, Czech Republic, 2003.

[28]

{28} Y. Wang, E.-P. Lim, S.-Y. Hwang, Efficient group pattern mining using data summarization, in: Proceedings of the 9th International Conference on Database Systems for Advanced Applications--DASFAA 2004, Jeju Island, Korea, 2004.

[29]

{29} J. Yang, W. Wang, P. Yu, Mining asynchronous periodic patterns in time series data, IEEE Transaction on Knowledge and Data Engineering (TKDE) 15 (3) (2003) 613-628.

Digital Library

[30]

{30} J. Yang, P. Yu, W. Wang, J. Han, Mining long sequential patterns in a noisy environment, in: Proceedings of 2002 ACM-SIGMOD International Conference on Management of Data (SIGMOD'02), 2002.

Digital Library

[31]

{31} M.J. Zaki, SPADE: an efficient algorithm for mining frequent sequences Special Issue on Unsupervised Learning (Doug Fisher, ed.), Machine Learning Journal 42 (2001) 31-60.

Digital Library

[32]

{32} P. ZarchanGlobal Positioning System: Theory and Applications, vol. I, American Institute of Aeronautics and Astronautics, 1996.

[33]

{33} V. Zeimpekis, G.M. Giaglis, G. Lekakos, A taxonomy of indoor and outdoor positioning techniques for mobile location services, SIGecom Exchanges, ACM vol. 3.4, 2003, pp. 19-27.

Cited By

Anowar MShamail AAlbertsen AHall BThielen TRiemersma BTrajcevski G(2024)Detecting and Visualizing Bond-Forming Convoys in Atomic and Molecular TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691264(657-660)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3691264
Wang CChen LFeng SShang S(2024)Flexible Contact Correlation Learning on Spatio-Temporal TrajectoriesDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_10(152-168)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5552-3_10
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
Show More Cited By

Index Terms

Efficient mining of group patterns from user movement data

Recommendations

On Mining Movement Pattern from Mobile Users
Heterogenous Wireless Ad Hoc and Sensor Networks

In the era in which activities performed by mobile users are tracked through various sensing mechanisms, the movement data collected through these sensors is submitted into a data mining algorithm in order to determine the movement pattern. The movement ...
Efficient algorithms for mining constrained frequent patterns from uncertain data
U '09: Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data

Mining of frequent patterns is one of the popular knowledge discovery and data mining (KDD) tasks. It also plays an essential role in the mining of many other patterns such as correlation, sequences, and association rules. Hence, it has been the subject ...
Mining User Behavioral Rules from Smartphone Data Through Association Analysis
Advances in Knowledge Discovery and Data Mining
Abstract
The increasing popularity of smart mobile phones and their powerful sensing capabilities have enabled the collection of rich contextual information and mobile phone usage records through the device logs. This paper formulates the problem of mining ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Data & Knowledge Engineering

Data & Knowledge Engineering Volume 57, Issue 3

June 2006

90 pages

ISSN:0169-023X

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anowar MShamail AAlbertsen AHall BThielen TRiemersma BTrajcevski G(2024)Detecting and Visualizing Bond-Forming Convoys in Atomic and Molecular TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691264(657-660)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3691264
Wang CChen LFeng SShang S(2024)Flexible Contact Correlation Learning on Spatio-Temporal TrajectoriesDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_10(152-168)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5552-3_10
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
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
Chen LChao PFang JChen WXu JZhao L(2021)Disatra: A Real-Time Distributed Abstract Trajectory ClusteringWeb Information Systems Engineering – WISE 202110.1007/978-3-030-90888-1_47(619-635)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-90888-1_47
Monteiro DCoelho dos Santos RFerreira K(2020)Mining Partners in TrajectoriesInternational Journal of Data Warehousing and Mining10.4018/IJDWM.202001010216:1(22-38)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.4018/IJDWM.2020010102
Yadamjav MBao ZZheng BChoudhury FSamet H(2020)Querying Recurrent Convoys over Trajectory DataACM Transactions on Intelligent Systems and Technology10.1145/340073011:5(1-24)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3400730
Zhuang YMa CXie JLi ZYue Y(2020)A Fast Clustering Approach for Identifying Traffic CongestionsSpatial Data and Intelligence10.1007/978-3-030-69873-7_1(3-13)Online publication date: 8-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-69873-7_1
Chen LGao YFang ZMiao XJensen CGuo C(2019)Real-time distributed co-movement pattern detection on streaming trajectoriesProceedings of the VLDB Endowment10.14778/3339490.333950212:10(1208-1220)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.14778/3339490.3339502
Naserian EWang XXu XDong Y(2018)A Framework of Loose Travelling Companion Discovery from Human TrajectoriesIEEE Transactions on Mobile Computing10.1109/TMC.2018.281336917:11(2497-2511)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TMC.2018.2813369
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents