Abstract
In this paper, we propose a new trajectory pattern mining framework, namely Clustering and Aggregating Clues of Trajectories (CACT), for discovering trajectory routes that represent the frequent movement behaviors of a user. In addition to spatial and temporal biases, we observe that trajectories contain silent durations, i.e., the time durations when no data points are available to describe the movements of users, which bring many challenging issues to trajectory pattern mining. We claim that a movement behavior would leave some clues in its various sampled/observed trajectories. These clues may be extracted from spatially and temporally co-located data points from the observed trajectories. Based on this observation, we propose clue-aware trajectory similarity to measure the clues between two trajectories. Accordingly, we further propose the clue-aware trajectory clustering algorithm to cluster similar trajectories into groups to capture the movement behaviors of the user. Finally, we devise the clue-aware trajectory aggregation algorithm to aggregate trajectories in the same group to derive the corresponding trajectory pattern and route. We validate our ideas and evaluate the proposed CACT framework by experiments using both synthetic and real datasets. The experimental results show that CACT is more effective in discovering trajectory patterns than the state-of-the-art techniques for mining trajectory patterns.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
EveryTrail—GPS Travel Community. http://www.everytrail.com/
Cao, H., Mamoulis, N., Cheung, D.W.: Mining frequent spatio-temporal sequential patterns. In: Proceedings of ICDM (2005)
Chen, L., Ng, R.T.: On the marriage of Lp-norms and edit distance. In: Proceedings of VLDB (2004)
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of SIGMOD (2005)
Chen, Y., Nascimento, M.A., Ooi, B.C., Tung, A.K.H.: SpADe: on shape-based pattern detection in streaming time series. In: Proceedings of ICDE, pp. 786–795 (2007)
Ding, H., Trajcevski, G., Scheuermann, P.: Efficient similarity join of large sets of moving object trajectories. In: Proceedings of TIME, pp. 79–87 (2008)
Ding H., Trajcevski G., Scheuermann P., Wang X., Keogh E.J.: Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. VLDB 1(2), 1542–1552 (2008)
Dodge S., Weibel R., Forootan E.: Revealing the physics of movement: comparing the similarity of movement characteristics of different types of moving objects. Comput. Environ. Urban Syst. 33(6), 419–434 (2009)
Gaffney, S., Smyth, P.: Trajectory clustering with mixtures of regression models. In: Proceedings of KDD, pp. 63–72 (1999)
Giannotti, F., Nanni, M., Pedreschi, D.: Efficient mining of temporally annotated sequences. In: Proceedings of SDM (2006)
Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory pattern mining. In: Proceedings of KDD (2007)
Gramm, J., Guo, J., Huffner, F., Niedermeier, R.: Data reduction, exact, and heuristic algorithms for clique cover. In: Proceedings of SIAM Workshop on Algorithm Engineering and Experiments (2006)
Hadjieleftheriou, M., Kollios, G., Tsotras, V.J., Gunopulos, D.: Efficient indexing of spatiotemporal objects. In: Proceedings of EDBT, pp. 251–268 (2002)
Jeung, H., Liu, Q., Shen, H.T., Zhou, X.: A hybrid prediction model for moving objects. In: Proceedings of ICDE (2008)
Jeung, H., Shen, H.T., Zhou, X.: Mining trajectory patterns using Hidden Markov models. In: Proceedings of DaWaK, pp. 470–480 (2007)
Jeung H., Yiu M.L., Zhou X., Jensen C.S., Shen H.T.: Discovery of convoys in trajectory databases. Proc. VLDB 1(1), 1068–1080 (2008)
Kalnis, P., Mamoulis, N., Bakiras, S.: On discovering moving clusters in spatio-temporal data. In: Proceedings of SSTD, pp. 364–381 (2005)
Keogh, E.J.: Exact indexing of dynamic time warping. In: Proceedings of VLDB (2002)
Lee, J.-G., Han, J., Whang, K.-Y.: Trajectory clustering: a partition-and-group framework. In: Proceedings of SIGMOD (2007)
Li Z., Ding B., Han J., Kays R.: Swarm: mining relaxed temporal moving object clusters. Proc. VLDB 3(1), 723–734 (2010)
Li, Z., Lee, J.-G., Li, X., Han, J.: Incremental clustering for trajectories. In: Proceedings of DASFAA, pp. 32–46 (2010)
Lo, C.-H., Peng, W.-C., Chen, C.-W., Lin, T.-Y., Lin, C.-S.: CarWeb: a traffic data collection platform. In: Proceedings of MDM (2008)
Mamoulis, N., Cao, H., Kollios, G., Hadjieleftheriou, M., Tao, Y., Cheung, D.W.: Mining, indexing, and querying historical spatiotemporal data. In: Proceedings of KDD (2004)
Meratnia, N., de By, R.A.: Spatiotemporal compression techniques for moving point objects. In: Proceedings of EDBT, pp. 765–782 (2004)
Nanni M., Pedreschi D.: Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. 27(3), 267–289 (2006)
Pei, J., Hua, M., Tao, Y., Lin, X.: Query answering techniques on uncertain and probabilistic data. ACM SIGMOD Tutorial (2008). doi:10.1145/1376616.1376774
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the positions of continuously moving objects. In: Proceedings of SIGMOD, pp. 331–342 (2000)
Tan P.-N., Steinbach M., Kumar V.: Introduction to Data Mining. Addison-Wesley Longman Publishing Co. Inc., Boston, MA, USA (2005)
Trajcevski, G., Ding, H., Scheuermann, P., Tamassia, R., Vaccaro, D.: Dynamics-aware similarity of moving objects trajectories. In Proceedings of GIS (2007)
Verhein, F., Chawla, S.: Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases. In: Proceedings of DASFAA (2006)
Vlachos M., Hadjieleftheriou M., Gunopulos D., Keogh E.J.: Indexing multidimensional time-series. VLDB J. 15(1), 1–20 (2006)
Wolberg, G., Alfy, I.: Monotonic cubic spline interpolation. In: Proceedings of the International Conference on Computer Graphics, pp. 188–195, Washington, DC, USA (1999)
Yi, B.-K., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: Proceedings of ICDE (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hung, CC., Peng, WC. & Lee, WC. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal 24, 169–192 (2015). https://doi.org/10.1007/s00778-011-0262-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-011-0262-6