基于分布式3D R-Tree索引的軌跡查詢方法研究
2022-02-16 12:10:08王麗明
無線互聯(lián)科技 2022年23期
王麗明，熊 文
(云南師范大學(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)營(yíng)水平和服務(wù)質(zhì)量是管理部門面臨的首要問題。如何對(duì)數(shù)以億計(jì)的GPS軌跡進(jìn)行索引和快速響應(yīng)是一個(gè)極具挑戰(zhàn)的難題。
對(duì)于GPS軌跡的存儲(chǔ)和查詢，通常采用構(gòu)建索引等方法來提高查詢效率。Ding[1]利用時(shí)空索引(ST-Index)和連接索引(Con-Index)減少軌跡數(shù)據(jù)冗余的訪問操作。Hanan[2]使用遞歸分解的四叉樹建立索引，當(dāng)節(jié)點(diǎn)達(dá)到最大容量時(shí)，可以進(jìn)行分裂，缺點(diǎn)是如果對(duì)象分布不均勻，將會(huì)形成不平衡四叉樹，導(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ī)模上升以后，這些方法性能會(huì)持續(xù)下降。因此，本研究嘗試借助大數(shù)據(jù)和分布式索引來解決該問題。本文借助大數(shù)據(jù)計(jì)算引擎的Spark的核心組件RDD，對(duì)3D R-tree[4]進(jìn)行分布式的實(shí)現(xiàn)，并使用3個(gè)經(jīng)典查詢，包括軌跡點(diǎn)、子串和區(qū)域查詢，分析運(yùn)行時(shí)間并對(duì)比了空間網(wǎng)格分區(qū)和時(shí)空網(wǎng)格分區(qū)方法下3種查詢類型的性能。
1 背景與動(dòng)機(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)對(duì)大規(guī)模軌跡查詢需求。
經(jīng)典軌跡查詢有軌跡點(diǎn)、子串和區(qū)域查詢。本文對(duì)軌跡點(diǎn)查詢形式化定義如下：給定一個(gè)軌跡集合S，一個(gè)查詢時(shí)間范圍T=
Point_query(S,T,q)={tri∈S|?pk∈tri^
pk=q,timemin≤pk.t≤timemax}
(1)
本文對(duì)子串查詢形式化定義如下：給定一個(gè)軌跡集合S，一個(gè)查詢時(shí)間范圍T=
Substring_query(S,T,q)={tri∈S|q?tri^
pk∈q,timemin≤pk.t≤timemax}
(2)
本文對(duì)區(qū)域查詢形式化定義如下：給定一個(gè)軌跡集合S，一個(gè)查詢時(shí)間范圍T=
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ù)處理
車輛所處的位置例如隧道、高樓對(duì)信號(hào)傳輸影響，以及由GPS設(shè)備自身測(cè)量精度導(dǎo)致的局限，導(dǎo)致GPS軌跡數(shù)據(jù)質(zhì)量存在一定的偏差。具體表現(xiàn)是車輛軌跡中部分GPS點(diǎn)不在對(duì)應(yīng)的路網(wǎng)上。因此，需要對(duì)GPS軌跡進(jìn)行校準(zhǔn)，本文使用FMM[5]方法對(duì)GPS數(shù)據(jù)進(jìn)行地圖匹配。
3 索引的建立
3.1 數(shù)據(jù)分區(qū)
RDD是一個(gè)分布式的數(shù)據(jù)結(jié)構(gòu)，以一個(gè)分區(qū)規(guī)則將數(shù)據(jù)集合劃分為多個(gè)分區(qū)。本研究建立分布式索引，以實(shí)現(xiàn)大規(guī)模軌跡數(shù)據(jù)查詢。本研究使用空間網(wǎng)格和時(shí)空網(wǎng)格兩種分區(qū)方法。
3.2 空間索引
空間索引是指將空間對(duì)象按一定的規(guī)則進(jìn)行排列組織，在查詢時(shí)可以篩選掉大量與特定對(duì)象無關(guān)的空間對(duì)象，提高查詢的速度。本文建立全局索引和局部索引，劃分全局索引的依據(jù)是軌跡所在的網(wǎng)格編號(hào)，每個(gè)RDD分區(qū)存儲(chǔ)軌跡的部分片段。在每個(gè)分區(qū)內(nèi)部對(duì)軌跡數(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)對(duì)比
測(cè)試在兩種分區(qū)方法下，位于大鵬區(qū)、坪山區(qū)、龍華區(qū)、龍崗區(qū)和南山區(qū)的軌跡點(diǎn)查詢時(shí)延。查詢時(shí)延是指從提交查詢請(qǐng)求到返回查詢結(jié)果所消耗的時(shí)間。結(jié)果如圖1所示，在不同位置查詢，時(shí)延不同。在空間網(wǎng)格分區(qū)方式下，綜合平均時(shí)延為2.79 s。在時(shí)空網(wǎng)格分區(qū)方式下，綜合平均時(shí)延為2.33 s。
圖1 軌跡點(diǎn)查詢
測(cè)試在兩種分區(qū)方式下，子串查詢長(zhǎng)度分別為5，10，15，20，25個(gè)軌跡點(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í)延都隨著查詢子串長(zhǎng)度變長(zhǎng)而變長(zhǎng)。
圖2 子串查詢
測(cè)試在兩種分區(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ò)大而變長(zhǎng)。
圖3 區(qū)域查詢
5 結(jié)語
本文利用Spark平臺(tái)實(shí)現(xiàn)了基于3D R-Tree的出租車軌跡數(shù)據(jù)查詢，對(duì)比了空間網(wǎng)格和時(shí)空網(wǎng)格兩種分區(qū)方式。實(shí)驗(yàn)表明，在軌跡點(diǎn)查詢下，不同的位置查詢時(shí)延不同；在子串查詢下，查詢軌跡長(zhǎng)度越長(zhǎng)，查詢時(shí)延越長(zhǎng)；在區(qū)域查詢下，查詢的范圍越大，查詢時(shí)延越長(zhǎng)；用時(shí)空網(wǎng)格分區(qū)方法比用空間網(wǎng)格分區(qū)方法的查詢時(shí)延短。在下一步的工作中，本研究計(jì)劃在Spark streaming流式處理框架實(shí)現(xiàn)基于3D R-tree的流式軌跡數(shù)據(jù)查詢。
