向隆剛,吳 濤,龔健雅

1.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079;2.中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南長(zhǎng)沙 410083

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

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

1.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079;2.中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南長(zhǎng)沙 410083

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

地理空間信息;軌跡;時(shí)空關(guān)聯(lián);時(shí)空模式;SQL處理

1 引 言

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

Stop/Move模型從面向?qū)ο蠼嵌让枋鲕壽E數(shù)據(jù),是軌跡數(shù)據(jù)分析研究的熱點(diǎn)之一[15-16]。目前,大多數(shù)工作主要圍繞Stop/Move對(duì)象的組織模型與提取方法兩方面而展開,在集成地理空間上下文信息并開展查詢分析方面的研究還比較少。據(jù)筆者所知,文獻(xiàn)[17]首次就這一問(wèn)題進(jìn)行了論述,但在關(guān)聯(lián)語(yǔ)義表達(dá)、空間集成度和查詢能力等方面均需進(jìn)一步增強(qiáng)。

本文旨在研究軌跡數(shù)據(jù)與地理空間要素之間的時(shí)空關(guān)聯(lián)語(yǔ)義,設(shè)計(jì)面向時(shí)空關(guān)聯(lián)關(guān)系的軌跡數(shù)據(jù)組織模型,從而實(shí)現(xiàn)基于純SQL語(yǔ)言的、針對(duì)軌跡數(shù)據(jù)的

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

2 地理關(guān)聯(lián)軌跡模型

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

軌跡總是發(fā)生于地理空間之中,地理空間即是軌跡賴以生存的土壤。當(dāng)Stop/Move模型與地理空間上下文信息結(jié)合時(shí),將增強(qiáng)軌跡數(shù)據(jù)的語(yǔ)義信息,更易于理解背后隱藏的行為與模式。文獻(xiàn)[14,17]將這種結(jié)合視作一種應(yīng)用相關(guān)的軌跡語(yǔ)義增強(qiáng)手段:前者僅在概念層次上提供兩種建模方式,用戶需要擴(kuò)展以自定義地理關(guān)聯(lián)語(yǔ)義,而后者限于同預(yù)定義的感興趣域間的關(guān)聯(lián),且僅支持“停留”型地理關(guān)聯(lián)語(yǔ)義。為此,本文面向Stop/Move軌跡模型和OGC地理空間數(shù)據(jù)模型,從基本空間拓?fù)潢P(guān)系[18-19]出發(fā),推導(dǎo)出Stop/ Move對(duì)象與點(diǎn)/線/面3類地理空間要素之間的時(shí)空關(guān)聯(lián)關(guān)系,如圖1所示。

圖1 Stop/Move與點(diǎn)/線/面之間的時(shí)空關(guān)聯(lián)關(guān)系Fig.1 Spatio-temporal association relationships between Stop/Move and point/line/polygon

Stop對(duì)象與地理空間要素的關(guān)聯(lián)關(guān)系較為簡(jiǎn)單,共3種情形,即停留在點(diǎn)上、停留在線旁和停留在面內(nèi),見圖1(a)。Move對(duì)象與地理空間要素的時(shí)空關(guān)聯(lián)關(guān)系則較為復(fù)雜:關(guān)聯(lián)于點(diǎn)要素時(shí),是一種經(jīng)過(guò)語(yǔ)義,見圖1(b);關(guān)聯(lián)于線要素時(shí),可得到進(jìn)入、在里面、離開、穿越和交于等5種語(yǔ)義關(guān)系,見圖1(c);關(guān)聯(lián)于面要素時(shí),可得到進(jìn)入、在里面、離開和穿越等4種語(yǔ)義關(guān)系,見圖1 (d)。需要指出的是,本文將面的內(nèi)部與邊界視為一個(gè)整體,因而在Move-Polygon的“在里面”關(guān)聯(lián)語(yǔ)義中,Move的起止點(diǎn)可以在內(nèi)部,也可以在邊界上,該語(yǔ)義界定同樣適用于線要素。

依據(jù)Stop/Move軌跡模型,以及Stop/Move對(duì)象與點(diǎn)/線/面要素之間的時(shí)空關(guān)聯(lián)關(guān)系,即可得到集成地理空間上下文信息的Stop/Move軌跡模型,即地理關(guān)聯(lián)軌跡模型,如圖2所示。在地理關(guān)聯(lián)軌跡模型中,不是以整條軌跡,而是以其語(yǔ)義單元—Stop/Move對(duì)象,作為軌跡數(shù)據(jù)處理與分析的基本粒度。

圖2 地理關(guān)聯(lián)軌跡模型Fig.2 Geo-information associated trajectory model

3 軌跡關(guān)系模式設(shè)計(jì)

在空間信息應(yīng)用方面,目前使用得最為廣泛仍是關(guān)系-對(duì)象型數(shù)據(jù)庫(kù),如Oralce、SQL Server等。為此,本文基于關(guān)系-對(duì)象數(shù)據(jù)庫(kù)技術(shù),設(shè)計(jì)地理關(guān)聯(lián)軌跡模型的關(guān)系模式,即地理關(guān)聯(lián)軌跡關(guān)系模式,作為軌跡時(shí)空模式查詢與分析的基礎(chǔ)。

軌跡由時(shí)空點(diǎn)構(gòu)成,作為實(shí)體對(duì)象獨(dú)立存在,在地理關(guān)聯(lián)軌跡關(guān)系模式中表現(xiàn)為實(shí)體表,即trajectory(tid,point,time);Stop對(duì)象對(duì)應(yīng)軌跡中的一段連續(xù)時(shí)空點(diǎn),其關(guān)系模式為:stop(sid, tid,begin,end,center),其中,sid是Stop對(duì)象的唯一標(biāo)識(shí),begin和end是Stop對(duì)象的起止點(diǎn)時(shí)刻;同理,Move對(duì)象的關(guān)系模式為:move (mid,tid,sid1,sid2,box),其中,mid是Move對(duì)象的唯一標(biāo)識(shí),sid1和sid2表示與Move對(duì)象關(guān)聯(lián)的起止Stop對(duì)象的標(biāo)識(shí)。在上述Stop/ Move關(guān)系模式中,Stop和Move對(duì)象通過(guò)tid同軌跡關(guān)聯(lián),Move對(duì)象通過(guò)sid1和sid2同Stop對(duì)象關(guān)聯(lián)。

在Stop/Move對(duì)象與地理空間要素的關(guān)聯(lián)關(guān)系模式之中,Stop對(duì)象與點(diǎn)/線/面要素的關(guān)聯(lián)較為簡(jiǎn)單,其關(guān)系模式為:stay(sid,oid, activity),oid可以是點(diǎn)、線或面要素的標(biāo)識(shí)符,分別對(duì)應(yīng)Stay At、Stay By和StayIn三種時(shí)空關(guān)聯(lián)關(guān)系,如圖1所示。Move對(duì)象與點(diǎn)/線/面要素的關(guān)聯(lián)則復(fù)雜一些,下面將分別展開討論。

對(duì)于Move-Point關(guān)聯(lián),關(guān)系模式為:pass (mid,oid,time),其中,time是Move對(duì)象經(jīng)過(guò)點(diǎn)要素的時(shí)刻。對(duì)于Move-Polygon關(guān)聯(lián),存在進(jìn)入、在里面、離開和穿越4種關(guān)聯(lián)語(yǔ)義,為了降低關(guān)系模式的復(fù)雜度,本文采用同一個(gè)關(guān)系來(lái)統(tǒng)一表達(dá)Move-Polygon關(guān)聯(lián),即mvpg(mid,oid, time1,time2),并通過(guò)time1和time2的空值設(shè)置來(lái)表達(dá)4種不同的時(shí)空關(guān)聯(lián)語(yǔ)義:①time1＝NULL AND time2＝NULL,對(duì)應(yīng)語(yǔ)義“In”;②time1＝NULL AND time2NULL,對(duì)應(yīng)語(yǔ)義“enter”;③time1≠NULL AND time2＝NULL,對(duì)應(yīng)語(yǔ)義“Leave”;④time1≠NULL AND time2≠NULL,對(duì)應(yīng)語(yǔ)義“Cross”。對(duì)于Move-Line關(guān)聯(lián):其進(jìn)入、在里面、離開和穿越4種關(guān)聯(lián)語(yǔ)義同理可采用一個(gè)關(guān)系來(lái)表達(dá),即mvln(mid,oid,time1, time2),字段time1和time2含義類同于關(guān)系mvpg;而語(yǔ)義“交于”可采用關(guān)系:Intersect(mid, oid,point,time)來(lái)表達(dá),其中,字段time記錄相交時(shí)刻,而字段point為相交點(diǎn)。

根據(jù)上述討論,不難設(shè)計(jì)出地理關(guān)聯(lián)軌跡關(guān)系模式,如圖3所示。在該關(guān)系模式圖中,點(diǎn)/線/面地理空間要素的關(guān)系模式并未標(biāo)出,代之以oid字段,作為時(shí)空關(guān)聯(lián)關(guān)系的外鍵,以引用相應(yīng)的地理空間要素。

4 軌跡時(shí)空模式查詢的處理與分析

本節(jié)基于地理關(guān)聯(lián)軌跡模型及其關(guān)系模式,首先給出軌跡時(shí)空模式查詢定義及其SQL處理框架,然后通過(guò)典型性的檢索請(qǐng)求來(lái)分析軌跡時(shí)空模式查詢的純SQL處理技術(shù)。

圖3 地理關(guān)聯(lián)軌跡關(guān)系模式Fig.3 Geo-information associated trajectory relational schema

4.1 時(shí)空模式查詢及其處理框架

軌跡時(shí)空模式查詢是指帶多個(gè)時(shí)空謂詞,且每一個(gè)時(shí)空謂詞同時(shí)在時(shí)空兩維施加限制的軌跡數(shù)據(jù)查詢,本文將其分為3類:①位置-時(shí)間,在空間上與位置綁定,同時(shí)給出訪問(wèn)時(shí)間;②位置-順序,在空間上與位置綁定,未給出訪問(wèn)時(shí)間,但指出這些位置的出現(xiàn)順序;③位置-關(guān)系,在空間上與位置綁定,并給出軌跡之間相對(duì)于該位置的時(shí)間拓?fù)潢P(guān)系。依據(jù)地理關(guān)聯(lián)軌跡模型及其關(guān)系模式,軌跡時(shí)空模式查詢的SQL處理框架如圖4所示。

圖4 軌跡時(shí)空模式查詢的SQL處理框架Fig.4 A SQL processing framework for trajectory spatio-temporal pattern queries

地理關(guān)聯(lián)軌跡關(guān)系庫(kù)的構(gòu)建并不簡(jiǎn)單,但是一旦構(gòu)建完畢,即可持續(xù)用于軌跡時(shí)空模式的查詢與分析。在此基礎(chǔ)上,用戶即可以純SQL語(yǔ)句進(jìn)行軌跡時(shí)空模式查詢,從而以較小代價(jià)來(lái)實(shí)現(xiàn)復(fù)雜軌跡時(shí)空模式的查詢與分析。

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

4.2 SQL處理與分析

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

4.2.1 位置-時(shí)間查詢

Q1:找出T 1時(shí)刻抵達(dá)A地并停留,T 2—T 3時(shí)段內(nèi)經(jīng)過(guò)B地,T 4時(shí)刻進(jìn)入C區(qū)域的所有軌跡。

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

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

4.2.2 位置-順序查詢

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

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

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

4.2.3 位置-關(guān)系查詢

Q3:當(dāng)軌跡X在A地停留期間,哪些軌跡經(jīng)過(guò)此地,但不停留。

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

在上述SQL語(yǔ)句中:C1測(cè)試時(shí)空謂詞“軌跡X在A地停留”,并返回停留時(shí)間;C2返回在該時(shí)間段內(nèi)經(jīng)過(guò)A的所有Move;最后返回軌跡標(biāo)識(shí)。

4.3 試驗(yàn)驗(yàn)證

如前文所述,地理關(guān)聯(lián)軌跡庫(kù)的高效構(gòu)建目前仍是一項(xiàng)有待深入研究的技術(shù),這也是下一步工作的重點(diǎn)之一。為了驗(yàn)證本文方法的可行性,本節(jié)采用樣例軌跡數(shù)據(jù),基于SQL Server數(shù)據(jù)庫(kù)開展試驗(yàn)驗(yàn)證。樣例數(shù)據(jù)的Stop/Move時(shí)空關(guān)聯(lián)關(guān)系見圖5所示,其中,左圖表示空間關(guān)聯(lián)關(guān)系,右圖表示時(shí)間關(guān)聯(lián)關(guān)系。依據(jù)圖5,不難對(duì)其地理關(guān)聯(lián)軌跡庫(kù)的各關(guān)系模式進(jìn)行實(shí)化,結(jié)果見圖6所示,其中,sid2字段取∞時(shí)表示Move結(jié)束于終點(diǎn)。由于本樣例軌跡未涉及與線要素的關(guān)聯(lián)關(guān)系,即intersect和mvln表為空,故未在圖6中將其列出。

圖5 樣例旅游軌跡的Stop/Move時(shí)空關(guān)聯(lián)關(guān)系Fig.5 The spatio-temporal association for sample tourist Stop/Move trajectories

圖6 樣例旅游軌跡的地理關(guān)聯(lián)軌跡Fig.6 The materialized trajectory relational schema for sample tourist trajectories

基于該地理關(guān)聯(lián)軌跡庫(kù),對(duì)查詢Q1—Q3進(jìn)行了檢驗(yàn),均為符合SQL Server要求的SQL語(yǔ)句,并有相應(yīng)的結(jié)果返回。也可發(fā)出如下查詢:在軌跡1離開廣場(chǎng)之后,有哪些軌跡訪問(wèn)了此地,該查詢類似于Q3,即面向某一軌跡的空間關(guān)聯(lián)關(guān)系,檢索與之時(shí)空相關(guān)的軌跡,其SQL查詢語(yǔ)句如下,將返回軌跡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é)試驗(yàn)僅用到4條樣例軌跡數(shù)據(jù),但考慮到地理關(guān)聯(lián)軌跡庫(kù)及其時(shí)空模式查詢建立在SQL Server等成熟的關(guān)系-對(duì)象型數(shù)據(jù)庫(kù)及其SQL處理引擎之上,其存儲(chǔ)組織能力和查詢檢索性能在面向大規(guī)模軌跡數(shù)據(jù)與地理空間數(shù)據(jù)時(shí)也是有保障的。

5 結(jié) 論

本文著眼于軌跡數(shù)據(jù)及其地理空間上下文要素之間固有的關(guān)聯(lián)關(guān)系,旨在有效查詢與分析隱藏于軌跡數(shù)據(jù)中的時(shí)空行為與模式。本文提出的軌跡數(shù)據(jù)模型及其時(shí)空模式查詢方法,不僅適用于建模軌跡數(shù)據(jù)及其地理空間上下文,而且不必費(fèi)力研制復(fù)雜的數(shù)據(jù)挖掘算法,只需使用業(yè)已成熟的SQL技術(shù),即可處理關(guān)于軌跡時(shí)空模式的查詢與分析。

[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ī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),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].上海:華東師范大學(xué),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.(李立言,秦小麟.空間數(shù)據(jù)庫(kù)中連接運(yùn)算的處理與優(yōu)化[J].中國(guó)圖形圖像學(xué)報(bào), 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.

(責(zé)任編輯:宋啟凡)

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

國(guó)家自然科學(xué)基金(41001296;60903035);國(guó)家863計(jì)劃(2012AA121401;21012AA12A405)

2013-05-27

向隆剛(1976—),男,博士,副教授,主要從事軌跡數(shù)據(jù)處理與分析。

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.(向隆剛,吳濤,龔健雅.面向地理空間信息的軌跡模型及時(shí)空模式查詢[J].測(cè)繪學(xué)報(bào),2014,43(9):982-988.)

10.13485/j.cnki.11-2089.2014.0121

修回日期:2014-05-10