軌跡大數(shù)據(jù)：數(shù)據(jù)、應用與技術(shù)現(xiàn)狀

許佳捷，鄭凱，池明旻，朱揚勇，禹曉輝，周曉方

(1.蘇州大學 計算機科學與技術(shù)學院，江蘇 蘇州 215006；2.江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇 南京 211102；3.復旦大學 計算機科學技術(shù)學院 上海市數(shù)據(jù)科學重點實驗室，上海 201203；4.山東大學 計算機科學與技術(shù)學院，山東 濟南 250101)

1 引言

隨著衛(wèi)星導航、無線通信、普適計算技術(shù)的不斷發(fā)展，帶有定位功能的移動智能設(shè)備被廣泛使用。人們在使用這些設(shè)備的同時也主動或被動地記錄了大量的歷史移動軌跡并被持久化保存，形成了時空軌跡（spatio-temporal trajectories）數(shù)據(jù)。時空軌跡是地理空間加上時間軸所形成的多維空間中的一條曲線，可以表示移動對象在一段較長時間范圍內(nèi)的位置變化。每條軌跡由一序列時空采樣點構(gòu)成，其中每個采樣點記錄了位置、時間、方向、速度、甚至人與社會交互活動等信息，刻畫了人們在時空環(huán)境下的個體移動和行為歷史。從宏觀角度來看，海量的軌跡數(shù)據(jù)中不僅蘊含了群體對象的泛在移動模式與規(guī)律，例如人群的移動與活動特征、交通擁堵規(guī)律等，還揭示了交通演化的內(nèi)在機理。在大數(shù)據(jù)時代，企業(yè)級的軌跡數(shù)據(jù)采集、存儲已經(jīng)普遍達到相當規(guī)模并得以有效利用。人們通過軌跡分析等手段進行知識發(fā)現(xiàn)，并將它們運用在各種交通和位置服務(wù)應用系統(tǒng)中，包括交通導航、城市規(guī)劃、服務(wù)推薦、軍事調(diào)度、交通指揮、物流配送、車輛監(jiān)控等。

高質(zhì)量的軌跡數(shù)據(jù)具有重要的社會和應用價值，不僅為解決交通擁堵、改善交通服務(wù)、監(jiān)控道路環(huán)境、緩解能源緊缺等社會問題提供了新的機遇，而且對認知人們的社會活動、優(yōu)化公共資源配置有著特殊意義，成為各政府與企業(yè)的重要財富并受到廣泛重視。在此背景下，軌跡大數(shù)據(jù)管理被學術(shù)、工業(yè)界大量研究，軌跡數(shù)據(jù)分析與挖掘已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的一個重要的新興分支。工業(yè)界和學術(shù)界針對大規(guī)模軌跡數(shù)據(jù)存儲與分析技術(shù)開展了大量的理論和系統(tǒng)探索工作，包括軌跡預處理、索引、查詢優(yōu)化、軌跡分析與挖掘等。這些成果的使用顯著提升了政府管理、社會服務(wù)、企業(yè)盈利能力，并深入影響了人們的生活方式。但是隨著數(shù)據(jù)規(guī)模的指數(shù)級增長，應用需求的飛速提升，現(xiàn)有的軌跡數(shù)據(jù)存儲、計算和分析方法面臨諸多局限，亟需突破軌跡數(shù)據(jù)的處理架構(gòu)、分布式算法等關(guān)鍵技術(shù)。

本文將從軌跡分析的需求入手，從數(shù)據(jù)、應用、技術(shù)3個方面闡述該領(lǐng)域現(xiàn)狀和發(fā)展。在數(shù)據(jù)方面，介紹軌跡數(shù)據(jù)的類型、規(guī)模、頻率等指標，并分析它們對軌跡數(shù)據(jù)管理的影響；在應用方面，將介紹各種軌跡數(shù)據(jù)的典型應用及其場景，并分析其現(xiàn)狀和發(fā)展趨勢；在軌跡管理技術(shù)方面，將分類介紹軌跡數(shù)據(jù)存儲與分析領(lǐng)域的科學問題和前沿技術(shù)，最后展望大數(shù)據(jù)環(huán)境下的軌跡管理技術(shù)存在的問題和發(fā)展方向。

2 企業(yè)級軌跡數(shù)據(jù)現(xiàn)狀

衛(wèi)星定位和移動互聯(lián)技術(shù)在近年來的快速發(fā)展催生了海量的軌跡數(shù)據(jù)。它們記錄了移動對象在時空環(huán)境下的位置采樣序列。軌跡數(shù)據(jù)的來源多樣復雜，可以通過車載GPS、手機服務(wù)、通信基站、公交卡，甚至通過射頻識別、圖像識別、衛(wèi)星遙感、社交媒體數(shù)據(jù)等不同方式獲取，不同的回傳軌跡遵循不同的數(shù)據(jù)格式和坐標系統(tǒng)。同時，軌跡數(shù)據(jù)以極快的速度產(chǎn)生并呈指數(shù)級增長，調(diào)查顯示導航服務(wù)公司所接入的移動對象數(shù)量可達千萬，以高速數(shù)據(jù)流的形態(tài)進入存儲和處理系統(tǒng)。軌跡數(shù)據(jù)的一些關(guān)鍵屬性（例如更新頻率、數(shù)據(jù)總量、每日增量、時空分布等）對數(shù)據(jù)處理和分析平臺搭建有著直接的影響。

本文首先介紹不同采集方式下真實的企業(yè)軌跡數(shù)據(jù)。表1匯總了不同應用中由GPS、地圖服務(wù)、基站、公交卡、道路卡口所采集的軌跡數(shù)據(jù)及其關(guān)鍵屬性。在企業(yè)應用中，對象采樣頻率在秒級、分鐘甚至小時級不等，每天所采集的軌跡數(shù)據(jù)在千萬至百億個采樣點的規(guī)模區(qū)間，最終積累成為TB甚至PB規(guī)模的軌跡數(shù)據(jù)。其中基站定位的軌跡精度較差，通過CellID所對應的基站坐標轉(zhuǎn)換獲取位置信息，因此精度通常在數(shù)百米誤差范圍。而車載GPS和地圖APP所采集的軌跡采樣精度較高，誤差通常在數(shù)米以內(nèi)。軌跡庫已經(jīng)成為各大地圖、導航等服務(wù)公司的重要數(shù)據(jù)資源，單庫的原始軌跡規(guī)模通常在百億條以上。目前已經(jīng)有一些公開的真實軌跡數(shù)據(jù)集可用于研究工作，如GeoLife、T-Drive等。

由表1可知，軌跡數(shù)據(jù)繼承了大數(shù)據(jù)的經(jīng)典“3V”特征，即量大（volume）、實時（velocity）、多樣（variance）。此外，移動對象軌跡數(shù)據(jù)庫的一些特有特征可以總結(jié)如下。

1)時空序列性。軌跡是時空環(huán)境下的采樣序列，這些軌跡點序列蘊含了對象的時空動態(tài)性，數(shù)據(jù)操作是以序列為基本單位，顯著加大了搜索與分析的處理復雜度。

2)異頻采樣性。軌跡的采樣間隔差異顯著，從導航服務(wù)的秒級或分鐘級采樣，到社交媒體行為軌跡的小時甚至以天為間隔的采樣，這種差異性極大影響了軌跡的相似性度量與分析。

3)數(shù)據(jù)質(zhì)量差。由于連續(xù)的運動軌跡被離散化表示，特別是當采樣間隔達到數(shù)分鐘以上或設(shè)備的采樣精度較差時，位置不確定性對軌跡數(shù)據(jù)分析構(gòu)成極大挑戰(zhàn)。

4)路網(wǎng)相關(guān)性。在交通類應用中，軌跡的運行狀態(tài)通常限于交通路網(wǎng)，因此數(shù)據(jù)分析需要首先完成GPS空間向路網(wǎng)空間的映射，并利用路網(wǎng)的時空拓撲信息優(yōu)化數(shù)據(jù)處理。

綜上，軌跡數(shù)據(jù)語義豐富，蘊含著各種移動對象的時空和行為信息，被廣泛應用在諸多企業(yè)級應用中。而軌跡數(shù)據(jù)的上述特征給軌跡數(shù)據(jù)處理與分析提出了一系列要求與挑戰(zhàn)。

3 企業(yè)級軌跡應用

軌跡數(shù)據(jù)記錄了人類的活動和行為歷史，蘊含了群體性的移動模式和規(guī)律。如表2所示，軌跡數(shù)據(jù)搜索與分析已經(jīng)被廣泛應用在智能交通、位置服務(wù)等系統(tǒng)，具體應用主要包括以下幾方面。

1)大眾化經(jīng)驗路徑推薦。路徑搜索和導航服務(wù)的核心挑戰(zhàn)是難以在實時綜合各種因素有效地評估并搜索路徑。一些地圖服務(wù)公司借助軌跡分析手段改進路徑推薦策略，從大規(guī)模軌跡中提取泛在的移動模式，并挖掘不同環(huán)境下的高質(zhì)量“經(jīng)驗”路徑，根據(jù)實時的背景模式匹配（例如根據(jù)氣候、車輛類型、交通、匝道開放狀態(tài)等因素），為用戶推薦更為合理、多樣化的經(jīng)驗路徑，結(jié)果顯示用這種方式顯著提升了用戶體驗。

2)交通路況預測。通過軌跡流統(tǒng)計的方式評估不同區(qū)域的進出流量，檢測施工或故障路段，獲取實時的交通態(tài)勢，為用戶提供道路預警；通過軌跡數(shù)據(jù)分析來深入理解交通路況特征和擁堵的演化模式，綜合運用歷史事件、時空、活動、天氣等多維信息，輔助構(gòu)建數(shù)據(jù)驅(qū)動的城市交通指揮體系，做到指揮決策的先知先覺，警力的優(yōu)化部署，指揮調(diào)度的及時主動；以此引導智能化的交通導航，為導航用戶提供準確的行駛時間預測，并根據(jù)用戶對到達時間的要求推薦路況敏感的合理出行時間。

3)城市規(guī)劃。通過軌跡計算來分析城市不同區(qū)域的社會功能、熱度特征，確定這些城市區(qū)域的性質(zhì)、規(guī)模和發(fā)展方向，提煉城市內(nèi)、城市間的交通流模式。這些信息被用于指導城市開發(fā)、建設(shè)和管理，使有關(guān)部門能夠合理利用土地資源，協(xié)調(diào)城市的空間布局，為城市建設(shè)、重大施工提供決策輔助；為機構(gòu)、商家和各類活動的選址需求提供解決方案；優(yōu)化城市公交、地鐵等公共服務(wù)線路。

4)個性化服務(wù)與活動推薦。社交媒體中的軌跡數(shù)據(jù)記錄了用戶的位置行為，能夠更加深入地分析軌跡，包括對軌跡行為的理解、用戶特征的刻畫、用戶行為模式的挖掘等。針對用戶對多個目的區(qū)域的活動描述，搜索引擎將為用戶推薦能夠滿足查詢意圖的商家或個性化的服務(wù)與活動；考慮軌跡行為和用戶體驗（基于情感分析），為觀光旅客推薦符合用戶興趣和個性化景點、路線。根據(jù)用戶的駕駛路線推測目的地和出行意圖，進行基于位置的精準廣告投放。

5)出租車服務(wù)。軌跡數(shù)據(jù)被用來監(jiān)控出租車的行駛路線，提供對繞路欺客等現(xiàn)象的檢測功能。通過對海量出租車軌跡的分析，系統(tǒng)可以為空駛的出租車優(yōu)化行駛路線（避免交通擁堵區(qū)域、最大化行駛中遇到客戶的概率）；為行人提示就近的有效打車地點，以及實時的、最優(yōu)的公共交通出行路線。一些企業(yè)嘗試通過軌跡挖掘?qū)ふ揖哂邢嗨瞥鲂心Ｊ降挠脩?，實現(xiàn)智能拼車等個性化推薦。

表2 代表性軌跡分析應用

在上述應用系統(tǒng)中，對軌跡數(shù)據(jù)在完整生命周期內(nèi)的有效處理成為共性需求。學術(shù)界和工業(yè)界開展了大量的研究工作，這些技術(shù)使原始軌跡數(shù)據(jù)逐步可用，最后變成所需要的信息與知識。下面將介紹軌跡數(shù)據(jù)管理與分析技術(shù)的前沿成果與研究現(xiàn)狀。

4 軌跡搜索與分析技術(shù)現(xiàn)狀

從軌跡數(shù)據(jù)的生命周期來看，圖1展示了軌跡數(shù)據(jù)金字塔模型，代表了軌跡數(shù)據(jù)的不同認知程度和可用性層次。各層之間緊密聯(lián)系，相互依托。最底層是原始軌跡數(shù)據(jù)，存在很多冗余和噪音，無法被直接使用。通過數(shù)據(jù)預處理，由一系列操作將其轉(zhuǎn)換為校準軌跡。校準軌跡是可用數(shù)據(jù)，但是無法被有效檢索和分析，需要通過數(shù)據(jù)庫管理技術(shù)對其有效組織，成為能夠有效存取的數(shù)據(jù)庫軌跡。在此基礎(chǔ)上，需要進一步對時空、文本等屬性的理解分析，構(gòu)成軌跡數(shù)據(jù)倉庫，形成語義軌跡。最后通過挖掘和分析處理等手段從語義軌跡中得到有用的軌跡知識，服務(wù)各類應用。軌跡金字塔模型體現(xiàn)了軌跡數(shù)據(jù)的知識化過程。

圖1 軌跡金字塔

過去10年中，人們對軌跡數(shù)據(jù)處理技術(shù)進行了大量的探索，使海量軌跡數(shù)據(jù)能夠被及時處理，信息和知識能夠被從中提取。這些技術(shù)按照軌跡金字塔模型分層展開。如圖1所示，它們的目標是使軌跡從底層向高層轉(zhuǎn)化，可以被大致歸納為數(shù)據(jù)預處理（data preprocessing）、軌跡數(shù)據(jù)庫（trajectory database）、軌跡數(shù)據(jù)倉庫（trajectory data warehouse）、知識提?。╰rajectory knowledge discovery）。4種技術(shù)環(huán)環(huán)相扣，使軌跡由原始數(shù)據(jù)轉(zhuǎn)變?yōu)橐?guī)范化數(shù)據(jù)、信息、知識，形成完整的生命周期。本節(jié)首先探討這些關(guān)鍵問題，結(jié)合一些有影響力的科研成果闡述研究現(xiàn)狀。

4.1 數(shù)據(jù)預處理

與其他大數(shù)據(jù)相似，軌跡數(shù)據(jù)存在著一系列的數(shù)據(jù)質(zhì)量問題，主要包括：由定位裝置和物理環(huán)境導致的數(shù)據(jù)不準確（位置）；由設(shè)備、傳輸故障或誤操作等因素導致的數(shù)據(jù)不完整，使部分（通常是一段時間和區(qū)域）數(shù)據(jù)缺失；由不同坐標表示更新策略和語境變換（例如軌跡數(shù)據(jù)集參照了多個地圖或地圖版本等）導致的數(shù)據(jù)不一致；由部分軌跡數(shù)據(jù)導出、備份導致的數(shù)據(jù)冗余。這些數(shù)據(jù)質(zhì)量問題使原始軌跡數(shù)據(jù)不能直接用于分析和挖掘，首先需要通過預處理技術(shù)進行數(shù)據(jù)轉(zhuǎn)換與校準。一般來說，軌跡數(shù)據(jù)的預處理主要包括以下4類操作。

1)軌跡數(shù)據(jù)清洗（data cleaning）旨在去除軌跡中的冗余點（redundant points）和噪音點（noisy points）。冗余點是指可以通過插值等計算導出的采樣，它們顯著增加了系統(tǒng)的存儲和計算開銷，移動對象在靜止和勻速運行狀態(tài)中都會產(chǎn)生大量的冗余點；噪音點是指由軟硬件設(shè)備異常導致的錯誤采樣，它們會極大影響軌跡挖掘和分析結(jié)果?，F(xiàn)有方法主要是從單條軌跡的角度清洗數(shù)據(jù)。借鑒曲線平滑思想，軌跡清洗算法[1,2]智能選取少量的“代表性”采樣點，去除大量的冗余采樣，使該條軌跡的完整時空投影依然能夠被有效表示（基于線性擬合算法）。結(jié)合一些時空規(guī)則，異常的噪音點得以被準確識別并去除。針對實時化的軌跡清洗要求，文獻[3]提出了一種基于時間窗的在線清洗算法。

2)軌跡分段（trajectory segmentation）是指對長時段軌跡（例如以天、月為單位）的合理切分與標注，切分后的每個子軌跡段代表一次出行記錄，是原子級的軌跡分析對象。軌跡分段的核心問題是理解時空移動特征，主流的軌跡分段方式包括基于時間閾值、幾何拓撲和軌跡語義這3種基本策略。以基于語義的軌跡分段為目標，鄭宇在文獻[4]中提出了一種基于GPS軌跡數(shù)據(jù)的停留點檢測（stay points detection）方法，停留點是通過學習得到的經(jīng)常作為起點或終點的位置或區(qū)域，例如天安門廣場、首都機場等，是軌跡分段的重要參考對象；文獻[5]提出了一種基于軌跡聚類的停留點抽取方法。

3)路網(wǎng)匹配（map-matching）是關(guān)聯(lián)軌跡與數(shù)字地圖，將GPS坐標下采樣序列轉(zhuǎn)換為路網(wǎng)坐標序列。路網(wǎng)匹配后的每個軌跡采樣點都映射到一個路網(wǎng)位置，難點在于采樣的位置誤差、低采樣頻率、地圖對路段連續(xù)拓撲的離散化表示等，使每個采樣點坐標無法準確匹配路段。路網(wǎng)匹配算法的核心思想是利用軌跡點之間的時空可達性做匹配校正。為了實現(xiàn)高效的路網(wǎng)匹配，文獻[6]提出了一種基于空間幾何度量的匹配算法；文獻[7]提出了一種基于拓撲Frechet距離的路網(wǎng)匹配算法；文獻[8]采用隱馬爾可夫模型，通過動態(tài)規(guī)劃算法最大化匹配狀態(tài)的轉(zhuǎn)移概率，實現(xiàn)向地圖空間的精準映射。文獻[9～11]解決了基于簡化地圖的高效路網(wǎng)匹配問題。

4)軌跡校準（trajectory calibration）是保證軌跡數(shù)據(jù)可用性的重要技術(shù)。面向低頻采樣軌跡，文獻[12]提出了一種基于軌跡移動模式學習的位置不確定消減機制。軌跡數(shù)據(jù)的質(zhì)量問題很大程度上是由于采樣率差異過大導致的。當2個軌跡的采樣率差別較大時，直接基于它們的采樣點進行相似性比較沒有意義，需要對原始軌跡校準以便合理評估軌跡相似性。文獻[13]提出了2種考慮空間特性的校準模型，通過機器學習算法訓練得到參照系統(tǒng)，在該系統(tǒng)中去除冗余數(shù)據(jù)并補全重要缺失采樣。文獻[14]進一步同時考慮了時間和空間屬性，滿足時空雙重受限的軌跡相似性分析要求，大幅提升軌跡校準效果并得到高質(zhì)量軌跡數(shù)據(jù)。

4.2 軌跡數(shù)據(jù)庫

軌跡數(shù)據(jù)庫是軌跡大數(shù)據(jù)管理的核心，是數(shù)據(jù)搜索與處理性能的保證。傳統(tǒng)數(shù)據(jù)庫技術(shù)不適用于管理高度冗余、非結(jié)構(gòu)化變長的軌跡數(shù)據(jù)。為了實現(xiàn)大規(guī)模軌跡數(shù)據(jù)在數(shù)據(jù)庫的有效管理與組織，人們針對軌跡數(shù)據(jù)模型、軌跡壓縮、軌跡索引等核心問題展開了大量研究。

軌跡數(shù)據(jù)模型（trajectory data model）是軌跡數(shù)據(jù)在數(shù)據(jù)庫中的表示方法，是數(shù)據(jù)組織與管理的基礎(chǔ)。軌跡數(shù)據(jù)模型起源于移動對象數(shù)據(jù)庫，早期工作主要是基于關(guān)系模型擴展，包括Wolfson等提出的MOST模型[15]，將移動對象的位置信息表示為動態(tài)屬性；Guting等在文獻[16]中，設(shè)計了一種基于抽象數(shù)據(jù)類型ADT的模型和類似SQL的查詢語言，以移動點和移動區(qū)域為基本抽象。近些年隨著Hadoop的興起，軌跡數(shù)據(jù)模型被極大簡化，通常是以移動對象為中心，以序列化軌跡點來靈活表示，數(shù)據(jù)在HDFS中持久化保存。面向?qū)崟r軌跡數(shù)據(jù)分析的需求，文獻[17]借鑒視頻數(shù)據(jù)表示機制，提出了一種以時間為中心的軌跡模型，基于該模型的軌跡數(shù)據(jù)庫SharkDB適用于內(nèi)存計算環(huán)境、對時間受限的軌跡分析（如實時交通流、擁堵識別與趨勢分析等）具有天然優(yōu)勢。

軌跡壓縮（trajectory compression）。由于軌跡數(shù)據(jù)的低價值密度和存儲設(shè)備限制，數(shù)據(jù)庫無法保存全部軌跡數(shù)據(jù)，通常需要對軌跡數(shù)據(jù)集進行壓縮存儲?，F(xiàn)有軌跡壓縮方法主要分為3類。

1) 基于路網(wǎng)（road network based）的壓縮[18,19]。對基于路網(wǎng)表示的軌跡通過路段拓撲和編碼等方法來壓縮軌跡數(shù)據(jù)存儲空間。

2)基于軌跡（trajectory based）的壓縮[2,3,20]，主流研究側(cè)重于單條軌跡的壓縮，通過對移動對象軌跡建模，去除可通過模型（插值）還原的軌跡點，例如路網(wǎng)最短路徑上的軌跡點，保證與原軌跡的誤差符合精度范圍。

3) 基于幀編碼（frameencoding based）的壓縮[17]，每個對象在關(guān)鍵幀中記錄精確的采樣信息，在非關(guān)鍵幀中僅記錄采樣與上一幀中的偏移值，從而大幅壓縮數(shù)據(jù)量。

軌跡查詢與索引（trajectory indexing）。軌跡分析依賴于大量的查詢操作，根據(jù)用戶給定的移動對象、時空范圍、移動屬性（如平均/瞬時速度、軌跡長度、采樣頻率等）值域等條件，返回用戶或分析所需的相關(guān)軌跡。

軌跡數(shù)據(jù)的高效檢索依賴于數(shù)據(jù)索引。在空間數(shù)據(jù)庫中最經(jīng)典的索引結(jié)構(gòu)是R-tree[21]及其改進版本，若直接使用三維的3D R-tree對軌跡索引將導致諸多問題，如死區(qū)(dead space)過大、軌跡的完整性被破壞等。針對這些問題Pfoster等在文獻[22]中提出了TB-tree索引結(jié)構(gòu)，嚴格地讓每個葉節(jié)點只包含屬于同一軌跡的線段以最大限度地保證軌跡的完整性。有些學者嘗試把軌跡的時間和空間維度分別進行索引，把數(shù)據(jù)在時間維度上進行劃分然后分別用R-tree組織起來，每個R-tree對應的是一個時間點（HR-tree[23]）或時間段（MV3R-tree[24]），這種結(jié)構(gòu)可以更好地處理基于時間的軌跡查詢。文獻[25]提出了一種空間優(yōu)先劃分的格柵索引結(jié)構(gòu)，對基于空間區(qū)域的查詢有很好的效果。

除了上述通用軌跡索引，還有一些工作研究重點在于面向定制查詢的索引設(shè)計，例如面向路網(wǎng)受限軌跡查詢的NDTR-tree[26]以及基于LCSS[27]、ERP[28]、EDR[29]、k-BCQ[30]等軌跡相似性度量的索引結(jié)構(gòu)[27～30]。結(jié)合相應的查詢優(yōu)化技術(shù)，這些索引支持了各種類型的軌跡精準查詢與個性化軌跡分析的快速處理。

4.3 軌跡數(shù)據(jù)倉庫

軌跡知識發(fā)現(xiàn)以對數(shù)據(jù)的深刻理解為前提。學者們?yōu)榇苏归_大量研究，試圖融合各種相關(guān)信息，理解軌跡數(shù)據(jù)背后的時空與行為特征，將軌跡數(shù)據(jù)轉(zhuǎn)換為易于理解的語義軌跡（semantic trajectories），構(gòu)建軌跡數(shù)據(jù)倉庫。

移動性理解（mobility understanding）。對軌跡的認知首先是從時空角度，對用戶運動方式進行分析。文獻[31]研究了基于軌跡運動方式（如步行、騎車、公交、自駕等）的軌跡分段與標注，設(shè)計了一種基于條件隨機場模型的算法最大化分段精度，使對軌跡運動方式的精準標注成為可能。近年來，人們越來越多地關(guān)注如何通過時空統(tǒng)計的方法理解移動對象的共性移動，匯總趨勢性信息。

行為理解（activity understanding）的目標是理解用戶在軌跡中的行為或可能的行為。對軌跡行為的理解需要在時空維度之外引入文本描述，現(xiàn)有方法主要通過2種方式。第1種是將軌跡數(shù)據(jù)與興趣點（point of interests）和簽到（check-ins）數(shù)據(jù)結(jié)合[32,33]，豐富用戶在軌跡停留點可能的行為內(nèi)容`。第2種是從社交媒體、簽到數(shù)據(jù)中爬取行為軌跡（activity trajectories），其中每個軌跡點包含時空、文本和其他信息，表示了用戶在不同位置的狀態(tài)和行為。與傳統(tǒng)時空軌跡相比，上述軌跡包含了更多維度信息，因此難于管理，鄭凱等在文獻[34]中提出了一種高效的檢索框架。

軌跡相似性（trajectory similarity）用于評估不同軌跡之間的時空曲線和語義相似程度，是軌跡搜索與挖掘的核心。在基于空間的軌跡相似性度量函數(shù)方面，除了經(jīng)典DTW、LCSS，陳雷等在文獻[29]中定義一種基于軌跡編輯距離的EDR函數(shù)，文獻[35]定義了考慮連續(xù)性的度量指標OWD。針對時空環(huán)境下的軌跡相似性度量，人們在此基礎(chǔ)上進行了時間維度的擴展[27]。針對包含用戶行為信息的語義軌跡，文獻[36]定義了一種融合文本相似度的軌跡距離。文獻[37]針對軌跡不確定性定義了一種基于概率的相似性評估機制。

4.4 軌跡知識提取

軌跡數(shù)據(jù)挖掘旨在從軌跡中發(fā)現(xiàn)有價值的知識和模型，已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的一個重要新興分支[38]，被廣泛使用在各類應用之中?，F(xiàn)有的軌跡知識提取工作主要從基于軌跡的數(shù)據(jù)挖掘和語義歸納2個角度展開。

1)頻繁模式挖掘（frequent patterns）旨在從大規(guī)模軌跡中發(fā)現(xiàn)時序模式，例如超過一定數(shù)量的對象在給定時間間隔內(nèi)行駛的公共路徑，對目的地預測、路徑推薦、行為理解有重要的價值。文獻[39]將空間格柵化，根據(jù)GPS采樣點密度將格柵組合成為區(qū)域，通過頻繁項挖掘算法提取頻繁模式；文獻[40]提出了一種基于前綴樹的頻繁軌跡高效挖掘方法，避免過量的子軌跡組合驗證；文獻[41]定義了體現(xiàn)出行共性規(guī)律的頻繁路徑，并設(shè)計了一種高效的頻繁路徑搜索策略。在此基礎(chǔ)上，文獻[42]設(shè)計了一種基于離群檢測機制的異常軌跡提取方法。文獻[43,44]通過軌跡學習實現(xiàn)有效的目的地預測，此外，文獻[45]研究了面向大規(guī)模軌跡的周期性模式挖掘。

2)伴行模式挖掘（moving together patterns）在軌跡數(shù)據(jù)中提取伴行的移動對象，用于事故調(diào)查、軍事監(jiān)控等應用。代表性的軌跡模式主要包括Flock[46]、Convey[47]、Swarm[48]、Gathering[49,50]等。其中，F(xiàn)lock模式挖掘[46,47]旨在發(fā)現(xiàn)給定時間間隔內(nèi)可被給定面積覆蓋的一組移動對象；Convey模式[46,47]則是根據(jù)密度來挖掘緊密伴行的移動對象，避免過于機械化的空間閾值限定；而Swarm[48]是一種更為通用化的軌跡模式。文獻[51]提出了面向軌跡數(shù)據(jù)流的伴行模式在線挖掘方法。

3)軌跡聚類、分類（trajectory clustering and classification）。對移動軌跡的時空聚類可以幫助發(fā)現(xiàn)具有代表性和趨勢性的移動模式。早期的軌跡聚類是以整條軌跡為對象。但是由于移動對象軌跡通常不完全重疊，文獻[52]設(shè)計了一種基于分段軌跡、以豪斯多夫距離為度量的聚類方法，顯著提升了聚類效果。文獻[53]提出了增量式的軌跡聚類算法，降低軌跡聚類處理的時間和空間開銷。而軌跡分類問題[31]則是根據(jù)行為、交通方式等特征來區(qū)別不同類型軌跡。此外，文獻[54]提出了一種基于軌跡的高影響力位置挖掘算法。袁晶等[55]所研發(fā)了T-Drive系統(tǒng)從軌跡數(shù)據(jù)中學習出租車的運行規(guī)律和經(jīng)驗，為用戶推薦更為通暢、便捷的路徑以及出發(fā)時間的合理推薦。

4)軌跡摘要（trajectory summarization）是以文本的方式來概要一條軌跡所包含的信息，使軌跡數(shù)據(jù)更加易于理解。文獻[54]提出了一種基于軌跡切分的摘要方法，使軌跡段內(nèi)語義相似、軌跡段間語義不同，最后通過短文本總結(jié)蘊含在軌跡數(shù)據(jù)中的時空、交通、行為等各維度信息。

5 結(jié)束語

移動對象軌跡數(shù)據(jù)已經(jīng)成為一種基本的數(shù)據(jù)資源，相關(guān)應用具有無限的潛力。因此，分析移動軌跡所蘊含的知識是認知用戶、人群和城市行為的重要手段。軌跡數(shù)據(jù)與其他數(shù)據(jù)、特別是用戶行為數(shù)據(jù)的疊加將產(chǎn)生更為巨大的商業(yè)和社會價值。企業(yè)級的軌跡數(shù)據(jù)已經(jīng)積累到相當大規(guī)模，且增量數(shù)據(jù)以極快速度產(chǎn)生。因此，多用途、易擴展的軌跡數(shù)據(jù)管理系統(tǒng)已經(jīng)成為上述應用的共性需求。

為了滿足上述需求，人們對軌跡預處理、數(shù)據(jù)庫、數(shù)據(jù)倉庫和知識提取等一系列問題展開研究，取得了豐碩的成果。通過這些技術(shù)，軌跡數(shù)據(jù)能夠被有效處理，從中提取的知識被應用于車輛導航、行程推薦、城市規(guī)劃等中。但是隨著軌跡數(shù)據(jù)規(guī)模的快速增長，各類位置服務(wù)的涌現(xiàn)，現(xiàn)有的軌跡處理技術(shù)在處理性能、分析能力等方面已經(jīng)無法滿足實際應用需求。

未來，軌跡數(shù)據(jù)管理需要重點突破以下關(guān)鍵技術(shù)。在數(shù)據(jù)庫/數(shù)據(jù)倉庫技術(shù)方面，現(xiàn)有的軌跡數(shù)據(jù)庫主要面對集中式的軌跡管理，無法支持企業(yè)級大規(guī)模、高增量軌跡數(shù)據(jù)的高效處理，因此分布式環(huán)境下、可動態(tài)擴容的軌跡存儲與計算框架將成為熱點問題；在軌跡數(shù)據(jù)的理解與分析方面，為了充分發(fā)掘數(shù)據(jù)背后的巨大價值，如何集成軌跡與其他網(wǎng)絡(luò)數(shù)據(jù)業(yè)務(wù)，從中準確地刻畫用戶行為并挖掘交通模式將受到更為廣泛的關(guān)注。同時，軌跡數(shù)據(jù)管理作為一個跨學科研究問題，涉及地理信息系統(tǒng)、智能交通、數(shù)據(jù)庫、數(shù)據(jù)挖掘等不同領(lǐng)域，需要這些不同領(lǐng)域的研究人員共同協(xié)作，最終實現(xiàn)軌跡數(shù)據(jù)完整生命周期的有效管理和價值發(fā)現(xiàn)。

[1]SCHUESSLER N,AXHAUSEN K.Processing raw data from global positioning systems without additional information[J].Transportation Research Record:Journal of the Transportation Research Board,2009(2105):28-36.

[2] DOUGLAS D H,PEUCKER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10(2):112-122.

[3] MERATNIA N,ROLF A.Spatiotemporal compression techniques for moving point objects[A].Advances in Database Technology-EDBT[C].2004.765-782.

[4] ZHENG Y,et al.Mining interesting locations and travel sequences from GPS trajectories[A].Proceedings of the 18th International Conference on World Wide Web[C].2009.

[5] PALMA A T,et al.A clustering-based approach for discovering interesting places in trajectories[A].Proceedings of the 2008 ACM Symposium onApplied Computing[C].2008.

[6] GREENFELD J S,Matching GPS observations to locations on a digital map[A].Transportation Research Board 81stAnnual Meeting[C].2002.

[7]BRAKATSOULAS S,et al.On map-matching vehicle tracking data[A].Proceedings of the 31st International Conference on Very Large Data Bases[C].2005.

[8]NEWSON P,KRUMM J.Hidden Markov map matching through noise and sparseness[A].Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].2009.

[9] LIU K,et al.Effective map-matching on the most simplified road network[A].Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C].2012.ACM.

[10]LI S,et al.Quick geo-fencing using trajectory partitioning and boundary simplification[A]. Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].2013.

[11]TANG Y,ZHU A D,XIAO X.An efficient algorithm for mapping vehicle trajectories onto road networks[A].Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C].2012.

[12]ZHENG K,etal.Reducing uncertainty oflow-sampling-rate trajectories[A]. Data Engineering (ICDE), 2012 IEEE 28th International Conference on[C].2012.

[13]SU H,et al.Calibrating trajectory data for similarity-based analysis[A].Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data[C].2013.

[14]SU H,et al.Calibrating trajectory data for spatio-temporal similarity analysis[J].The VLDB Journal,2015,24(1):93-116.

[15]SISTLA A P,et al.Modeling and querying moving objects[A].ICDE[C].1997.

[16]GüTING R H,et al.A foundation for representing and querying moving objects[J].ACM Transactions on Database Systems(TODS),2000,25(1):1-42.

[17]WANG H,et al.SharkDB:An in-memory column-oriented trajectory storage[A].Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management[C].2014.

[18]KELLARIS PELEKIS G N,THEODORIDIS Y.Trajectory compression under network constraints[A].Advances in Spatial and Temporal Databases[C].2009.392-398.

[19]SONG R,et al.PRESS:A novel framework of trajectory compression in road networks[J].Proceedings of the VLDB Endowment,2014,7(9):661-672.

[20]CHAN W S,CHIN F,Approximation of polygonal curves with minimum number of line segments or minimum error[J].International Journal of Computational Geometry&Applications,1996,6(1):59-77.

[21]GUTTMAN A,R-trees:a dynamic index structure for spatial searching[A].SIGMOD[C].1984.47-57.

[22]PFOSER D,JENSEN C S,THEODORIDIS Y.Novel approaches to the indexing ofmoving objecttrajectories[A].Proceedingsof VLDB[C].2000.

[23]NASCIMENTO M A,SILVA J R.Towards historical R-trees[A].Proceedings of the 1998 ACM Symposium on Applied Computing[C].1998.

[24]YUFEI T,PAPADIAS D.MV3R-tree:a spatio-temporal access method for timestamp and interval queries[A].VLDB[C].2001.431-440.

[25]CHAKKA V P,EVERSPAUGH A C,PATEL J M.Indexing large trajectory data sets with SETI[A].CIDR[C].2003.

[26]丁治明.一種適合于頻繁位置更新的網(wǎng)絡(luò)受限移動對象軌跡索引[J].計算機學報,2012,35(7):1448-1461.DING Z M.An index structure for frequently updated network-constrainted moving object trajectories[J].Chinese Journal of Computers,2012,35(7):1448-1461.

[27]VLACHOS M,KOLLIOS G,GUNOPULOS D.Discovering similar multidimensional trajectories[A].Data Engineering,2002 Proceedings 18th International Conference on[C].2002.

[28]CHEN L,NG R.On the marriage of lp-norms and edit distance[A].Proceedings of the Thirtieth International Conference on Very Large Data Bases-Volume[C].2004.

[29]CHEN L,?ZSU M T,ORIA V.Robust and fast similarity search for movingobjecttrajectories[A].Proceedingsofthe2005 ACM SIGMOD International Conference on Management of Data[C].2005.ACM.

[30]CHEN Z,et al.Searching trajectories by locations:an efficiency study[A].Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data[C].2010.

[31]ZHENG Y,et al.Learning transportation mode from raw gps data for geographic applications on the web[A].Proceedings of the 17th International Conference on World Wide Web[C].2008.

[32]YAN Z,et al.Semantic trajectories:Mobility data computation and annotation[J].ACM Transactions on IntelligentSystems and Technology(TIST),2013,4(3):49.

[33]ALVARES L O,et al.A model for enriching trajectories with semantic geographical information[A].Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems[C].2007.

[34]ZHENG K,et al.Towards efficient search for activity trajectories[A].Data Engineering (ICDE), 2013 IEEE 29th International Conference[C].2013.

[35]LIN B,SU J.One way distance:For shape based similarity search of moving object trajectories[J].Geoinformatica,2008,12(2):117-142.

[36]ZHENG B,et al.Approximate keyword search in semantic trajectory database[A].Data Engineering(ICDE),2015 IEEE 31st International Conference[C].2015.

[37]MA C,et al.KSQ:Top-ksimilarity query on uncertain trajectories[J].Knowledge and Data Engineering,IEEE Transactions 2013,25(9):2049-2062.

[38]ZHENG Y.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems and Technology(TIST),2015,6(3):29.

[39]GIANNOTTI F.et al.Trajectory pattern mining[A].Proceedings of the 13thACM SIGKDD InternationalConferenceon Knowledge Discovery and Data Mining[C].2007.

[40]WANG Y,ZHENG Y,XUE Y.Travel time estimation of a path using sparse trajectories[A].Proceedings of the 20th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining[C].2014.

[41]CHEN Z,SHEN H T,ZHOU X.Discovering popular routes from trajectories[A]. Data Engineering (ICDE), 2011 IEEE 27th International Conference[C].2011.

[42]LEE J G,HAN J,LIX.Trajectory outlierdetection:A partition-and-detect framework[A].Data Engineering,ICDE 2008 IEEE 24th International Conference[C].2008.

[43]KRUMM J,HORVITZ E.Predestination:Inferring destinations from partial trajectories[A].UbiComp 2006:Ubiquitous Computing[C].2006.243-260.

[44]LIAO L,et al.Learning and inferring transportation routines[J].Artificial Intelligence,2007,171(5):311-331.

[45]CAO H,MAMOULIS N,CHEUNG D W.Discovery of periodic patterns in spatiotemporalsequences[J].Knowledge and Data Engineering,IEEE Transactions on,2007,19(4):453-467.

[46]GUDMUNDSSON J,KREVELD M V.Computing longest duration flocks in trajectory data[A].Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems[C].2006.ACM.

[47]JEUNG H,et al.Discovery of convoys in trajectory databases[J].Proceedings of the VLDB Endowment,2008,1(1):1068-1080.

[48]LI Z,et al.Swarm:Mining relaxed temporal moving object clusters[J].Proceedings of the VLDB Endowment,2010,3(1-2):723-734.

[49]ZHENG K,ZHENG Y,et al.On discovery of gathering patterns from trajectories[A].ICDE[C].2013.242-253

[50]ZHENG K,ZHENG Y,et al.Online discovery of gathering patterns over trajectories[J].IEEE Trans Knowl Data Eng,2004 26(8):1974-1988.

[51]TANG L A,et al.On discovery of traveling companions from streaming trajectories[A].Data Engineering(ICDE),IEEE 28th International Conference[C].2012.

[52]LEE JG,HAN J,WHANG K Y.Trajectoryclustering:a partition-and-group framework[A].Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data[C].2007.

[53]LI Z,et al.Incremental clustering for trajectories[A].Database Systems forAdvancedApplications[C].2010.

[54]CAO X,CONG G,JENSEN C S.Mining significant semantic locations from GPS data[J].Proceedings of the VLDB Endowment,2010,3(1-2):1009-1020.

[55]YUAN J,et al.T-drive:driving directions based on taxi trajectories[A].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].2010.

[56]SU H,et al.Making sense of trajectory data:a partition-andsummarization approach[A].Data Engineering(ICDE),IEEE 31st International Conference[C].2015.