基于分布式3D R-Tree索引的軌跡查詢方法研究

王麗明，熊 文

(云南師范大學(xué) 信息學(xué)院，云南 昆明 650000)

0 引言

隨著現(xiàn)代城市公共交通系統(tǒng)的發(fā)展，數(shù)以十萬計(jì)的出租車、網(wǎng)約車和公共汽車每天為城市居民提供日常出行服務(wù)。這些車輛均部署了GPS終端設(shè)備，時(shí)刻采集并上報(bào)車輛的GPS軌跡數(shù)據(jù)。如何管理和分析這些軌跡數(shù)據(jù)，用來提升運(yùn)營水平和服務(wù)質(zhì)量是管理部門面臨的首要問題。如何對數(shù)以億計(jì)的GPS軌跡進(jìn)行索引和快速響應(yīng)是一個極具挑戰(zhàn)的難題。

對于GPS軌跡的存儲和查詢，通常采用構(gòu)建索引等方法來提高查詢效率。Ding[1]利用時(shí)空索引(ST-Index)和連接索引(Con-Index)減少軌跡數(shù)據(jù)冗余的訪問操作。Hanan[2]使用遞歸分解的四叉樹建立索引，當(dāng)節(jié)點(diǎn)達(dá)到最大容量時(shí)，可以進(jìn)行分裂，缺點(diǎn)是如果對象分布不均勻，將會形成不平衡四叉樹，導(dǎo)致查詢效率急劇下降。此外，還有一些R-Tree的改進(jìn)版本，如IR2-Tree[3]，利用疊加文本和R-Tree相結(jié)合來處理指定位置和關(guān)鍵字的查詢。

這些方法都在單節(jié)點(diǎn)實(shí)現(xiàn)，在數(shù)據(jù)規(guī)模較小時(shí)可以較好地解決查詢效率的問題。但是，當(dāng)數(shù)據(jù)規(guī)模上升以后，這些方法性能會持續(xù)下降。因此，本研究嘗試借助大數(shù)據(jù)和分布式索引來解決該問題。本文借助大數(shù)據(jù)計(jì)算引擎的Spark的核心組件RDD，對3D R-tree[4]進(jìn)行分布式的實(shí)現(xiàn)，并使用3個經(jīng)典查詢，包括軌跡點(diǎn)、子串和區(qū)域查詢，分析運(yùn)行時(shí)間并對比了空間網(wǎng)格分區(qū)和時(shí)空網(wǎng)格分區(qū)方法下3種查詢類型的性能。

1 背景與動機(jī)

以深圳市為例，截至2019年12月，該市擁有公交車1.9萬輛，巡游出租車3萬輛，網(wǎng)約車8萬輛。假設(shè)每輛車每30 s產(chǎn)生一條GPS記錄。這些車輛每天可以產(chǎn)生3.7億條GPS記錄。傳統(tǒng)的索引方式在單機(jī)環(huán)境下顯然沒有能力處理如此規(guī)模的GPS軌跡數(shù)據(jù)。因此，本研究嘗試借助Spark的RDD組件構(gòu)建分布式的時(shí)空索引來應(yīng)對大規(guī)模軌跡查詢需求。

經(jīng)典軌跡查詢有軌跡點(diǎn)、子串和區(qū)域查詢。本文對軌跡點(diǎn)查詢形式化定義如下：給定一個軌跡集合S，一個查詢時(shí)間范圍T=，一個查詢點(diǎn)q。點(diǎn)查詢返回所有滿足以下條件的軌跡tri∈S：tri中至少存在一個GPS點(diǎn)pk產(chǎn)生于時(shí)間范圍T內(nèi)且等于q。如式(1)所示：

Point_query(S,T,q)={tri∈S|?pk∈tri^

pk=q,timemin≤pk.t≤timemax}

(1)

本文對子串查詢形式化定義如下：給定一個軌跡集合S，一個查詢時(shí)間范圍T=，一條查詢軌跡q。子串查詢返回所有滿足以下條件的軌跡tri∈S：對于每一個pk∈q，均有pk∈tri，且GPS點(diǎn)pk產(chǎn)生于時(shí)間范圍T內(nèi)。如式(2)所示：

Substring_query(S,T,q)={tri∈S|q?tri^

pk∈q,timemin≤pk.t≤timemax}

(2)

本文對區(qū)域查詢形式化定義如下：給定一個軌跡集合S，一個查詢時(shí)間范圍T=，一個經(jīng)緯度范圍q=。區(qū)域查詢返回所有滿足以下條件的軌跡tri∈S：tri中至少存在一個GPS點(diǎn)pk產(chǎn)生于時(shí)間范圍T和經(jīng)緯度范圍q內(nèi)。如式(3)所示：

Range_query(S,T,q)={tri∈S|?pk∈tri,

timemin≤pk.t≤timemax^latmin≤pk.lat≤

latmax^lngmin≤pk.lng≤lngmax}

(3)

2 數(shù)據(jù)預(yù)處理

車輛所處的位置例如隧道、高樓對信號傳輸影響，以及由GPS設(shè)備自身測量精度導(dǎo)致的局限，導(dǎo)致GPS軌跡數(shù)據(jù)質(zhì)量存在一定的偏差。具體表現(xiàn)是車輛軌跡中部分GPS點(diǎn)不在對應(yīng)的路網(wǎng)上。因此，需要對GPS軌跡進(jìn)行校準(zhǔn)，本文使用FMM[5]方法對GPS數(shù)據(jù)進(jìn)行地圖匹配。

3 索引的建立

3.1 數(shù)據(jù)分區(qū)

RDD是一個分布式的數(shù)據(jù)結(jié)構(gòu)，以一個分區(qū)規(guī)則將數(shù)據(jù)集合劃分為多個分區(qū)。本研究建立分布式索引，以實(shí)現(xiàn)大規(guī)模軌跡數(shù)據(jù)查詢。本研究使用空間網(wǎng)格和時(shí)空網(wǎng)格兩種分區(qū)方法。

3.2 空間索引

空間索引是指將空間對象按一定的規(guī)則進(jìn)行排列組織，在查詢時(shí)可以篩選掉大量與特定對象無關(guān)的空間對象，提高查詢的速度。本文建立全局索引和局部索引，劃分全局索引的依據(jù)是軌跡所在的網(wǎng)格編號，每個RDD分區(qū)存儲軌跡的部分片段。在每個分區(qū)內(nèi)部對軌跡數(shù)據(jù)構(gòu)建3D R-tree為局部索引。查詢時(shí)，通過全局索引定位局部索引，在局部索引樹中執(zhí)行具體查詢。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)集

本次實(shí)驗(yàn)的數(shù)據(jù)集是以深圳市30 747輛出租車?yán)塾?jì)一周的GPS軌跡數(shù)據(jù)，約2.97億條數(shù)據(jù)，來建立索引和進(jìn)行查詢。

4.2 實(shí)驗(yàn)對比

測試在兩種分區(qū)方法下，位于大鵬區(qū)、坪山區(qū)、龍華區(qū)、龍崗區(qū)和南山區(qū)的軌跡點(diǎn)查詢時(shí)延。查詢時(shí)延是指從提交查詢請求到返回查詢結(jié)果所消耗的時(shí)間。結(jié)果如圖1所示，在不同位置查詢，時(shí)延不同。在空間網(wǎng)格分區(qū)方式下，綜合平均時(shí)延為2.79 s。在時(shí)空網(wǎng)格分區(qū)方式下，綜合平均時(shí)延為2.33 s。

圖1 軌跡點(diǎn)查詢

測試在兩種分區(qū)方式下，子串查詢長度分別為5，10，15，20，25個軌跡點(diǎn)時(shí)，子串查詢所需的查詢時(shí)延。結(jié)果如圖2所示，在空間網(wǎng)格方法下，查詢分別需要1.42 s、4.32 s、4.48 s、4.75 s、4.81 s，綜合平均時(shí)延為3.96 s。在時(shí)空網(wǎng)格分區(qū)方式下，查詢分別需要1.35 s、3.73 s、3.80 s、3.84 s、3.96 s，綜合平均時(shí)延為3.33 s。查詢時(shí)延都隨著查詢子串長度變長而變長。

圖2 子串查詢

測試在兩種分區(qū)方式下，區(qū)域查詢范圍分別為1×1 km2、2×2 km2、3×3 km2、4×4 km2、5×5 km2時(shí)，統(tǒng)計(jì)查詢所需時(shí)間。結(jié)果如圖3所示，空間網(wǎng)格方法查詢，分別需要13.79 s、14.04 s、14.36 s、14.93 s、15.33 s，綜合平均時(shí)延為14.49 s。在時(shí)空網(wǎng)格分區(qū)方式下，查詢分別需要2.90 s、4.89 s、6.43 s、8.62 s、11.57 s，綜合平均時(shí)延為6.88 s。查詢時(shí)延都隨著查詢范圍的擴(kuò)大而變長。

圖3 區(qū)域查詢

5 結(jié)語

本文利用Spark平臺實(shí)現(xiàn)了基于3D R-Tree的出租車軌跡數(shù)據(jù)查詢，對比了空間網(wǎng)格和時(shí)空網(wǎng)格兩種分區(qū)方式。實(shí)驗(yàn)表明，在軌跡點(diǎn)查詢下，不同的位置查詢時(shí)延不同；在子串查詢下，查詢軌跡長度越長，查詢時(shí)延越長；在區(qū)域查詢下，查詢的范圍越大，查詢時(shí)延越長；用時(shí)空網(wǎng)格分區(qū)方法比用空間網(wǎng)格分區(qū)方法的查詢時(shí)延短。在下一步的工作中，本研究計(jì)劃在Spark streaming流式處理框架實(shí)現(xiàn)基于3D R-tree的流式軌跡數(shù)據(jù)查詢。