Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Approach to discovering companion patterns based on traffic data stream

  • Author(s): Meiling Zhu 1, 2, 3 ; Chen Liu 2, 3 ; Yanbo Han 2, 3
    • View affiliations
  • Source: Volume 12, Issue 10, December 2018, p. 1351 – 1359
    DOI:  10.1049/iet-its.2018.5166 , Print ISSN 1751-956X, Online ISSN 1751-9578
© The Institution of Engineering and Technology
Received 01/10/2017, Accepted 07/08/2018, Revised 25/04/2018, Published 07/09/2018

A companion of moving objects is an object group that move together in a period of time. Platoon companions are a generalised companion pattern, which describes a group of objects that move together for time segments, each with some minimum consecutive duration of time. This study proposes a method that can instantly discover platoon companions from a special kind of streaming traffic data, called automatic number plate recognition data. Compared to related approaches, the authors transform the companion discovery into a frequent sequence mining problem. The authors propose a data structure, platoon tree (PTree), to record discovered platoon companions. To reduce the cost of tree traversal during mining platoon companions, they utilise the last two together-moving objects of a group to update PTree. Finally, a lot of experiments have been carried out to show the efficiency and effectiveness of the proposed approach.

Inspec keywords: data structures; tree data structures; traffic engineering computing; trees (mathematics); data mining

Other keywords: time segments; traffic data stream; companion patterns; mining platoon companions; data structure; called automatic number plate recognition data; related approaches; platoon tree; frequent sequence mining problem; discovered platoon companions; object group; generalised companion pattern; companion discovery

Subjects: Data handling techniques; Knowledge engineering techniques

References

    1. 1)
      • 16. Kriege, H.P., Pfeifle, M.: ‘Density-based clustering of uncertain data’. Proc. 11th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), Chicago, Illinois, USA, August 2005, pp. 672–677.
    2. 2)
      • 50. Gao, C., Wang, J., Yang, Q.: ‘Efficient mining of closed sequential patterns on stream sliding window’. Proc. IEEE 11th Int. Conf. Data Mining (ICDM), Vancouver, BC, Canada, January 2011, pp. 1044–1049.
    3. 3)
      • 30. Zaki, M.J.: ‘SPADE: an efficient algorithm for mining frequent sequences’, Mach. Learn., 2001, 42, (1/2), pp. 31–60.
    4. 4)
      • 22. Zhang, J., Li, J., Wang, S., et al: ‘On retrieving moving objects gathering patterns from trajectory data via spatio-temporal graph’. Proc. IEEE Int. Congress Big Data (Big Data), Anchorage, AK, USA, June 2014, pp. 390–397.
    5. 5)
      • 42. Qiao, S., Tang, C., Dai, S., et al: ‘Partspan: parallel sequence mining of trajectory patterns’. Proc. 5th Int. Conf. on Fuzzy Systems and Knowledge Discovery (FSKD), Jinan, Shandong, China, October 2008, pp. 363–367.
    6. 6)
      • 46. Cheng, H., Yan, X., Han, J.: ‘IncSpan: incremental mining of sequential patterns in large database’. Proc. 10th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), Seattle, Washington, USA, August 2004, pp. 527–532.
    7. 7)
      • 35. Wang, J., Han, J., Li, C.: ‘Frequent closed sequence mining without candidate maintenance’, IEEE Trans. Knowl. Data Eng., 2007, 19, (8), pp. 1042–1056.
    8. 8)
      • 31. Ayres, J., Flannick, J., Gehrke, J., et al: ‘Sequential pattern mining using a bitmap representation’. Proc. 8th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Edmonton, Alberta, Canada, July 2002, pp. 429–435.
    9. 9)
      • 8. Tang, L.A., Zheng, Y., Yuan, J., et al: ‘A framework of traveling companion discovery on trajectory data streams’, ACM Trans. Intell. Syst. Technol., 2013, 5, (1), pp. 1–34.
    10. 10)
      • 33. Pei, J., Han, J., Mortazavi-Asl, B., et al: ‘Prefixspan: mining sequential patterns efficiently by prefix-projected pattern growth’. Proc. IEEE 17th Int. Conf. Data Engineering (ICDE), Heidelberg, Germany, August 2001, pp. 215–224.
    11. 11)
      • 19. Silva, T.L.C.D., Zeitouni, K., Macêdo, J.A.F.D., et al: ‘A framework for online mobility pattern discovery from trajectory data streams’. IEEE Int. Conf. on Mobile Data Management (MDM), Porto, Portugal, June 2016, pp. 365–368.
    12. 12)
      • 17. Jensen, C.S., Lin, D., Ooi, B.C.: ‘Continuous clustering of moving objects’, IEEE Trans. Knowl. Data Eng., 2007, 19, (9), pp. 1161–1174.
    13. 13)
      • 41. Ma, C., Li, Q.: ‘Parallel algorithm for mining frequent closed sequences’. Proc. Int. Workshop on Autonomous Intelligent Systems: Agents and Data Mining (AIS-ADM), Petersburg, Russia, June 2005, pp. 184–192.
    14. 14)
      • 9. Nautiyal, A., Lal, R.P.: ‘Time-efficient discovery of moving object groups from trajectory data’. Proc. Innovations in Computer Science and Engineering (ICICSE), Singapore, June 2017, pp. 185–192.
    15. 15)
      • 5. Jeung, H., Yiu, M. L., Zhou, X., et al: ‘Discovery of convoys in trajectory databases’, Proc. VLDB Endowment, 2008, 1, (1), pp. 1068–1080.
    16. 16)
      • 21. Yoo, J.S., Boulware, D., Kimmey, D: ‘A parallel spatial co-location mining algorithm based on map reduce’. Proc. IEEE Int. Congress on Big Data (BigData Congress), Anchorage, AK, USA, June 2014, pp. 25–31.
    17. 17)
      • 37. Pei, J., Han, J., Wang, W.: ‘Constraint-based sequential pattern mining: the pattern-growth methods’, J. Intell. Inf. Syst., 2007, 28, (2), pp. 133–160.
    18. 18)
      • 3. Vieira, M.R., Bakalov, P., Tsotras, V.J.: ‘On-line discovery of flock patterns in spatio-temporal data’. Proc. 17th ACM Int. Symp. on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS), Seattle, Washington, USA, November 2009, pp. 286–295.
    19. 19)
      • 39. Demiriz, A.: ‘webSPADE: a parallel sequence mining algorithm to analyze web log data’. Proc. IEEE Int. Conf. on Data Mining (ICDM), Maebashi, Japan, December 2002, pp. 755–758.
    20. 20)
      • 18. Wang, Y., Luo, Z., Takekawa, J., et al: ‘A new method for discovering behavior patterns among animal movements’, Int. J. Geogr. Inf. Sci., 2015, 30, (5), pp. 929–947.
    21. 21)
      • 10. Li, Y., Bailey, J., Kulik, L.: ‘Efficient mining of platoon patterns in trajectory databases’, Data Knowl. Eng., 2015, 100, pp. 167–187.
    22. 22)
      • 23. Zhang, J., Li, J., Liu, Z., et al: ‘Moving objects gathering patterns retrieving based on spatio-temporal graph’, Int. J. Web Serv. Res., 2016, 13, (3), pp. 88–107.
    23. 23)
      • 45. Chang, L., Wang, T., Yang, D., et al: ‘SeqStream: mining closed sequential patterns over stream sliding windows’. Proc. 8th IEEE Int. Conf. on Data Mining (ICDM), Pisa, Italy, February 2008, pp. 83–92.
    24. 24)
      • 4. Jeung, H., Shen, H.T., Zhou, X.: ‘Convoy queries in spatio-temporal databases’. Proc. IEEE 24th Int. Conf. Data Engineering (ICDE), Cancun, Mexico, April 2008, pp. 1457–1459.
    25. 25)
      • 2. Gudmundsson, J., Van Kreveld, M.: ‘Computing longest duration flocks in trajectory data’. Proc. 14th Annual ACM Int. Symp. on Advances in Geographic Information Systems (ACM GIS), Arlington, Virginia, USA, November 2006, pp. 35–42.
    26. 26)
      • 32. Han, J., Pei, J., Mortazavi-Asl, B., et al: ‘Freespan: frequent pattern-projected sequential pattern mining’. Proc. 6th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Boston, MA, USA, August 2000, pp. 355–359.
    27. 27)
      • 29. Srikant, R., Agrawal, R.: ‘Mining sequential patterns: generalizations and performance improvements’. Proc. 5th Int. Conf. Extending Data Base Technology (EDBT), Avignon, France, March 1996, pp. 3–17.
    28. 28)
      • 24. Xian, Y., Liu, Y., Xu, C.: ‘Parallel gathering discovery over big trajectory data’. IEEE Int. Conf. on Big Data (Big Data), Washington, DC, USA, December 2016, pp. 783–792.
    29. 29)
      • 44. Kessl, R.: ‘Probabilistic static load-balancing of parallel mining of frequent sequences’, IEEE Trans. Knowl. Data Eng., 2016, 28, (5), pp. 1299–1311.
    30. 30)
      • 27. Mooney, C.H., Roddick, J.F.: ‘Sequential pattern mining: approaches and algorithms’, ACM Comput. Surv., 2013, 45, (2), pp. 94–111.
    31. 31)
      • 28. Agrawal, R., Srikant, R.: ‘Mining sequential patterns’. Proc. 1995 IEEE 11th Int. Conf. on Data Engineering (ICDE), Taipei, Taiwan, March 1995, pp. 3–14.
    32. 32)
      • 7. Tang, L.A., Zheng, Y., Yuan, J., et al: ‘On discovery of traveling companions from streaming trajectories’. Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE), Washington, DC, USA, April 2012, pp. 186–197.
    33. 33)
      • 11. Han, Y., Wang, G., Yu, J., et al: ‘A service-based approach to traffic sensor data integration and analysis to support community-wide green commute in China’, IEEE Trans. Intell. Transp. Syst., 2016, 17, (9), pp. 1–10.
    34. 34)
      • 1. Laube, P., Imfeld, S.: ‘Analyzing relative motion within groups of trackable moving point objects’. Proc. Second Int. Conf. on Advances in Geographic Information Systems (GIScience), Boulder, CO, USA, September 2002, pp. 132–144.
    35. 35)
      • 15. Li, Y., Han, J., Yang, J.: ‘Clustering moving objects’. Proc. 10th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), Seattle, Washington, USA, August 2004, pp. 617–622.
    36. 36)
      • 20. Zheng, K., Zheng, Y., Yuan, N.J., et al: ‘Online discovery of gathering patterns from trajectories’, IEEE Trans. Knowl. Data Eng., 2014, 26, (8), pp. 1974–1988.
    37. 37)
      • 48. Ho, C.C., Li, H.F., Kuo, F.F., et al: ‘Incremental mining of sequential patterns over a stream sliding window’. Workshops Proc. IEEE 6th Int. Conf. on Data Mining (ICDM - Workshops), Hong Kong, China, January 2006, pp. 677–681.
    38. 38)
      • 40. Guralnik, V., Karypis, G.: ‘Parallel tree-projection-based sequence mining algorithms’, Parallel Comput., 2004, 30, (4), pp. 443–472.
    39. 39)
      • 36. Pinto, H., Han, J., Pei, J., et al: ‘Multi-dimensional sequential pattern mining’. Proc. 10th Int. Conf. on Information and Knowledge Management (CIMK), Atlanta, Georgia, USA, January 2001, pp. 81–88.
    40. 40)
      • 49. Yuan, D., Lee, K., Cheng, H., et al: ‘CISpan: comprehensive incremental mining algorithms of closed sequential patterns for multi-versional software mining’. Proc. 8th SIAM Int. Conf. Data Mining (SDM), Atlanta, Georgia, USA, April 2008, pp. 84–95.
    41. 41)
      • 34. Yan, X., Han, J., Afshar, R.: ‘Clospan: mining closed sequential patterns in large databases’. Proc. Third SIAM Int. Conf. Data Mining (SDM), San Francisco, CA, USA, May 2003, pp. 166–177.
    42. 42)
      • 43. Yu, D., Wu, W., Zheng, S., et al: ‘BIDE-based parallel mining of frequent closed sequences with mapreduce’. Proc. 12th Int. Conf. on Algorithms and Architectures for Parallel Processing (ICA3PP), Fukuoka, Japan, November 2012, pp. 177–186.
    43. 43)
      • 47. Chen, G., Wu, X., Zhu, X.: ‘Sequential pattern mining in multiple streams’. Proc. IEEE 5th Int. Conf. Data Mining (ICDM), Houston, Texas, USA, November 2005, pp. 585–588.
    44. 44)
      • 14. Kalnis, P., Mamoulis, N., Bakiras, S.: ‘On discovering moving clusters in spatio-temporal data’. Proc. Ninth Int. Symp. on Spatial and Temporal Databases (SSTD), Santorini Island, Greece, August 2005, pp. 364–381.
    45. 45)
      • 25. Yu, Y., Wang, Q., Wang, X.: ‘Continuous clustering trajectory stream of moving objects’, China Commun., 2013, 10, (9), pp. 120–129.
    46. 46)
      • 26. Yu, Y., Wang, Q., Wang, X., et al: ‘Online clustering for trajectory data stream of moving objects’, Comput. Sci. Inf. Syst., 2013, 10, (3), pp. 1293–1317.
    47. 47)
      • 13. Liu, C., Wang, X., Zhu, M., et al: ‘Discovering companion vehicles from live streaming traffic data’. Proc. 17th Asia-Pacific Web Conf. (APWeb), Suzhou, China, September 2016, pp. 116–128.
    48. 48)
      • 12. Zhu, M., Liu, C., Wang, J., et al: ‘A service-friendly approach to discover traveling companions based on ANPR data stream’. Proc. IEEE Int. Conf. on Services Computing (SCC), San Francisco, CA, USA, June 2016, pp. 171–178.
    49. 49)
      • 6. Li, Z., Ding, B., Han, J., et al: ‘Swarm: mining relaxed temporal moving object clusters’, Proc. VLDB Endowment, 2010, 3, (1), pp. 723–734.
    50. 50)
      • 38. Chueh, H.E.: ‘Mining target-oriented sequential patterns with time-intervals’, Int. J. Comput. Sci. Inf. Technol., 2010, 2, (4), pp. 113–123.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2018.5166
Loading

Related content

content/journals/10.1049/iet-its.2018.5166
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address