ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

A parallel algorithm for mining user frequent moving patterns

  • College of Computer Science and Technology, Nanjing Normal University, Nanjing 210046, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.01.008
  • Received Date: 20 May 2017
  • Rev Recd Date: 23 June 2017
  • Publish Date: 31 January 2018
    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.

    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.
    • FullText(HTML)
  • loading
    • References(22)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 48 Issue 1 page: 57-64
    Cover

    Article Metrics

    Article views (565) PDF downloads(229)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return