Approach to discovering companion patterns based on traffic data stream

Approach to discovering companion patterns based on traffic data stream

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Intelligent Transport Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    1. 1)
      • 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. 132144.
    2. 2)
      • 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. 3542.
    3. 3)
      • 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. 286295.
    4. 4)
      • 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. 14571459.
    5. 5)
      • 5. Jeung, H., Yiu, M. L., Zhou, X., et al: ‘Discovery of convoys in trajectory databases’, Proc. VLDB Endowment, 2008, 1, (1), pp. 10681080.
    6. 6)
      • 6. Li, Z., Ding, B., Han, J., et al: ‘Swarm: mining relaxed temporal moving object clusters’, Proc. VLDB Endowment, 2010, 3, (1), pp. 723734.
    7. 7)
      • 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. 186197.
    8. 8)
      • 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. 134.
    9. 9)
      • 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. 185192.
    10. 10)
      • 10. Li, Y., Bailey, J., Kulik, L.: ‘Efficient mining of platoon patterns in trajectory databases’, Data Knowl. Eng., 2015, 100, pp. 167187.
    11. 11)
      • 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. 110.
    12. 12)
      • 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. 171178.
    13. 13)
      • 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. 116128.
    14. 14)
      • 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. 364381.
    15. 15)
      • 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. 617622.
    16. 16)
      • 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. 672677.
    17. 17)
      • 17. Jensen, C.S., Lin, D., Ooi, B.C.: ‘Continuous clustering of moving objects’, IEEE Trans. Knowl. Data Eng., 2007, 19, (9), pp. 11611174.
    18. 18)
      • 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. 929947.
    19. 19)
      • 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. 365368.
    20. 20)
      • 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. 19741988.
    21. 21)
      • 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. 2531.
    22. 22)
      • 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. 390397.
    23. 23)
      • 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. 88107.
    24. 24)
      • 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. 783792.
    25. 25)
      • 25. Yu, Y., Wang, Q., Wang, X.: ‘Continuous clustering trajectory stream of moving objects’, China Commun., 2013, 10, (9), pp. 120129.
    26. 26)
      • 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. 12931317.
    27. 27)
      • 27. Mooney, C.H., Roddick, J.F.: ‘Sequential pattern mining: approaches and algorithms’, ACM Comput. Surv., 2013, 45, (2), pp. 94111.
    28. 28)
      • 28. Agrawal, R., Srikant, R.: ‘Mining sequential patterns’. Proc. 1995 IEEE 11th Int. Conf. on Data Engineering (ICDE), Taipei, Taiwan, March 1995, pp. 314.
    29. 29)
      • 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. 317.
    30. 30)
      • 30. Zaki, M.J.: ‘SPADE: an efficient algorithm for mining frequent sequences’, Mach. Learn., 2001, 42, (1/2), pp. 3160.
    31. 31)
      • 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. 429435.
    32. 32)
      • 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. 355359.
    33. 33)
      • 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. 215224.
    34. 34)
      • 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. 166177.
    35. 35)
      • 35. Wang, J., Han, J., Li, C.: ‘Frequent closed sequence mining without candidate maintenance’, IEEE Trans. Knowl. Data Eng., 2007, 19, (8), pp. 10421056.
    36. 36)
      • 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. 8188.
    37. 37)
      • 37. Pei, J., Han, J., Wang, W.: ‘Constraint-based sequential pattern mining: the pattern-growth methods’, J. Intell. Inf. Syst., 2007, 28, (2), pp. 133160.
    38. 38)
      • 38. Chueh, H.E.: ‘Mining target-oriented sequential patterns with time-intervals’, Int. J. Comput. Sci. Inf. Technol., 2010, 2, (4), pp. 113123.
    39. 39)
      • 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. 755758.
    40. 40)
      • 40. Guralnik, V., Karypis, G.: ‘Parallel tree-projection-based sequence mining algorithms’, Parallel Comput., 2004, 30, (4), pp. 443472.
    41. 41)
      • 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. 184192.
    42. 42)
      • 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. 363367.
    43. 43)
      • 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. 177186.
    44. 44)
      • 44. Kessl, R.: ‘Probabilistic static load-balancing of parallel mining of frequent sequences’, IEEE Trans. Knowl. Data Eng., 2016, 28, (5), pp. 12991311.
    45. 45)
      • 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. 8392.
    46. 46)
      • 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. 527532.
    47. 47)
      • 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. 585588.
    48. 48)
      • 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. 677681.
    49. 49)
      • 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. 8495.
    50. 50)
      • 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. 10441049.

Related content

This is a required field
Please enter a valid email address