A geographical information oriented trajectory model and spatio-temporal pattern querying

doi:10.13485/j.cnki.11-2089.2014.0121

Abstract

Abstract:

Trajectory processing and analyzing is now one of the hottest research issues in related fields, such as geography, database, and so on. Inspired from the Stop/Move abstract model of trajectory, this paper aims at modeling trajectory by integrating context geographical information and studying the processing techniques on trajectory spatio-temporal pattern queries. First, the semantic relationships between Stop/Move objects and point/line/polygon features are analyzed, based on which a novel trajectory model that explicitly expresses geographical information associated semantics is proposed; Next, an application-independent trajectory relational schema for this trajectory model is designed; Next, the concept of trajectory spatio-temporal pattern query is introduced, and its SQL processing framework, based on trajectory relational schema, is also proposed. Finally, this paper discusses how to processing trajectory spatio-temporal pattern queries with pure SQL languages. To make the answering procedure more clearly, this paper not only presents several typical example queries and their corresponding SQL statements, covering all three types of trajectory spatio-temporal pattern queries, i.e., location-time, location-order and location-relation, but also analyze in detail the hidden SQL processing steps. The trajectory model and its sptaio-temporal pattern querying, proposed in this paper, is a relatively new solution to process and analyze trajectory dataset. It is not only capable to model trajectory and its context geographical information, but also a cost-efficient way to process trajectory spatio-temporal pattern queries, which is carried out just based on mature SQL technology without the necessary to develop complicated data mining methods.

Key words: Trajectory, Stop-Move, Spatio-temporal association, Spatio-temporal pattern, SQL processing

XIANG Longgang WU Tao GONG Jianya. A geographical information oriented trajectory model and spatio-temporal pattern querying[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9): 982-988.

References

[1] Zheng V W, Zheng Y, Xie X, et al. Towards mobile intelligence:　Learning from GPS history for collaborative recommendation [J]. Artificial Intelligence, 2012, 184(1): 17-37.
[2] Yuan J, Zheng Y, Xie X, et al. T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence [J]. Data & Knowledge Engineering, 2013, 25(1): 220-232.
[3] Castro P S, Zhang D, Li S. Urban Traffic Modeling and Prediction Using Large Scale Taxi GPS Traces [C]. In 10th International Conference of Pervasive Computation, Newcastle, 2012, UK, 57-72.
[4] Kaltenbrunner A, Meza R, Grivolla J, et al. Urban cycles and mobility patterns: Exploring and predicting trends in a bicycle-based public transport system [J]. Pervasive and Mobile Computing, 2010, 6(4): 455-466.
[5] Li Z, Han J, Ji M, et al. MoveMine: Mining moving object data for discovery of animal movement patterns [J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(4): 111-146.
[6] Cudré-Mauroux P, Wu E, Madden S. Trajstore: An adaptive storage system for very large trajectory data sets [C]. In Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, Long Beach, California, USA, 2010, 109-120.
[7] Chakka V P, Everspaugh A C, Patel J M. Indexing large trajectory data sets with SETI [C]. In Proceedings on Innovative Data Systems Research, CIDR 2003, Asilomar, CA, USA.
[8] Sakr M A, Guting R H. Spationtemporal pattern Queries [J]. Geoinformatics, 2011, 15(3): 497-540.
[9] Yuan jing. Querying, mining with applications on large-scale trajectory data [D]. Ph.D Dissertation, University of Science and Technology of China, 2012.（袁晶，大规模轨迹数据的检索、挖掘和应用 [D]. 合肥：博士论文，2012，中国科学技术大学.）
[10] Giannotti F, Nanni M, Pinelli F, et al. Trajectory pattern mining [C]. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD 2007, New York, NY, USA, 2007, 330–339.
[11] Dodge S, Weibei R, Lautenschutz A K. Towards a Taxonomy of Movement Patterns [J]. Information Visualization, 2008, 7: 240-252.
[12] Yan Z, Chakraborty D, Parent C, et al. Semantic Trajectories: Mobility Data Computation and Annotation [J]. In ACM Transactions on Intelligent Systems and Technology, 2012, 9(4): 1-34.
[13] Quddus M A, Ochieng W Y, Noland R B. Current map-matching algorithms for transport applications: State-of-the-art and future research directions [J]. In Transportation Research Part C, 2007, 15(5): 312-328.
[14] Spaccapietra S, Parent C, Damiani M L, et al. A conceptual view on trajectories [J]. Data & Knowledge Engineering, 2008, 65(1): 126-146.
[15] Zhang Zhihua. Deriving trip information from GPS trajectories [D]. Ph.D Dissertation, East China Normal University, 2010. （张治华. 基于GPS轨迹的出行信息提取研究[D]，博士论文，华东师范大学，2010.）
[16] Andrienko G, Adnrrienko N, Heurich M. An event-based conceptual model for context-aware movement [J]. International Journal of Geographical Information Science, 2011, 25(9): 1347-1370.
[17] Alvares L O, Bogorny V, Kuijpers B, et al. A model for enriching trajectories with semantic geographical information [C]. In Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, GIS 2007, New York, NY, USA.
[18] EgenhoferM, Franzosa R. Point-set topological spatial relations [J]. International Journal of Geographical Information Systems, 1991, 5 (2): 161-174.
[19] EgenhoferM, Herring J. Categorizing binary topological relationships between regions, lines and points in geographic databases [C]. In: A Framework for the Definition of Topological Relationships and An Approach to Spatial Reasoning within this Framework, Santa Barbara, CA, 1991: 1-28.
[20] Li liyan, Qin Xiaolin. Processing and optimization of join operation in spatial database [J]. Journal of Image and Graphics, 8A(7): 732-737, 2003.（李立言, 秦小麟. 空间数据库中连接运算的处理与优化[J]. 中国图形图像学报, 8A(7): 732-737, 2003.）
[21] Krumm J, Horvitz E. Predestination: Inferring Destinations from Partial Trajectories [C]. In 8th International Conference of Ubiquitous Computation, CA, USA, 2006, 243-260.
[22] Buchin M, Driemel A, Kreveld M, et al. Segmenting trajectories: A framework and algorithms using spatio-temporal criteria [J]. Journal of Spatial Information Science, 2011, 3(2011): 33-63.
[23] Cao X, Cong G, Jensen C S. Mining significant semantic locations from GPS data [C]. In Proceedings of the VLDB Endowment, 2010, 3(1): 1009-1021.