Abstract
Mobile objects have become ubiquitous in our everyday lives, ranging from cellular phones to sensors, therefore, analyzing and mining mobile data becomes an interesting problem with great practical importance. For instance, by finding trajectory patterns of the mobile clients, the mobile communication network can allocate resources more efficiently. However, due to the limited power of the mobile devices, we are only able to obtain the imprecise location of a mobile object at a given time. Sequential patterns are a popular data mining model. By applying the sequential pattern model on the set of imprecise trajectories of the mobile objects, we may uncover important information or further our understanding of the inherent characteristics of the mobile objects, e.g., constructing a classifier based on the discovered patterns or using the patterns to improve the accuracy of location prediction. Since the input data is highly imprecise, it may not be possible to directly apply any existing sequential pattern discovery algorithm to the problem in this paper. Thus, we propose the model of the trajectory patterns and a novel measure to represent the expected occurrences of a pattern in a set of imprecise trajectories. The concept of pattern groups is introduced to present the trajectory patterns in a concise manner. Since the Apriori property no longer holds on the trajectory patterns, a new min-max property is identified and a novel TrajPattern algorithm is devised based on the newly discovered property. Last but not least, we apply the TrajPattern algorithm on a wide range of real and synthetic data sets to demonstrate the usefulness, efficiency, and scalability of this approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Han, J., Dong, G., Yin, Y.: Efficient mining partial periodic patterns in time series database. In: Proc. of ICDE (1999)
Jain, A., Chang, E., Wang, Y.: Adaptive stream resource management using Kalman filters. In: Proc. of SIGMOD (2004)
Li, Y., Han, J., Yang, J.: Clustering mobile objects. In: Proc. of KDD (2004)
Mamoulis, N., Cao, H., Kollios, G., Hadjieleftheriou, M., Tao, Y., Cheung, D.: Mining, indexing, and querying historical spatiotemporal data. In: Proc. of KDD (2004)
Peng, W.-C., Chen, M.-S.: Developing data allocation schemes by incremental mining of user moving patterns in a mobile computing system. In: IEEE TKDE (2003)
Song, Z., Roussopoulos, N.: K-Nearest neighbor search for moving query point. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol. 2121, p. 79. Springer, Heidelberg (2001)
Patel, J., Chen, Y., Chakka, V.: STRIPES: an efficient index for predicted trajectories. In: Proc. of SIGMOD (2004)
Pei, J., Han, J., Pinto, H., Chen, Q., Dayal, U., Hsu, M.: PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth. In: Proc. of ICDE (2001)
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the positions of continuously moving objects. In: Proc. of SIGMOD (2000)
Tao, Y., Sun, J., Papadias, D.: Selectivity estimation for predictive spatio-temporal queries. In: Proc. of ICDE, Bangalore, India, March, pp. 417–428 (2003)
Tao, Y., Faloutsos, C., Papadias, D.: Prediction and indexing of moving objects with unknown motion patterns. In: Proc. of SIGMOD (2004)
Wolfson, O., Sistla, P., Chamberlain, S., Yesha, Y.: Updating and query databases that track mobile unites. Distributed and Parallel Databases 7(3) (1999)
Yang, J., Wang, W., Yu, P.: mining surprising periodic patterns. In: Proc. of (KDD), pp. 395–400 (2001)
Yang, J., Wang, W., Yu, P., Han, J.: Mining long sequential patterns in a noisy environment. In: Proc. of SIGMOD (2002)
Zaki, M.: SPADE: an efficient algorithm for mining frequent sequences. Machine Learning 42(1/2), 31–60 (2001)
Wang, Y., Martonosi, M., Peh, L.S., Zhang, P., Sadler, C., Liu, T., Rubenstein, D., Lyon, S.A.: ZebraNet mobility data. Princeton University Press, Princeton (2004)
Yang, J., Hu, M.: TrajPattern: Mining sequential patterns from imprecise trajectories of mobile objects. Technical Report, EECS, Case Western Reserve University (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yang, J., Hu, M. (2006). TrajPattern: Mining Sequential Patterns from Imprecise Trajectories of Mobile Objects. In: Ioannidis, Y., et al. Advances in Database Technology - EDBT 2006. EDBT 2006. Lecture Notes in Computer Science, vol 3896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11687238_40
Download citation
DOI: https://doi.org/10.1007/11687238_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32960-2
Online ISBN: 978-3-540-32961-9
eBook Packages: Computer ScienceComputer Science (R0)