向隆剛,吳 濤,龔健雅

1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079;2.中南大學地球科學與信息物理學院,湖南長沙 410083

面向地理空間信息的軌跡模型及時空模式查詢

向隆剛1,吳 濤2,龔健雅1

1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079;2.中南大學地球科學與信息物理學院,湖南長沙 410083

軌跡數據處理與分析是目前空間信息和數據庫等相關領域的研究熱點之一。本文從Stop/ Move軌跡模型出發(fā),通過集成地理空間上下文信息來建模軌跡數據,并研究軌跡時空模式的查詢處理技術。首先分析Stop/Move對象與點/線/面地理空間要素之間的時空關聯關系,據此提出顯式表達該關聯語義的地理關聯軌跡模型;在此基礎上利用關系-對象數據庫技術,為地理關聯軌跡模型設計獨立于應用的關系模式;接著定義軌跡時空模式查詢,并提出基于地理關聯軌跡關系模式的SQL處理框架;最后以典型性檢索請求為例,討論分析位置-時間、位置-順序和位置-關系等3類軌跡時空模式查詢的純SQL處理技術,并以樣例軌跡數據驗證了本文方法的可行性。

地理空間信息;軌跡;時空關聯;時空模式;SQL處理

1 引 言

軌跡是移動主體在時空中活動的真實反映,蘊含了豐富的信息與知識,針對軌跡數據的研究可以惠及社交網絡[1]、位置服務[2]、交通監(jiān)控[3]、出行分析[4]和生態(tài)學[5]等多個領域。軌跡數據處理與分析吸引了國內外越來越多的研究,主要圍繞下述3個方向展開:①軌跡數據組織,即研制組織模型[6]、索引技術[7]和查詢算法[8]來高效組織、管理和查詢軌跡數據;②軌跡數據挖掘,即利用/改造已有數據挖掘技術[9],或者開發(fā)新的數據挖掘方法[10],以發(fā)現隱藏于軌跡數據中的行為與模式[11];③軌跡語義注解,即借助于人工、半自動或全自動的方法,為原始軌跡數據附加上下文語義信息,以提高軌跡數據的可讀性和易用性[12-13]。在上述研究工作中,文獻[14]提出的Stop/Move軌跡模型是本文研究的出發(fā)點。

Stop/Move模型從面向對象角度描述軌跡數據,是軌跡數據分析研究的熱點之一[15-16]。目前,大多數工作主要圍繞Stop/Move對象的組織模型與提取方法兩方面而展開,在集成地理空間上下文信息并開展查詢分析方面的研究還比較少。據筆者所知,文獻[17]首次就這一問題進行了論述,但在關聯語義表達、空間集成度和查詢能力等方面均需進一步增強。

本文旨在研究軌跡數據與地理空間要素之間的時空關聯語義,設計面向時空關聯關系的軌跡數據組織模型,從而實現基于純SQL語言的、針對軌跡數據的

復雜時空模式的高效查詢。為此,本文依據空間拓撲關系,提出了軌跡Stop/Move對象與點/線/面地理空間要素之間的時空關聯關系;在此基礎之上設計了集成地理空間信息的地理關聯軌跡模型及其關系模式;最后定義了軌跡時空模式查詢及其基于地理關聯軌跡關系模式的SQL處理框架,并以典型性請求和樣例軌跡數據為例,討論并分析了位置-時間、位置-順序和位置-關系等3類軌跡時空模式查詢的純SQL處理技術。本文提出的軌跡數據模型及其時空模式查詢方法,不僅適用于建模軌跡數據及其地理空間上下文,而且不必研制復雜的數據挖掘算法,使用業(yè)已成熟的SQL技術,即可處理關于軌跡時空模式的查詢與分析。

2 地理關聯軌跡模型

軌跡是移動主體在地理空間中有目的的移動。移動主體在其移動過程中,可能出于某一目的在某一地點停留一段時間(如就餐和購物等);此后繼續(xù)在空間中移動,并到達下一地點停留或者抵達終點。由此,軌跡亦可看作由Stop/Move語義對象序列構成,即Stop/Move軌跡模型[14]。

軌跡總是發(fā)生于地理空間之中,地理空間即是軌跡賴以生存的土壤。當Stop/Move模型與地理空間上下文信息結合時,將增強軌跡數據的語義信息,更易于理解背后隱藏的行為與模式。文獻[14,17]將這種結合視作一種應用相關的軌跡語義增強手段:前者僅在概念層次上提供兩種建模方式,用戶需要擴展以自定義地理關聯語義,而后者限于同預定義的感興趣域間的關聯,且僅支持“停留”型地理關聯語義。為此,本文面向Stop/Move軌跡模型和OGC地理空間數據模型,從基本空間拓撲關系[18-19]出發(fā),推導出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對象對應軌跡中的一段連續(xù)時空點,其關系模式為: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 軌跡時空模式查詢的處理與分析

本節(jié)基于地理關聯軌跡模型及其關系模式,首先給出軌跡時空模式查詢定義及其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

地理關聯軌跡關系庫的構建并不簡單,但是一旦構建完畢,即可持續(xù)用于軌跡時空模式的查詢與分析。在此基礎上,用戶即可以純SQL語句進行軌跡時空模式查詢,從而以較小代價來實現復雜軌跡時空模式的查詢與分析。

在軌跡時空模式查詢的SQL處理框架之中,預處理用于構建地理關聯軌跡關系庫,即從軌跡數據中提取出Stop/Move對象,并借助空間連接方法,將其與點/線/面地理空間要素關聯。空間連接方法方面有比較成熟的算法可用[20],而Stop對象提取方面則需要依據數據的采樣情況采用相應方法:檢索時間間隔超過閾值的相鄰時空點[21];搜索空間鄰近且持續(xù)時間超過閾值的最長點序列[22];借助聚類等數據挖掘方法[23]。

4.2 SQL處理與分析

基于傳統的時空點序列組織模式來回答軌跡時空模式查詢,必須針對所有軌跡,首先逐一評估時空謂詞的真?zhèn)?為此需要執(zhí)行代價昂貴的空間連接操作,并進行時間過濾,然后分析時空謂詞之間的時間拓撲關系。顯然,其查詢處理過程非常費力耗時,更為嚴重的是,每查詢一次都得重復一次上述復雜的流程。此外,由于軌跡數據不可避免地存在位置誤差,傳統空間連接算法難以保證空間謂詞評估的正確性。因此,上述處理方法不僅復雜度高,而且可靠性低。本節(jié)將分別針對3類時空模式查詢,通過典型性請求來分析其SQL處理過程,說明地理關聯軌跡模型及其關系模式在軌跡時空模式查詢與分析方面的有效性。

4.2.1 位置-時間查詢

Q1:找出T 1時刻抵達A地并停留,T 2—T 3時段內經過B地,T 4時刻進入C區(qū)域的所有軌跡。

Q1是一條典型的位置-時間型軌跡時空模式查詢,每一個時空謂詞均含位置和時間(時刻或時段)限定。如果依據點序列組織模式,除了執(zhí)行3次在線空間連接操作外,還得測算與位置綁定的時間,其查詢處理性能較低,進而將嚴重影響到查詢響應基礎之上的分析操作?；诘乩黻P聯軌跡關系庫和地理空間信息庫,可寫出如下的純SQL語句來響應Q1:

在上述SQL語句中:C1返回“T 1時刻抵達A地并停留”的所有Stop;C2返回“T 2—T 3時段內經過B地”的所有Move;C3返回“T 4時刻進入C區(qū)域”的所有Move;而C4保證是同一條軌跡同時滿足C1、C2和C3。

4.2.2 位置-順序查詢

Q2:找出先在A地停留,隨后穿越B區(qū)域的所有軌跡。

Q2并未給出訪問A、B兩地的具體時間,但它們在時間軸上的出現是有先后順序的。如果依據點序列組織模式,除了執(zhí)行兩次在線空間連接操作外,還得測算這兩次空間事件的發(fā)生時間,并比較其先后順序?；诘乩黻P聯軌跡關系庫和地理空間信息庫,可寫出如下的純SQL語句來響應Q2:

在上述SQL語句中:C1返回“在A地停留”的所有Stop;C2返回“穿越B區(qū)域”的所有Move;而C3保證是同一條軌跡滿足C1和C2,并且C1先于C2發(fā)生。這里之所以采用“s.sid＜＝m.sid1”來比較時間先后關系,其原因是在同一條軌跡中,Stop的標識符的編號將隨時間推移而增加(這一編碼特性較容易實現)。

4.2.3 位置-關系查詢

Q3:當軌跡X在A地停留期間,哪些軌跡經過此地,但不停留。

不同于Q1和Q2,Q3旨在檢索與某條軌跡存在指定時空關系的軌跡。如果依據點序列組織模式,首先借助空間連接操作確定軌跡X在A地停留,然后同樣借助空間連接操作,搜索所有經過A的軌跡,最后通過比較時間關系來返回結果軌跡,其處理過程復雜,且代價昂貴?；诘乩黻P聯軌跡關系庫和地理空間信息庫,可寫出如下的純SQL語句來響應Q3:

在上述SQL語句中:C1測試時空謂詞“軌跡X在A地停留”,并返回停留時間;C2返回在該時間段內經過A的所有Move;最后返回軌跡標識。

4.3 試驗驗證

如前文所述,地理關聯軌跡庫的高效構建目前仍是一項有待深入研究的技術,這也是下一步工作的重點之一。為了驗證本文方法的可行性,本節(jié)采用樣例軌跡數據,基于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語句,并有相應的結果返回。也可發(fā)出如下查詢:在軌跡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

雖然本節(jié)試驗僅用到4條樣例軌跡數據,但考慮到地理關聯軌跡庫及其時空模式查詢建立在SQL Server等成熟的關系-對象型數據庫及其SQL處理引擎之上,其存儲組織能力和查詢檢索性能在面向大規(guī)模軌跡數據與地理空間數據時也是有保障的。

5 結 論

本文著眼于軌跡數據及其地理空間上下文要素之間固有的關聯關系,旨在有效查詢與分析隱藏于軌跡數據中的時空行為與模式。本文提出的軌跡數據模型及其時空模式查詢方法,不僅適用于建模軌跡數據及其地理空間上下文,而且不必費力研制復雜的數據挖掘算法,只需使用業(yè)已成熟的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.(袁晶.大規(guī)模軌跡數據的檢索、挖掘和應用[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.(李立言,秦小麟.空間數據庫中連接運算的處理與優(yōu)化[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