A Topological Process Model of Trajectories-regions Based on Critical Points

doi:10.11947/j.AGCS.2015.20140261

Abstract

Abstract: The increasing pervasiveness of movement data, as a consequence of ubiquitous positioning techniques, has made researches on trajectories in the spotlight, which can facilitate and convey valuable knowledge to various kinds of studies as well as applications, such as spatio-temporal query and data mining. Despite recent research interest on trajectories switched from raw data to semantic trajectories, neither of them take into account topological invariants harbored in movements. This paper develops a topological process model of trajectories-regions based on critical points in a two-dimensional space, which distinguishes 14 basic intersection types, in point set topological theory, between trajectories and region objects by the pattern of a nested matrix, combined as sequences of intersections for describing topological correlations of trajectories-regions. The model is not only a description of topological invariants among trajectories and regions, but also the complicated topological process covering multi-trajectory and multi-region, by incorporating semantics of trajectories' behaviors. Also, constraints on trajectories' movements, brought by topological relations among regions, are discussed in the model by means of intersection linkage patterns between two adjacent intersection events.

Key words: topological process, intersection types, semantic relations, linkage of intersection

CLC Number:

P208

WU Tao, XIANG Longgang, GONG Jianya. A Topological Process Model of Trajectories-regions Based on Critical Points[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1277-1284.

References

[1] ZHENG Yu, ZHOU Xiaofang. Computing with Spatial Trajectories[M]. New York:Springer, 2011.
[2] WOLFSON O, SISTLA P, XU Bo, et al. Tracking Moving Objects Using Database Technology in DOMINO[C]//Proceedings of the 4th Workshop on Next Generation Information Technologies and Systems(NGITS).Zikhron-Yaakov, Israel:[s.n.], 1999:112-119.
[3] GVTING R H, BEHR T, ALMEIDA V, et al. SECONDO:An Extensible DBMS Architecture and Prototype[J]. Collaborative Design, 2004:439-450.
[4] CUDRÉ-MAUROUX P, WU E, MADDEN S. Trajstore:An Adaptive Storage System for Very Large Trajectory Data Sets[C]//ICDE Conference.[S.l.]:IEEE, 2010:109-120.
[5] BUCHIN K, BUCHIN M, VAN KREVELD M, et al. Trajectory Grouping Structure[C]//DEHNE F,SOLIS-OBA R, SACK J R. Proceedings of the 13th International Symposium WADS. Berlin:Springer, 2013:219-230.
[6] POPAI S, ZEITOUNI K, ORIA V, et al. Spatio-temporal Compression of Trajectories in Road Networks[J]. Geoinformatica,2015, 9(1):117-145.
[7] VIEIRA M R, BAKALOV P, TSOTRAS V J. Querying Trajectories Using Flexible Patterns[C]//Proceedings of the 13th International Conference on Extending Database Technology.New York:ACM, 2010:406-417.
[8] FRENTZOS E, GRATSIAS K, THEODORIDIS Y. Index-based Most Similar Trajectory Search[C]//Proceedings of the IEEE International Conference on Data Engineering.Istanbul:IEEE, 2007:816-825.
[9] ZHENG Kai, ZHENG Yu, YUAN N J, et al. On Discovery of Gathering Patterns from Trajectories[C]//Proceedings of the IEEE International Conference on Data Engineering.Washington, D.C.:IEEE, 2013.
[10] CAO Xin, CONG Gao, JENSEN C S. Mining Significant Semantic Locations from GPS Data[J]. Proceedings of the VLDB Endowment,2010, 3(1-2):1009-1020.
[11] HADJIELEFTHERIOU M, KOLLIOS G, GUNOPULOSD, et al. On-line Discovery of Dense Areas in Spatio-temporal Databases[C]//HADZILACOST, MANOLOPOULOS Y, RODDICK J, et al. Advances in Spatial and Temporal Databases.Berlin:Springer,2003:306-324.
[12] LEE J G, HAN Jiawei, LI Xiaolei. Trajectory Outlier Detection:A Partition and Detect Framework[C]//Proceedings of the IEEE International Conference on Data Engineering.Cancun, Mexico:IEEE, 2008:140-149.
[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]. Transportation Research Part C:Emerging Technologies, 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] YING J J C, LEE W C, WENG T C, et al. Semantic Trajectory Mining for Location Prediction[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago:ACM,2011:34-43.
[16] KLIPPELA. Spatial Information Theory Meets Spatial Thinking:Is Topology the Rosetta Stone of Spatio-temporal Cognition?[J]. Annals of the Association of American Geographers,2012, 102(6):1310-1328.
[17] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems,1991, 5(2):161-174.
[18] KURATAY. Three-valued 9-intersection for Deriving Possible Topological Relations from Incomplete Observations[M]//SESTER M, BERNARD L, PAELKE V.Advances in GIS Science.Berlin:Springer,2009:289-308.
[19] KURATAY. 9⁺-intersection Calculi for Spatial Reasoning on the Topological Relations between Heterogeneous Objects[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, CA:ACM, 2010:390-393.
[20] LI Zhilin, ZHAO Renliang, CHEN Jun. A Voronoi-based Spatial Algebra for Spatial Relations[J]. Progress in Natural Science,2002, 12(7):528-536.
[21] DENG Min, MA Hangying. The Hierarchical Representation of Topological Relations between a Line and an Area[J]. Acta Geodaetica et Cartographica Sinica,2008, 37(4):507-520.(邓敏, 马杭英. 线与面目标间拓扑关系的层次表达方法[J]. 测绘学报,2008, 37(4):507-520.)
[22] GUO Qingsheng, CHEN Yujian, LIU Hao. Combinational Reasoning of Spatial Topological Relations between a Line and an Area[J]. Geomatics and Information Science of Wuhan University,2005, 30(6):529-532.(郭庆胜, 陈宇箭, 刘浩. 线与面的空间拓扑关系组合推理[J]. 武汉大学学报:信息科学版,2005, 30(6):529-532.)
[23] ZHOU Xiaoguang, CHEN Jun, LI Zhilin, et al. Computation of Topological Relations between Cadastral Objects Based on Euler-number[J]. Acta Geodaetica et Cartographica Sinica,2006, 35(3):293-298.(周晓光, 陈军, 李志林, 等. 基于欧拉数的地籍拓扑关系计算[J]. 测绘学报,2006, 35(3):293-298.)
[24] ZHOU Xiaoguang, CHEN Jun, ZHAN FB, et al. A Euler Number-based Topological Computation Model for Land Parcel Database Updating[J]. International Journal of Geographical Information Science,2013, 27(10):1983-2005.
[25] ZHOU Xiaoguang, CHEN Fei, CHEN Jun. A Node-degree Based Line/Region Topological Relationship Refinement Model and Its Applications[J]. Acta Geodaetica et Cartographica Sinica,2015, 44(4):445-452.(周晓光, 陈斐, 陈军. 引入结点度的线面拓扑关系细分方法与应用[J]. 测绘学报,2015, 44(8):445-452.)
[26] SESTERM, FEUERHAKE U, KUNTZSCH C, et al. Revealing Underlying Structure and Behaviour form Movement Data[J]. Künstliche Intelligenz,2012, 26(3):223-231.
[27] EGENHOFER M J, MARK D M. Modeling Conceptual Neighborhoods of Topological Line-region Relations[J]. International Journal of Geographical Information Systems,1995, 9(5):555-565.