面向地理空间信息的轨迹模型及时空模式查询

向隆刚,吴 涛,龚健雅

1.武汉大学测绘遥感信息工程国家重点实验室,湖北武汉 430079;2.中南大学地球科学与信息物理学院,湖南长沙 410083

面向地理空间信息的轨迹模型及时空模式查询

向隆刚1,吴 涛2,龚健雅1

1.武汉大学测绘遥感信息工程国家重点实验室,湖北武汉 430079;2.中南大学地球科学与信息物理学院,湖南长沙 410083

轨迹数据处理与分析是目前空间信息和数据库等相关领域的研究热点之一。本文从Stop/ Move轨迹模型出发,通过集成地理空间上下文信息来建模轨迹数据,并研究轨迹时空模式的查询处理技术。首先分析Stop/Move对象与点/线/面地理空间要素之间的时空关联关系,据此提出显式表达该关联语义的地理关联轨迹模型;在此基础上利用关系-对象数据库技术,为地理关联轨迹模型设计独立于应用的关系模式;接着定义轨迹时空模式查询,并提出基于地理关联轨迹关系模式的SQL处理框架;最后以典型性检索请求为例,讨论分析位置-时间、位置-顺序和位置-关系等3类轨迹时空模式查询的纯SQL处理技术,并以样例轨迹数据验证了本文方法的可行性。

地理空间信息;轨迹;时空关联;时空模式;SQL处理

1 引 言

轨迹是移动主体在时空中活动的真实反映,蕴含了丰富的信息与知识,针对轨迹数据的研究可以惠及社交网络[1]、位置服务[2]、交通监控[3]、出行分析[4]和生态学[5]等多个领域。轨迹数据处理与分析吸引了国内外越来越多的研究,主要围绕下述3个方向展开:①轨迹数据组织,即研制组织模型[6]、索引技术[7]和查询算法[8]来高效组织、管理和查询轨迹数据;②轨迹数据挖掘,即利用/改造已有数据挖掘技术[9],或者开发新的数据挖掘方法[10],以发现隐藏于轨迹数据中的行为与模式[11];③轨迹语义注解,即借助于人工、半自动或全自动的方法,为原始轨迹数据附加上下文语义信息,以提高轨迹数据的可读性和易用性[12-13]。在上述研究工作中,文献[14]提出的Stop/Move轨迹模型是本文研究的出发点。

Stop/Move模型从面向对象角度描述轨迹数据,是轨迹数据分析研究的热点之一[15-16]。目前,大多数工作主要围绕Stop/Move对象的组织模型与提取方法两方面而展开,在集成地理空间上下文信息并开展查询分析方面的研究还比较少。据笔者所知,文献[17]首次就这一问题进行了论述,但在关联语义表达、空间集成度和查询能力等方面均需进一步增强。

本文旨在研究轨迹数据与地理空间要素之间的时空关联语义,设计面向时空关联关系的轨迹数据组织模型,从而实现基于纯SQL语言的、针对轨迹数据的

复杂时空模式的高效查询。为此,本文依据空间拓扑关系,提出了轨迹Stop/Move对象与点/线/面地理空间要素之间的时空关联关系;在此基础之上设计了集成地理空间信息的地理关联轨迹模型及其关系模式;最后定义了轨迹时空模式查询及其基于地理关联轨迹关系模式的SQL处理框架,并以典型性请求和样例轨迹数据为例,讨论并分析了位置-时间、位置-顺序和位置-关系等3类轨迹时空模式查询的纯SQL处理技术。本文提出的轨迹数据模型及其时空模式查询方法,不仅适用于建模轨迹数据及其地理空间上下文,而且不必研制复杂的数据挖掘算法,使用业已成熟的SQL技术,即可处理关于轨迹时空模式的查询与分析。

2 地理关联轨迹模型

轨迹是移动主体在地理空间中有目的的移动。移动主体在其移动过程中,可能出于某一目的在某一地点停留一段时间(如就餐和购物等);此后继续在空间中移动,并到达下一地点停留或者抵达终点。由此,轨迹亦可看作由Stop/Move语义对象序列构成,即Stop/Move轨迹模型[14]。

轨迹总是发生于地理空间之中,地理空间即是轨迹赖以生存的土壤。当Stop/Move模型与地理空间上下文信息结合时,将增强轨迹数据的语义信息,更易于理解背后隐藏的行为与模式。文献[14,17]将这种结合视作一种应用相关的轨迹语义增强手段:前者仅在概念层次上提供两种建模方式,用户需要扩展以自定义地理关联语义,而后者限于同预定义的感兴趣域间的关联,且仅支持“停留”型地理关联语义。为此,本文面向Stop/Move轨迹模型和OGC地理空间数据模型,从基本空间拓扑关系[18-19]出发,推导出Stop/ Move对象与点/线/面3类地理空间要素之间的时空关联关系,如图1所示。

图1 Stop/Move与点/线/面之间的时空关联关系Fig.1 Spatio-temporal association relationships between Stop/Move and point/line/polygon

Stop对象与地理空间要素的关联关系较为简单,共3种情形,即停留在点上、停留在线旁和停留在面内,见图1(a)。Move对象与地理空间要素的时空关联关系则较为复杂:关联于点要素时,是一种经过语义,见图1(b);关联于线要素时,可得到进入、在里面、离开、穿越和交于等5种语义关系,见图1(c);关联于面要素时,可得到进入、在里面、离开和穿越等4种语义关系,见图1 (d)。需要指出的是,本文将面的内部与边界视为一个整体,因而在Move-Polygon的“在里面”关联语义中,Move的起止点可以在内部,也可以在边界上,该语义界定同样适用于线要素。

依据Stop/Move轨迹模型,以及Stop/Move对象与点/线/面要素之间的时空关联关系,即可得到集成地理空间上下文信息的Stop/Move轨迹模型,即地理关联轨迹模型,如图2所示。在地理关联轨迹模型中,不是以整条轨迹,而是以其语义单元—Stop/Move对象,作为轨迹数据处理与分析的基本粒度。

图2 地理关联轨迹模型Fig.2 Geo-information associated trajectory model

3 轨迹关系模式设计

在空间信息应用方面,目前使用得最为广泛仍是关系-对象型数据库,如Oralce、SQL Server等。为此,本文基于关系-对象数据库技术,设计地理关联轨迹模型的关系模式,即地理关联轨迹关系模式,作为轨迹时空模式查询与分析的基础。

轨迹由时空点构成,作为实体对象独立存在,在地理关联轨迹关系模式中表现为实体表,即trajectory(tid,point,time);Stop对象对应轨迹中的一段连续时空点,其关系模式为:stop(sid, tid,begin,end,center),其中,sid是Stop对象的唯一标识,begin和end是Stop对象的起止点时刻;同理,Move对象的关系模式为:move (mid,tid,sid1,sid2,box),其中,mid是Move对象的唯一标识,sid1和sid2表示与Move对象关联的起止Stop对象的标识。在上述Stop/ Move关系模式中,Stop和Move对象通过tid同轨迹关联,Move对象通过sid1和sid2同Stop对象关联。

在Stop/Move对象与地理空间要素的关联关系模式之中,Stop对象与点/线/面要素的关联较为简单,其关系模式为:stay(sid,oid, activity),oid可以是点、线或面要素的标识符,分别对应Stay At、Stay By和StayIn三种时空关联关系,如图1所示。Move对象与点/线/面要素的关联则复杂一些,下面将分别展开讨论。

对于Move-Point关联,关系模式为:pass (mid,oid,time),其中,time是Move对象经过点要素的时刻。对于Move-Polygon关联,存在进入、在里面、离开和穿越4种关联语义,为了降低关系模式的复杂度,本文采用同一个关系来统一表达Move-Polygon关联,即mvpg(mid,oid, time1,time2),并通过time1和time2的空值设置来表达4种不同的时空关联语义:①time1＝NULL AND time2＝NULL,对应语义“In”;②time1＝NULL AND time2NULL,对应语义“enter”;③time1≠NULL AND time2＝NULL,对应语义“Leave”;④time1≠NULL AND time2≠NULL,对应语义“Cross”。对于Move-Line关联:其进入、在里面、离开和穿越4种关联语义同理可采用一个关系来表达,即mvln(mid,oid,time1, time2),字段time1和time2含义类同于关系mvpg;而语义“交于”可采用关系:Intersect(mid, oid,point,time)来表达,其中,字段time记录相交时刻,而字段point为相交点。

根据上述讨论,不难设计出地理关联轨迹关系模式,如图3所示。在该关系模式图中,点/线/面地理空间要素的关系模式并未标出,代之以oid字段,作为时空关联关系的外键,以引用相应的地理空间要素。

4 轨迹时空模式查询的处理与分析

本节基于地理关联轨迹模型及其关系模式,首先给出轨迹时空模式查询定义及其SQL处理框架,然后通过典型性的检索请求来分析轨迹时空模式查询的纯SQL处理技术。

图3 地理关联轨迹关系模式Fig.3 Geo-information associated trajectory relational schema

4.1 时空模式查询及其处理框架

轨迹时空模式查询是指带多个时空谓词,且每一个时空谓词同时在时空两维施加限制的轨迹数据查询,本文将其分为3类:①位置-时间,在空间上与位置绑定,同时给出访问时间;②位置-顺序,在空间上与位置绑定,未给出访问时间,但指出这些位置的出现顺序;③位置-关系,在空间上与位置绑定,并给出轨迹之间相对于该位置的时间拓扑关系。依据地理关联轨迹模型及其关系模式,轨迹时空模式查询的SQL处理框架如图4所示。

图4 轨迹时空模式查询的SQL处理框架Fig.4 A SQL processing framework for trajectory spatio-temporal pattern queries

地理关联轨迹关系库的构建并不简单,但是一旦构建完毕,即可持续用于轨迹时空模式的查询与分析。在此基础上,用户即可以纯SQL语句进行轨迹时空模式查询,从而以较小代价来实现复杂轨迹时空模式的查询与分析。

在轨迹时空模式查询的SQL处理框架之中,预处理用于构建地理关联轨迹关系库,即从轨迹数据中提取出Stop/Move对象,并借助空间连接方法,将其与点/线/面地理空间要素关联。空间连接方法方面有比较成熟的算法可用[20],而Stop对象提取方面则需要依据数据的采样情况采用相应方法:检索时间间隔超过阈值的相邻时空点[21];搜索空间邻近且持续时间超过阈值的最长点序列[22];借助聚类等数据挖掘方法[23]。

4.2 SQL处理与分析

基于传统的时空点序列组织模式来回答轨迹时空模式查询,必须针对所有轨迹,首先逐一评估时空谓词的真伪,为此需要执行代价昂贵的空间连接操作,并进行时间过滤,然后分析时空谓词之间的时间拓扑关系。显然,其查询处理过程非常费力耗时,更为严重的是,每查询一次都得重复一次上述复杂的流程。此外,由于轨迹数据不可避免地存在位置误差,传统空间连接算法难以保证空间谓词评估的正确性。因此,上述处理方法不仅复杂度高,而且可靠性低。本节将分别针对3类时空模式查询,通过典型性请求来分析其SQL处理过程,说明地理关联轨迹模型及其关系模式在轨迹时空模式查询与分析方面的有效性。

4.2.1 位置-时间查询

Q1:找出T 1时刻抵达A地并停留,T 2—T 3时段内经过B地,T 4时刻进入C区域的所有轨迹。

Q1是一条典型的位置-时间型轨迹时空模式查询,每一个时空谓词均含位置和时间(时刻或时段)限定。如果依据点序列组织模式,除了执行3次在线空间连接操作外,还得测算与位置绑定的时间,其查询处理性能较低,进而将严重影响到查询响应基础之上的分析操作。基于地理关联轨迹关系库和地理空间信息库,可写出如下的纯SQL语句来响应Q1:

在上述SQL语句中:C1返回“T 1时刻抵达A地并停留”的所有Stop;C2返回“T 2—T 3时段内经过B地”的所有Move;C3返回“T 4时刻进入C区域”的所有Move;而C4保证是同一条轨迹同时满足C1、C2和C3。

4.2.2 位置-顺序查询

Q2:找出先在A地停留,随后穿越B区域的所有轨迹。

Q2并未给出访问A、B两地的具体时间,但它们在时间轴上的出现是有先后顺序的。如果依据点序列组织模式,除了执行两次在线空间连接操作外,还得测算这两次空间事件的发生时间,并比较其先后顺序。基于地理关联轨迹关系库和地理空间信息库,可写出如下的纯SQL语句来响应Q2:

在上述SQL语句中:C1返回“在A地停留”的所有Stop;C2返回“穿越B区域”的所有Move;而C3保证是同一条轨迹满足C1和C2,并且C1先于C2发生。这里之所以采用“s.sid＜＝m.sid1”来比较时间先后关系,其原因是在同一条轨迹中,Stop的标识符的编号将随时间推移而增加(这一编码特性较容易实现)。

4.2.3 位置-关系查询

Q3:当轨迹X在A地停留期间,哪些轨迹经过此地,但不停留。

不同于Q1和Q2,Q3旨在检索与某条轨迹存在指定时空关系的轨迹。如果依据点序列组织模式,首先借助空间连接操作确定轨迹X在A地停留,然后同样借助空间连接操作,搜索所有经过A的轨迹,最后通过比较时间关系来返回结果轨迹,其处理过程复杂,且代价昂贵。基于地理关联轨迹关系库和地理空间信息库,可写出如下的纯SQL语句来响应Q3:

在上述SQL语句中:C1测试时空谓词“轨迹X在A地停留”,并返回停留时间;C2返回在该时间段内经过A的所有Move;最后返回轨迹标识。

4.3 试验验证

如前文所述,地理关联轨迹库的高效构建目前仍是一项有待深入研究的技术,这也是下一步工作的重点之一。为了验证本文方法的可行性,本节采用样例轨迹数据,基于SQL Server数据库开展试验验证。样例数据的Stop/Move时空关联关系见图5所示,其中,左图表示空间关联关系,右图表示时间关联关系。依据图5,不难对其地理关联轨迹库的各关系模式进行实化,结果见图6所示,其中,sid2字段取∞时表示Move结束于终点。由于本样例轨迹未涉及与线要素的关联关系,即intersect和mvln表为空,故未在图6中将其列出。

图5 样例旅游轨迹的Stop/Move时空关联关系Fig.5 The spatio-temporal association for sample tourist Stop/Move trajectories

图6 样例旅游轨迹的地理关联轨迹Fig.6 The materialized trajectory relational schema for sample tourist trajectories

基于该地理关联轨迹库,对查询Q1—Q3进行了检验,均为符合SQL Server要求的SQL语句,并有相应的结果返回。也可发出如下查询:在轨迹1离开广场之后,有哪些轨迹访问了此地,该查询类似于Q3,即面向某一轨迹的空间关联关系,检索与之时空相关的轨迹,其SQL查询语句如下,将返回轨迹2和轨迹3。

SELECT s2.tid FROM stop s1,stop s2,stay st1, stay st2 WHERE st1.oid＝11 AND s1.tid＝1 AND s1.sid＝st1.sid AND st2.oid＝11 AND s2.sid＝st2.sid AND s2.begin＞s1.end

虽然本节试验仅用到4条样例轨迹数据,但考虑到地理关联轨迹库及其时空模式查询建立在SQL Server等成熟的关系-对象型数据库及其SQL处理引擎之上,其存储组织能力和查询检索性能在面向大规模轨迹数据与地理空间数据时也是有保障的。

5 结 论

本文着眼于轨迹数据及其地理空间上下文要素之间固有的关联关系,旨在有效查询与分析隐藏于轨迹数据中的时空行为与模式。本文提出的轨迹数据模型及其时空模式查询方法,不仅适用于建模轨迹数据及其地理空间上下文,而且不必费力研制复杂的数据挖掘算法,只需使用业已成熟的SQL技术,即可处理关于轨迹时空模式的查询与分析。

[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]∥Proceedings of 10th International Conference of Pervasive Computation.Newcastle:[s.n.],2012: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.Move Mine: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]∥Proceedings of the 26th International Conference on Data Engineering.Long Beach:ICDE, 2010:109-120.

[7] CHAKKA V P,EVERSPAUGH A C,PATEL J M.Indexing Large Trajectory Data Sets with SETI[C]∥Proceedings on Innovative Data Systems Research.Asilomar: CIDR,2003.

[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 Largescale Trajectory Data[D].Hefei:University of Science and Technology of China,2012.(袁晶.大规模轨迹数据的检索、挖掘和应用[D].合肥:中国科学技术大学,2012.)

[10] GIANNOTTI F,NANNI M,PINELLI F,et al.TrajectoryPattern Mining[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:[s.n.],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].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].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 and Knowledge Engineering,2008,65(1):126-146.

[15] ZH ANG Zhihua.Deriving Trip Information from GPS Trajectories[D].Shanghai: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]∥Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems.New York:[s.n.],2007.

[18] EGENHOFER M,FRANZOSA R.Point-set Topological Spatial Relations[J].International Journal of Geographical Information Systems,1991,5(2):161-174.

[19] EGENHOFER M,HERRING J.Categorizing Binary Topological Relationships between Regions,Lines and Points in Geographic Databases[C]∥A Framework for the Definition of Topological Relationships and an Approach to Spatial Reasoning within This Framework.Santa Barbara:[s.n.],1991:1-28.

[20] LI Liyan,QIN Xiaolin.Processing and Optimization of Join Operation in Spatial Database[J].Journal of Image and Graphics,2003,8A(7):732-737.(李立言,秦小麟.空间数据库中连接运算的处理与优化[J].中国图形图像学报, 2003,8A(7):732-737.)

[21] KRU M M J,H ORVITZ E.Predestination:Inferring Destinations from Partial Trajectories[C]∥Proceedings of 8th International Conference of Ubiquitous Computation.Los Angeles:[s.n.],2006:243-260.

[22] BUCHIN M,DRIEMEL A,KREVELD M,et al.Segmenting Trajectories:A Framework and Algorithms Using Spatiotemporal Criteria[J].Journal of Spatial Information Science,2011,3:33-63.

[23] CAO X,CONG G,JENSEN C S.Mining Significant Semantic Locations from GPS Data[J].VLDB Endowment,2010, 3(1):1009-1021.

(责任编辑:宋启凡)

A Geo-spatial Information Oriented Trajectory Model and Spatio-temporal Pattern Querying

XIANG Longgang1,WU Tao2,GONG Jianya1
1.State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University, Wuhan 430079,China;2.School of Geosciences and Info-physics,Central South University,Changsha 410083,China

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 contextual geo-spatial 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 geo-spatial 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,several typical example queries and their corresponding SQL statements are presented,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 is a relatively new solution to process and analyze trajectory dataset.It is not only capable to model trajectory and its contextual geo-spatial 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.

geo-spatial information;trajectory;spatio-temporal association;spatio-temporal pattern; SQL processing

XIANG Longgang(1976—),male,PhD, associate professor,majors in trajectory processing and analyzing.

P208

A

1001-1595(2014)09-0982-07

国家自然科学基金(41001296;60903035);国家863计划(2012AA121401;21012AA12A405)

2013-05-27

向隆刚(1976—),男,博士,副教授,主要从事轨迹数据处理与分析。

E-mail:geoxlg＠whu.edu.cn

XIANG Longgang,WU Tao,GONG Jianya.A Geo-spatial Information Oriented Trajectory Model and Spatio-temporal Pattern Querying[J].Acta Geodaetica et Cartographica Sinica,2014,43(9):982-988.(向隆刚,吴涛,龚健雅.面向地理空间信息的轨迹模型及时空模式查询[J].测绘学报,2014,43(9):982-988.)

10.13485/j.cnki.11-2089.2014.0121

修回日期:2014-05-10