近年來移動物件追蹤技術越趨進步，促使藉由地點採集技術可從不同類型的移動物件中蒐集到巨量的軌跡時間序列資料，因此從這些巨量軌跡時間序列資料中探勘有用的資訊是ㄧ個被受矚目的議題。在論文中我們探討如何從大量軌跡時間序列資料中發現一起旅遊的移動物件群組，例如遊伴團(Traveling Group)。
現有的方法定義移動物件群組有較強的限制，例如他們必須有同步的軌跡取樣速率以利在每個時間戳(timestamp)對移動物件進行聚集演算法，而此聚集演算法通常建構於以密度為基礎的概念上，如DBScan。相反的我們的主張是在現實環境中我們取得移動物件的軌跡時間序列資料通常其取樣速率是不同步的，另一主張之一的重點是我們認為事實上一個移動物件群組不必然在每個時間戳都是高密度群聚，更貼近事實的情況是於同遊時間中群組彼此平均距離保持在一定範圍內。
由上述動機我們提出新的遊伴團概念，不再以每個時間戳移動物件的聚合為觀點，而是以移動物件整段運動軌跡為觀點。在解決發現遊伴團的問題上我們分兩階段，第一階段建構相似圖G(V ,E)，首先提出在時間域相近的兩兩移動物件軌跡如何利用Dynamic Time Warping(DTW)計算彼此距離，再以軌跡彼此的距離定義軌跡相似度函數求得移動物件間的相似度值，藉此我們可建構一無向相似圖G(V ,E)。第二階段為劃分相似圖G(V ,E)，此階段為計算相似圖G(V ,E)中每一節點所屬極大團(maximal clique)。在無向相似圖G(V ,E)中找尋極大團的問題上為了減少運算時間因此我們採用分散式系統Apache Hama為基礎架構設計一找尋極大團演算法。相似圖G(V ,E)組成極大團的點集合即為我們所要找尋之遊伴團。最後我們經由大量的實驗驗證，以實際的移動物件北京計程車的移動軌跡資料作為實驗所需資料，驗證我們提出的方法的有效性以及效率。

In recent years,remarkable advances had been made in tracking technologies of moving objects. It would be able to collected large-scale trajectories of time series data from different types of moving objects through location-acquisition technologies. Therefore, mining useful information from large-scale trajectories of time series data will be a high-profile issue. In this study, we will discuss how to discover moving object groups that travel together from large-scale trajectories of time series data, such as Traveling Group.
There are much more restriction on the definition of moving object groups by present methods. For example, each trajectory should have synchronized sampling rate in order to perform clustering algorithm on moving objects in each timestamp ,such clustering algorithm is usually based on the concept of density-based clustering, like DBScan. But we have opposite views on this matter, because the trajectory collection of time series data from moving objects in the real world is usually with unsynchronized sampling rate. On the other hand,we suggest that each moving object group does not necessarily be high-density clustering in each timestamp. For real-world objects, the average distance between each group kept within a certain range through the travel-together time interval.
According to above reason we propose a new concept of Traveling Group,which is based on the entire trajectory of moving objects rather than the cluster on each timestamp of moving objects. We separate the problem of traveling companion discovery into two step. The first step is to construct an undirected similar graph G=(V, E).Using Dynamic Time Warping(DTW) we can calculate the distance of trajectory between two moving objects in the time domain ,then measure the similarity between the trajectories of moving objects by introducing a scoring function. The second step is to demarcate G (V, E) in order to determine each node belongs to which maximal clique in G (V, E). For reducing the spend of time,we propose an algorithm based on distributed computing framework (Apache Hama) to find out maximal clique. In graph G (V, E),the maximal clique formed with points set is the traveling companions we want to find. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on a real taxicab trajectory dataset.

[1] Q. Zhang and X. Lin, “Clustering moving objects for spatio-temporal selectivity estimation,” in Proceedings of the 15th Australasian database conference-Volume 27. Australian Computer Society, Inc., 2004, pp.123–130.
[2] C. S. Jensen, D. Lin, and B. C. Ooi, “Continuous clustering of moving objects,” IEEE Transactions on Knowledge and Data Engineering,vol. 19, no. 9, pp. 1161–1174, 2007.
[3] J.-G. Lee, J. Han, and K.-Y. Whang, “Trajectory clustering: a partitionand-group framework,” in Proceedings of the 2007 ACM SIGMOD international conference on Management of data. ACM, 2007, pp.593–604.
[4] D. Yang, E. A. Rundensteiner, and M. O. Ward, “Neighbor-based pattern detection for windows over streaming data,” in Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. ACM, 2009, pp. 529–540.
[5] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise.” in Kdd, vol. 96, no. 34, 1996, pp. 226–231.
[6] J. Gudmundsson and M. van Kreveld, “Computing longest duration flocks in trajectory data,” in Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems.ACM, 2006, pp. 35–42.
[7] H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen, “Discovery of convoys in trajectory databases,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 1068–1080, 2008.
[8] Z. Li, B. Ding, J. Han, and R. Kays, “Swarm: Mining relaxed temporal moving object clusters,” Proceedings of the VLDB Endowment, vol. 3, no. 1-2, pp. 723–734, 2010.
[9] B.-K. Yi, H. Jagadish, and C. Faloutsos, “Efficient retrieval of similar time sequences under time warping,” in Proceedings of the Fourteenth International Conference on Data Engineering. IEEE, 1998, pp. 201–208.
[10] P. Laube and S. Imfeld, “Analyzing relative motion within groups oftrackable moving point objects,” in Geographic information science. Springer, 2002, pp. 132–144.
[11] G. Al-Naymat, S. Chawla, and J. Gudmundsson, “Dimensionality reduction for long duration and complex spatio-temporal queries,” in Proceedings of the 2007 ACM symposium on Applied computing. ACM, 2007, pp. 393–397.
[12] M. Benkert, J. Gudmundsson, F. Hübner, and T. Wolle, Reporting flock patterns. Springer, 2006.
[13] J. Gudmundsson and M.van Kreveld,“Computing Longest Duration Flocks in Trajectory Data,”Proc. 14th Ann. ACM Int’l Symp. Advances in Geographic Information Systems (GIS), pp.35-42,2006.
[14] M. R. Vieira, P. Bakalov, and V. J. Tsotras, “On-line discovery of flock patterns in spatio-temporal data,” in Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. ACM, 2009, pp. 286–295.
[15] Y. Huang, C. Chen, and P. Dong, “Modeling herds and their evolvements from trajectory data,” in Geographic Information Science. Springer, 2008, pp. 90–105.
[16] H. Jeung, M.L. Yiu, X. Zhou, C.S. Jensen, and H.T. Shen, “Discovery of Convoys in Trajectory Databases,” Proc. VLDB Endowment, vol. 1, no. 1, pp. 1068-1080, 2008.
[17] H. H. Aung and K.-L. Tan, “Discovery of evolving convoys,” in Scientific and Statistical Database Management. Springer, 2010, pp. 196–213.
[18] Y. Wang, E.-P. Lim, and S.-Y. Hwang, “Efficient mining of group patterns from user movement data,” Data & Knowledge Engineering, vol. 57, no. 3, pp. 240–282, 2006.
[19] Z. Li, B. Ding, J. Han, and R. Kays, “Swarm: Mining Relaxed Temporal Moving Object Clusters,” Proc. VLDB Endowment, vol. 3, no. 1, pp. 723-734, 2010.
[20] P. Kalnis, N. Mamoulis, and S. Bakiras, “On discovering moving clusters in spatio-temporal data,” in Advances in spatial and temporal databases. Springer, 2005, pp. 364–381.
[21] M. Vlachos, G. Kollios, and D. Gunopulos, “Discovering similar multidimensional trajectories,” in Proceedings of the 18th International Conference on Data Engineering. IEEE, 2002, pp. 673–684.
[22] L. Chen, M. T. Özsu, and V. Oria, “Robust and fast similarity search for
moving object trajectories,” in Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM, 2005, pp.491–502.
[23] L. Chen and R. Ng, “On the marriage of lp-norms and edit distance,” in Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment, 2004, pp. 792–803.
[24] E. Tomita, A. Tanaka, and H. Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments,” Theoretical Computer Science, vol. 363, no. 1, pp. 28–42, 2006.
[25] N. Du, B. Wu, L. Xu, B. Wang, and P. Xin, “Parallel algorithm for enumerating maximal cliques in complex network,” in Mining Complex Data. Springer, 2009, pp. 207–221.
[26] M. Sipser, Introduction to the Theory of Computation.Cengage Learning, 2012.
[27] M. R. Garey and D. S. Johnson,“Computers and intractability: a guide to the theory of np-completeness. 1979,” San Francisco, LA: Freeman,1979.
[28] R. Carraghan and P. M. Pardalos, “An exact algorithm for the maximum clique problem,” Operations Research Letters, vol. 9, no. 6, pp. 375–382, 1990.
[29] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, “Pregel: a system for large-scale graph processing,” in Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 2010, pp. 135–146.
[30] “Apache hama.” [Online]. Available: https://hama.apache.org/
[31] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang, “Tdrive: driving directions based on taxi trajectories,” in Proceedings of the 18th SIGSPATIAL International conference on advances in geographic information systems. ACM, 2010, pp. 99–108.
[32] Y. Zheng, X. Xie, and W.-Y. Ma, “Geolife: A collaborative social networking service among user, location and trajectory.” IEEE Data Eng. Bull., vol. 33, no. 2, pp. 32–39, 2010.
[33] L. Tang, Y. Zheng, J. Yuan, J. Han, A. Leung, C. Hung, and W. Peng, “On discovery of traveling companions from streaming trajectories,” in Proceedings of the 28th International Conference on Data Engineering. IEEE, 2012, pp. 186–197.
[34] X. Li, , V. Ceikute, C. Jensen, and K.-L. Tan, “Effective online group discovery in trajectory databases,” IEEE Transactions on Knowledge and Data Engineering,vol. 25, no. 12, pp. 2752–2766, 2013.
[35] K. Zheng, Y. Zheng, N. J. Yuan, and S. Shang, “On discovery of gathering
patterns from trajectories,” in Proceedings of the 29th International Conference on Data Engineering. IEEE, 2013, pp. 242–253.
[36] G. Rote, “Computing the minimum hausdorff distance between two point sets on a line under translation,” Information Processing Letters, vol. 38,no. 3, pp. 123–127, 1991.