定位技术的广泛应用带来了铺天盖地的移动数据,为诸如时空查询和数据挖掘等各种时空的研究及应用提供了重要素材,使得对于轨迹数据的研究成为当前的一个热点。当前,无论是对于原始轨迹数据的研究,还是对语义化轨迹数据的研究,都较少考虑轨迹移动过程中所潜藏的拓扑不变量。本文提出二维空间上基于关键点的轨迹-区域拓扑过程模型,以矩阵描述轨迹与区域的14种基本点集拓扑交叠类型,既而组织交叠序列描述轨迹和区域对象间的拓扑关联关系。模型不仅描述了轨迹与区域之间的拓扑不变量,而且结合轨迹特有行为的语义关联模型,描述轨迹相对区域的复杂拓扑过程。同时,本文还以模型中相邻两次交叠的相接交叠模式,探讨了区域间拓扑关系对于轨迹移动描述的约束。
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.
[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.
