在現今科技進步的時代裡，具備 GPS 衛星定位功能的裝置廣泛地被人們使用在生活中，這些裝置能夠即時顯示使用者所處的位置資訊，更可以記錄移動物件在一段時間下的移動軌跡，而從巨量軌跡資料庫中尋找有價值的資源、探勘軌跡間的彼此的關係，一直是許多科學家致力於研究的議題，例如在動物學中觀察野生動物的族群遷徙、大眾運輸路線規劃、計程車共乘服務設計；本研究將深入探 討如何從非同步取樣時間的軌跡資料集尋找移動物件群組 (Travelinggroup)。
在考察大量前人的研究成果後發現目前對於軌跡資料集的處理有許多的限制，例如要求全部軌跡要有同步的取樣時間或在固定區間只計算最後取樣的資料點、無法處理串流的動態資料，但是現實中所能獲取的軌跡資料集絕大多數都包含這些屬性；基於這樣的困境，本篇研究提出一個有效率的演算法用在非同步取 樣軌跡資料集中尋找移動物件群組。首先用團（Clique）來重新定義移動物件群組並將找尋此群組的問題給出一個明確的定義，接著提出一個啟發式演算法來解決 此問題；在觀察啟發式演算法對於運算上計算效率後，加入夥伴（Buddy）的概念提出夥伴式的演算法來提升運算效率。最後透過真實軌跡資料集的大量實驗來驗證所提出之方法，實驗結果顯示此演算法能夠有效率地找到移動群組，並跟對照組演算法相比有更好的效能。

In recent years, GPS-equipped devices have been widely used in our life. It would be able to record location of time series data from different types of moving objects. Therefore, mining useful information from trajectories data sets is an important issue. Such as observation on the migratory route of wild animal population, ride-sharing planning, etc. In this study, we explore to finding moving object groups that continuously traveling together from trajectories data set. However, there are many restrictions on the methods provided by the predecessors. Sampling time is required to be synchronized and not allowed to processing streaming data. Yet, these properties usually exist in the real data sets. Based on these problems, the efficient approach is proposed in this study. First exploits clique to redefine the traveling group. Then propose a heuristic algorithm Clique-Based Approach (CBA) to finding the traveling group. After observing the bottleneck of CBA, the number of CBA operations is reduced by exploiting the Buddy concept, and the Buddy-Based Approach with better efficiency is proposed. In the end, through the results of the experiment, it shows that the designed algorithm find the group efficiently in real trajectory data set and gets better performance than the comparison method.

[1] R.Song, W.Sun, B.Zheng, and Y.Zheng, “Press: Anovelframeworkoftrajectory compression in road networks, ”Proceedings of the VLDB Endowment, vol.7, no.9, pp.661–672,2014.
[2] Y.Cai and R.Ng, “Indexing spatio-temporal trajectories with chebyshev polynomials, ” in Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004,pp.599–610.
[3] M. Rowland, L. Bryant, B. Johnson, J. Noyes, M. Wisdom, and J. Thomas, “The starkey project: History, facilities, and data collection methods for ungulate research. usda forest service, ”Pacific Northwest Research Station, Portland, Oregon, 1997.
[4] S. Ma, Y. Zheng, O. Wolfson et al., “Real-time city-scale taxi ridesharing.” IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 7, pp. 1782–1795, 2015.
[5] X.Kong, Z.Xu, G.Shen, J.Wang, Q.Yang, and B.Zhang, “Urban traffic congestion estimation and prediction based on floating car trajectory data,” Future Generation Computer Systems, vol.61,pp.97–107, 2016.
[6] J. J.-C. Ying, E. H.-C. Lu, W.-C. Lee, T.-C. Weng, and V. S. Tseng, “Mining user similarity from semantic trajectories, ”in Proceedings of the 2nd ACMSIGSPATIAL International Workshop on Location Based Social Networks, 2010, pp.19–26.
[7] P.Laube and S.Imfeld, “Analyzing relative motion within groups of trackable moving point objects, ”in International Conference on Geographic InformationScience. Springer,2002,pp.132–144.
[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] 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.
[10] J.-G. Lee, J. Han, and K.-Y. Whang, “Trajectory clustering: a partition-and-group framework, ”in Proceedings of the ACM SIGMOD international conference on Management of data, 2007, pp.593–604.
[11] L.-A. Tang, Y. Zheng, J. Yuan, J. Han, A. Leung, C.-C. Hung, and W.-C. Peng, “On discovery of traveling companions from streaming trajectories,” in IEEE 28th International Conference on Data Engineering, 2012,pp.186–197.
[12] M.Priestley, “State-dependent models: a general approach to non-linear time series analysis, ”Journal of Time Series Analysis, vol.1, no.1, pp.47–71,1980.
[13] B.-K.Yi, H.Jagadish, and C.Faloutsos, “Efficient retrieval of similar time sequences under time warping, ” in Proceedings 14th International Conference on Data Engineering. IEEE, 1998, pp.201–208.
[14] M.Vlachos, G.Kollios, and D.Gunopulos, “Discovering similar multidimensional
trajectories,” in Proceedings 18th International Conference on Data Engineering. IEEE,2002,pp.673–684.
[15] L.Chen and R.Ng, “On the marriage of lp-norms and edit distance, ”in Proceedings of the Thirtieth international conference on Very large databases-Volume30. VLDB Endowment, 2004, pp.792–803.
[16] L. Chen, M. T. Özsu, and V. Oria, “Robust and fast similarity search for moving object trajectories, ”in Proceedings of ACM SIGMOD international conference on Management of data, 2005, pp.491–502.
[17] S.Salvador and P.Chan, “Toward accurate dynamic time warping in linear time and space”, Intelligent Data Analysis, vol.11, no.5, pp.561–580,2007.
[18] Y. Sakurai, M. Yoshikawa, and C. Faloutsos, “Ftw: fast similarity search under the time warping distance, ”in Proceedings of ACM SIGMOD-SIGACT-SIGART Symposium on Principles of database systems, 2005, pp.326–337.
[19] 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.
[20] K.Zheng, Y.Zheng, N.J.Yuan, S.Shang, and X.Zhou, “Online discovery of gathering patterns over trajectories,” IEEE Transactions on Knowledge and Data Engineering, vol.26, no.8, pp.1974–1988, 2014.
[21] 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, 2006, pp.35–42.
[22] H.H.Aung and K.-L.Tan, “Discovery of evolving convoys, ”in International Conference on Scientific and Statistical Database Management. Springer, 2010, pp. 196–213.
[23] M.Nanni and D.Pedreschi, “Time-focused clustering of trajectories of moving objects, ”Journal of Intelligent Information Systems, vol.27, no.3, pp.267–289,2006.
[24] G.Yuan, P.Sun, J.Zhao, D.Li, and C.Wang, “A review of moving object trajectory clustering algorithms,” Artificial Intelligence Review, vol. 47, no. 1, pp. 123–144, 2017.
[25] B.Pattabiraman, M.M.A.Patwary, A.H.Gebremedhin, W.-k.Liao, and A.Choudhary, “Fast algorithms for the maximum clique problem on massive sparse graphs, ” in International Workshop on Algorithms and Models for the Web-Graph. Springer, 2013,pp.156–169.
[26] R.M.Karp, “Reducibility among combinatorial problems, ”in Complexity of computer computations. Springer, 1972, pp.85–103.
[27] E.V.Ruiz, F.C.Nolla, and H.R.Segovia, “Is the dtw “distance” really a metric? an algorithm reducing the number of dtw comparisons in isolated word recognition, ” Speech Communication, vol.4, no.4, pp.333–344, 1985.
[28] J.Yuan, Y.Zheng, C.Zhang, W.Xie, X.Xie, G.Sun, and Y.Huang, “T-drive: driving directions based on taxi trajectories, ” in Proceedings of the 18th SIGSPATIAL International conference on advances in geographic information systems, 2010, pp. 99–108.