A parallel algorithm for mining user frequent moving patterns

doi:10.3969/j.issn.0253-2778.2018.01.008

Abstract

Abstract: Through daily moving trajectories, one can effectively find the frequent moving rules, i.e., user frequent moving patterns. Based on PrefixSpan algorithm, a parallel algorithm named PASFORM is presented for mining user frequent moving patterns. PASFORM uses a new pruning strategy to reduce the search space and several time constraints to make mining results time-tagged. It also employs the parallel method to mine mass data and a prefix tree to save the store space. Experimental results show that PASFORM is effective and efficient.

Key words: frequent moving pattern mining, sequential pattern mining, prefix tree, parallelization

CLC Number:

TP391

ZHU Yibo, BAO Peiming, JI Genling. A parallel algorithm for mining user frequent moving patterns[J]. Journal of University of Science and Technology of China, 2018, 48(1): 57-64.

References

［1］
PENG W C, CHEN M S. Developing data allocation schemes by incremental mining of user moving patterns in a mobile computing system[J]. IEEE Transactions on Knowledge & Data Engineering, 2003, 15(1):70-85.
[2] 陈勐, 刘洋, 王月,等. 基于时序特征的移动模式挖掘[J]. 中国科学信息科学, 2016, 46(9): 1288-1297.
[3] 李雄, 马修军, 王晨星,等. 城市居民时空行为序列模式挖掘方法[J]. 地理与地理信息科学, 2009, 25(2): 10-14.
[4] LI Z H, DING B L, HAN J W, et al. Mining periodic behaviors for moving objects[C]// Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM Press, 2010: 1099-1108.
[5] YAVA��塁 G, KATSAROS D, ULUSOY , et al. A data mining approach for location prediction in mobile environments [J]. Data & Knowledge Engineering, 2005, 54(2): 121-146.
[6] LI Z H, HAN J W, JI M, et al. MoveMine: Mining moving object data for discovery of animal movement patterns[J]. ACM Transactions on Intelligent Systems & Technology, 2011, 2(4): No. 37(1-32).
[7] HUNG C C, PENG W C, LEE W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. The VLDB Journal, 2015, 24(2):169-192.
[8] LEE J G, HAN J W, LI X L. A unifying framework of mining trajectory patterns of various temporal tightness[J]. Knowledge & Data Engineering IEEE Transactions on, 2015, 27(6):1478-1490.
[9] 王亮, 汪梅, 郭鑫颖,等. 面向移动时空轨迹数据的频繁闭合模式挖掘[J]. 西安科技大学学报, 2016, 36(4): 573-576.
[10] HUANG Q Y, LI Z L, LI J, et al. Mining frequent trajectory patterns from online footprints[C]// Proceedings of the ACM SIGSPATIAL International Workshop on Geostreaming. Burlinggame, USA: ACM Press, 2016: No. 10(1-7).
[11] LEE J W, PAEK O H, RYU K H. Temporal moving pattern mining for location-based service[J]. Journal of Systems & Software, 2004, 73(3):481-490.
[12] Qiu M, Pi D. Mining Frequent Trajectory Patterns in Road Network Based on Similar Trajectory[M]// Intelligent Data Engineering and Automated Learning: IDEAL 2016, Springer International Publishing, 2016.
[13] 刘素杰. 时间标识的移动对象频繁模式发现[D]. 徐州：中国矿业大学, 2014.

[14] AGRAWAL R, SRIKANT R. Mining sequential patterns[C]// Proceedings of the 7th International Conference on Data Engineering. Taipei, China: IEEE Press, 1995:3-14.
[15] 王虎, 丁世飞. 序列模式挖掘研究与发展[J]. 计算机科学, 2009, 36(12): 14-17.
[16] RAO V C S, SAMMULAL P. Survey on sequential pattern mining algorithms[J]. International Journal of Computer Applications, 2013, 76(12): 24-31.
[17] SRIKANT R, AGRAWAL R. Mining sequential patterns: Generalizations and performance improvements[C]// Proceedings of the 5th International Conference on Extending Database Technology. London: Springer, 1996: 3-17.
[18] HAN J W, PEI J, MORTAZAVI-ASL B, et al. FreeSpan: Frequent pattern-projected sequential pattern mining[C]// Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston: ACM Press, 2000: 355-359.
[19] PEI J, HAN J W, MORTAZAVI-ASL B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]// Proceedings of the 17th International Conference on Data Engineering. Heidelberg, Germany: IEEE Press, 2001: 215-224.
[20] LIU J, YAN S, REN J. The design of frequent sequence tree in incremental mining of sequential patterns[C]// Proceedings of the 2nd International Conference on Software Engineering and Service Science. Beijing: IEEE Press, 2011: 679-682.
[21] Reality Commoms[EB/OL]. [2017-05-06]http://realitycommons.media.mit.edu/realitymining.html.
[22] System Data[EB/OL]. [2017-05-06]https://www.citibikenyc.com/system-data.

()
(

[1]	ZHAN Yongkun, YANG Wenfei, ZHANG Tianzhu. Relation aware network for weakly-supervised temporal action localization [J]. Journal of University of Science and Technology of China, 2021, 51(10): 753-765.
[2]	Liang Qipeng, Zhu Qiaohui, Kang Yu, Zhao YunBo. Estimation based approximating control for wireless networked control systems [J]. Journal of University of Science and Technology of China, 2021, 51(4): 327-334.
[3]	Li Huicong, Fu Xiaoming∗ . Anisotropic surface meshing using locally isometric embedding [J]. Journal of University of Science and Technology of China, 2020, 50(12): 1460-1471.
[4]	YU Jun, LI Yajie, CHENG Lilei, LIAN Shun, TAN Chang, DING Decheng, Liu Qi. Research and practice of plagiarism detection in program code assignments by college students [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1048-1057.
[5]	ZHANG Wenjing, BAN Zhijie. Citation network’s influence maximization algorithm based on global influence [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1058-1063.
[6]	REN Min, XU Ling, WANG Feng, WU Chao. Campus encyclopedia platform based on knowledge recommendation [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1072-1076.
[7]	SUN Lei, ZHANG Yining, XUE Yanfang, QIAO Lishan, ZHANG Limei. Adaptive functional connectivity network learning and application in brain disorders identification [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1102-1109.
[8]	BAI Jiangbo, YANG Yang, ZHANG Wensheng. A simulation of the synthetic aperture radar image based on improved CycleGAN [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1181-1186.
[9]	XIN Shouyu, ZHENG Ruirui, ZHOU Yu, LIU Wenpeng, HE Jianjun. A one-shot learning algorithm using support set information during training [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1187-1192.
[10]	WANG Zhihua, KANG Hongmei. Using splines on triangular mesh to solve PDE with nonhomogeneous boundary [J]. Journal of University of Science and Technology of China, 2020, 50(7): 901-905.
[11]	GONG Lejun , ZHOU Shehai, CHENG Yifei, GAO Zhihong, LI Huakang. Identification of PBMC-related cells of single cell RNA sequence data [J]. Journal of University of Science and Technology of China, 2020, 50(7): 1013-1018.
[12]	DU Shuying, DU Peng, DING Shifei. A malicious domain name detection method based on CNN [J]. Journal of University of Science and Technology of China, 2020, 50(7): 1019-1025.
[13]	LI Yongjun, CAO Weihua, LING Qiang. A multi-target tracking algorithm based on feature point trajectories [J]. Journal of University of Science and Technology of China, 2020, 50(6): 726-732.
[14]	. A modified coherent diffraction algorithm based on the total variation algorithm for insufficient data [J]. Journal of University of Science and Technology of China, 2020, 50(4): 418-427.
[15]	WANG Xuhui, YAN Mingye, WU Meng. Suitable for the construction of degenerate smooth interpolated surfaces patches in isogeometric analysis [J]. Journal of University of Science and Technology of China, 2020, 50(3): 335-342.