吳 政，武鵬達(dá)，李成名

中國(guó)測(cè)繪科學(xué)研究院，北京 100830

時(shí)空索引是時(shí)空數(shù)據(jù)存儲(chǔ)和管理的關(guān)鍵技術(shù)之一[1-2]。在分布式NoSQL數(shù)據(jù)庫(kù)環(huán)境下，時(shí)空索引的研究可分為兩大類(lèi)：一類(lèi)是基于傳統(tǒng)的空間索引(QuadTree、R-Tree、Grid索引等)進(jìn)行分布式改進(jìn)或擴(kuò)展的索引方法[3-9]；另一類(lèi)是基于空間填充曲線(space filling curve，SFC)的索引方法(Z-Order，Hilbert,Google S2等)。SFC由于具有良好的集聚特性，可以更好地描述時(shí)空數(shù)據(jù)的空間連續(xù)特征[10-11]，近年來(lái)被廣泛應(yīng)用于時(shí)空索引領(lǐng)域。

文獻(xiàn)[12]提出了以GeoHash字符串標(biāo)識(shí)空間信息，并與時(shí)間屬性字符串交織編碼構(gòu)成索引鍵值的時(shí)空索引結(jié)構(gòu)；文獻(xiàn)[13]提出了基于R-Tree與Geohash編碼的空間索引機(jī)制；Google公司于2011年提出了一種四叉樹(shù)與Hlibert曲線相結(jié)合的S2空間數(shù)據(jù)索引方法[14-15]，可以實(shí)現(xiàn)多層級(jí)的空間要素的表達(dá)；關(guān)注度較高的開(kāi)源項(xiàng)目GeoMesa[16]提出了XZ-Ordering[17-18]時(shí)空索引方法(以下簡(jiǎn)稱(chēng)XZ3)，其基本思想是將四叉樹(shù)與Z-Order曲線相結(jié)合，將空間信息的GeoHash字符串與時(shí)間信息字符串交錯(cuò)來(lái)實(shí)現(xiàn)時(shí)空信息的編碼，并以一個(gè)隨機(jī)的二進(jìn)制編號(hào)作為行索引鍵，從而實(shí)現(xiàn)任意分辨率下空間信息的表達(dá)，并且查詢性能不會(huì)隨分辨率的提高而出現(xiàn)退化。

對(duì)等網(wǎng)絡(luò)(peer to peer，P2P)是一種去中心化架構(gòu)，具有高擴(kuò)展性、高可用性、大吞吐量等特性。Apache Cassandra數(shù)據(jù)庫(kù)[19-20]作為一種P2P網(wǎng)絡(luò)下的NoSQL數(shù)據(jù)庫(kù)，顯現(xiàn)出了對(duì)于動(dòng)態(tài)增長(zhǎng)的海量數(shù)據(jù)管理方面的較大優(yōu)勢(shì)，然而基于Cassandra進(jìn)行時(shí)空數(shù)據(jù)管理特別是對(duì)矢量數(shù)據(jù)管理的研究較少[21-22]。S2空間索引相對(duì)于XZ3索引可以更好地實(shí)現(xiàn)全球范圍內(nèi)矢量要素的多層級(jí)表達(dá)及對(duì)非點(diǎn)要素的連續(xù)性描述，然而現(xiàn)有索引方法應(yīng)用于P2P網(wǎng)絡(luò)時(shí)，仍存在以下難點(diǎn)問(wèn)題需要解決：①時(shí)空信息聯(lián)合索引問(wèn)題，現(xiàn)有索引多側(cè)重于空間索引的研究，如何兼顧時(shí)間查詢與空間查詢的效率是一個(gè)難點(diǎn)；②非點(diǎn)要素的合理表達(dá)問(wèn)題，對(duì)于線、面狀要素，其覆蓋的空間范圍差異大，查詢時(shí)既要考慮小范圍內(nèi)的精確快速查詢，也要兼顧大范圍的全覆蓋掃描，如何對(duì)非點(diǎn)要素進(jìn)行合理表達(dá)是第2個(gè)難點(diǎn)；③最優(yōu)時(shí)空層級(jí)確定問(wèn)題，時(shí)間粒度與分層級(jí)別直接影響到查詢的效率和準(zhǔn)確度，如何根據(jù)地理要素自身特征確定合理的索引級(jí)別(時(shí)空分辨率)是第3個(gè)難點(diǎn)。

綜上所述，本文在“去中心化”的對(duì)等網(wǎng)絡(luò)下，基于S2索引，提出一種自適應(yīng)層級(jí)的時(shí)空索引構(gòu)建方法，實(shí)現(xiàn)對(duì)時(shí)空數(shù)據(jù)的時(shí)空聯(lián)合查詢、合理表達(dá)以及高效檢索。

1 自適應(yīng)層級(jí)的時(shí)空索引原理

NoSQL數(shù)據(jù)庫(kù)中的時(shí)空索引本質(zhì)上是一種在Row Key中編碼時(shí)空信息的方式。本文基于S2空間索引，構(gòu)建一種自適應(yīng)層級(jí)時(shí)空索引方法?；舅悸窞椋菏紫炔捎梅至６取⒎謱蛹?jí)的方法對(duì)時(shí)空信息進(jìn)行聯(lián)合編碼；其次，依據(jù)地理要素空間分布方式對(duì)點(diǎn)及非點(diǎn)要素進(jìn)行時(shí)空表達(dá)；最后，提出時(shí)空最優(yōu)層級(jí)確定算法，并基于多層級(jí)時(shí)空索引樹(shù)構(gòu)建MLS3(multi-level sphere 3)時(shí)空索引。

1.1 時(shí)空信息聯(lián)合編碼

1.1.1 時(shí)間信息編碼

時(shí)間信息按照數(shù)據(jù)更新周期或者采樣頻率劃分為6級(jí)，時(shí)間粒度在“秒”與“年”之間逐級(jí)分布，標(biāo)記為gi(i=0,1,…，5)，如表1所示。

表1 時(shí)間信息編碼

定義Tbase為起算基點(diǎn)，Tcurrent為當(dāng)前時(shí)間至Tbase的毫秒數(shù)，即Tcurrent=T(g5)-Tbase，則以當(dāng)前時(shí)間對(duì)應(yīng)時(shí)間粒度gi的整數(shù)部分作為分區(qū)鍵，記為T(mén)partition(gi)，而排序鍵Tsort(gi)=Tcurrent-Tpartition(gi)，得到時(shí)間信息在Row Key中編碼如圖1所示。

圖1 Row Key中時(shí)間信息的表示Fig.1 Time information part in Row Key

1.1.2 空間信息編碼

依據(jù)S2索引思想，各個(gè)層級(jí)中的空間要素均可由對(duì)其形成包絡(luò)的一個(gè)和多個(gè)格網(wǎng)進(jìn)行標(biāo)識(shí)。如圖2所示，線要素(灰色粗實(shí)線)在第1層級(jí)L1的包絡(luò)Cell集合為(0,2,3)，在第2層級(jí)L2的包絡(luò)Cell集合為(00,02,03,22,23,30,31)，在第3層級(jí)L3的包絡(luò)Cell集合為(001,002,020,022,023,031,220,231,232,303,310,311)。

圖2 空間信息編碼Fig.2 Spatial information coding

本文對(duì)S2空間索引進(jìn)行擴(kuò)展，根據(jù)各個(gè)格網(wǎng)內(nèi)的地理要素空間分布疏密情況，對(duì)格網(wǎng)作進(jìn)一步剖分，從而將矢量數(shù)據(jù)空間信息表示為多層級(jí)的Hilbert編碼。假設(shè)某個(gè)要素所在層級(jí)為L(zhǎng)m—Ln(0≤m

圖3 Row Key中空間信息的表示Fig.3 Spatial information part in Row Key

1.1.3 唯一標(biāo)識(shí)信息編碼

采用要素唯一標(biāo)識(shí)(feature identification，F(xiàn)ID)對(duì)同一格網(wǎng)內(nèi)的多個(gè)要素進(jìn)行區(qū)分，基本思路為采用Twitter的SnowFlake算法，按照ID生成的時(shí)間自增排序。FID編碼包括5部分：標(biāo)識(shí)位位于最高位，表示符號(hào)位；時(shí)間戳為第2部分，精確到毫秒級(jí)；對(duì)等網(wǎng)路中節(jié)點(diǎn)集群標(biāo)識(shí)(cluster identification，CID)和集群中節(jié)點(diǎn)標(biāo)識(shí)(node identification，NID)分別為第3和第4部分；最后部分由12位的計(jì)數(shù)順序號(hào)構(gòu)成，支持每個(gè)機(jī)器節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號(hào)，如圖4所示。

圖4 Row Key中FID的表示Fig.4 FID in Row Key

1.1.4 Row Key編碼組織方式

整合上述時(shí)間、空間和唯一標(biāo)識(shí)信息編碼，形成時(shí)空信息聯(lián)合編碼的Row Key值。組織方式為：①分區(qū)鍵采用“較大時(shí)間粒度+父級(jí)空間網(wǎng)格標(biāo)識(shí)”聯(lián)合確定，以保證時(shí)空中具有相鄰關(guān)系的要素分布在同一個(gè)或相鄰的邏輯分區(qū)；②排序鍵組織方式同分區(qū)鍵類(lèi)似，采用“較小時(shí)間粒度+子級(jí)空間網(wǎng)格標(biāo)識(shí)+唯一標(biāo)識(shí)”進(jìn)行表示。假設(shè)時(shí)間粒度為i級(jí)，在第j層級(jí)的要素，空間網(wǎng)格的父級(jí)定為m級(jí)，n級(jí)為其進(jìn)一步剖分后的子一級(jí)，則其時(shí)空編碼如圖5所示。

圖5 Row Key內(nèi)編碼組織方式Fig.5 Design of Row Key

1.2 索引編碼

1.2.1 點(diǎn)要素的時(shí)空表達(dá)

對(duì)于點(diǎn)要素，本文采用其所在某一級(jí)網(wǎng)格的中心點(diǎn)近似表示。假設(shè)其分區(qū)鍵為L(zhǎng)m(0≤m<30)，排序鍵為L(zhǎng)n(m≤n<30)，按照上文所述Row Key設(shè)計(jì)原則，其分區(qū)鍵由在時(shí)間粒度g(i)下的時(shí)間值以及空間網(wǎng)格在m級(jí)涵蓋該點(diǎn)的編碼表示，分區(qū)內(nèi)排序鍵由時(shí)間信息中去除分區(qū)鍵時(shí)間值的部分、空間信息在第Ln級(jí)的編碼以及要素唯一標(biāo)識(shí)表示。

以某收費(fèi)站POI興趣點(diǎn)為例，假設(shè)其更新時(shí)間粒度為月份，圖層空間范圍所在層級(jí)為9～10級(jí)，則該P(yáng)OI的分區(qū)鍵由月時(shí)間粒度“2016-02”和空間信息在9級(jí)的Cell ID(35f0ec)組成；分區(qū)內(nèi)排序鍵由時(shí)間戳(01 13:00:00)、空間信息在10級(jí)的Cell ID(35f0eb0)以及要素唯一ID組成，如圖6所示。

圖6 點(diǎn)要素的Row Key表示Fig.6 Row Key of point element

1.2.2 非點(diǎn)要素的時(shí)空表達(dá)

對(duì)于非點(diǎn)要素(線要素和面要素)，一個(gè)要素的空間信息可能由多個(gè)空間網(wǎng)格表示，即一個(gè)要素對(duì)應(yīng)多個(gè)鍵值。分區(qū)鍵及分區(qū)內(nèi)排序鍵組織形式同點(diǎn)要素一致。

以道路線要素為例，假設(shè)其更新時(shí)間粒度為月份，圖層空間范圍所在層級(jí)為4～7級(jí)，則該道路的分區(qū)鍵由月時(shí)間粒度“2008-02”和空間信息在4級(jí)的Cell ID(35b)組成；分區(qū)內(nèi)排序鍵由時(shí)間戳(01 12:00:00)、空間信息在6至7級(jí)的Cell ID(35acc、35ac9b、35accf等)以及要素唯一ID組成，如圖7所示。

圖7 一個(gè)線要素的Row Key表示Fig.7 Row Key of an line element

2 時(shí)空索引構(gòu)建算法

對(duì)于矢量數(shù)據(jù)時(shí)空索引，根據(jù)其時(shí)空特征自適應(yīng)確定最優(yōu)索引級(jí)別一直是難點(diǎn)所在。本文構(gòu)建MLS3索引，通過(guò)地理實(shí)體時(shí)間劃分間隔及空間密度特征確定最優(yōu)索引層級(jí)?；舅枷霝椋孩僮顑?yōu)時(shí)間層級(jí)。若T時(shí)間內(nèi)，在指定的采樣間隔下多個(gè)數(shù)據(jù)獲取源產(chǎn)生的數(shù)據(jù)量為P2P網(wǎng)絡(luò)下數(shù)據(jù)庫(kù)內(nèi)最優(yōu)分區(qū)數(shù)據(jù)塊大小，則表1中涵蓋時(shí)間范圍T的最小時(shí)間粒度為最優(yōu)時(shí)間層級(jí)。②最優(yōu)空間層級(jí)。設(shè)定一個(gè)初始格網(wǎng)劃分?jǐn)?shù)量閾值，若在第N層級(jí)上，圖層范圍內(nèi)的地物被近似該閾值的格網(wǎng)全覆蓋，則N為空間最優(yōu)初始層級(jí)，進(jìn)而根據(jù)N級(jí)上每個(gè)格網(wǎng)內(nèi)的要素稀疏程度對(duì)格網(wǎng)做多層級(jí)剖分，獲取該圖層的最優(yōu)空間層級(jí)。

2.1 時(shí)間粒度確定

對(duì)于靜態(tài)離散的時(shí)空數(shù)據(jù)，采用數(shù)據(jù)的更新周期作為分區(qū)鍵的時(shí)間粒度，比如年份或月份；對(duì)于動(dòng)態(tài)連續(xù)的時(shí)空數(shù)據(jù)，其時(shí)間粒度根據(jù)其采樣頻率及數(shù)據(jù)大小設(shè)定。以Cassandra數(shù)據(jù)庫(kù)為例，Cassandra數(shù)據(jù)庫(kù)單個(gè)分區(qū)數(shù)據(jù)塊超過(guò)100 MB后，在進(jìn)行壓縮、集群擴(kuò)容等操作時(shí)會(huì)對(duì)Cassandra帶來(lái)較大的Garbage Collection(GC)壓力，數(shù)據(jù)庫(kù)性能下降，為此本文以數(shù)據(jù)庫(kù)內(nèi)最優(yōu)分區(qū)數(shù)據(jù)塊大小作為約束計(jì)算最優(yōu)時(shí)間粒度。定義時(shí)間間隔(時(shí)間粒度)總長(zhǎng)度為T(mén)(ms)，采樣間隔為I(ms)，傳感器個(gè)數(shù)為N(個(gè))，存儲(chǔ)單條記錄所需的空間大小為S(MB)，則滿足式(1)的時(shí)間間隔T為最優(yōu)時(shí)間粒度

(1)

2.2 空間格網(wǎng)層級(jí)確定

最優(yōu)空間格網(wǎng)層級(jí)的確定需要顧及要素的分布、存儲(chǔ)代價(jià)以及查詢時(shí)間代價(jià)。假設(shè)Ecell表示一個(gè)單元格(cell)中所包含或相交的要素集合，Equery表示查詢范圍內(nèi)所包含或相交的要素集合。

定義1：有效查詢單元格：是指與查詢范圍相交或包含在查詢范圍內(nèi)的Cell并且其滿足Ecell∩Equery≠?。

定義2：無(wú)效查詢單元格：是指與查詢范圍相交的Cell并且其滿足Ecell∩Equery=?。

第k次空間查詢所需的查詢時(shí)間Tk主要由查詢m個(gè)有效單元格和n個(gè)無(wú)效查詢單元格的耗時(shí)組成。由于NoSQL數(shù)據(jù)庫(kù)查詢某一區(qū)域數(shù)據(jù)耗時(shí)主要由數(shù)據(jù)量決定，因此，可近似認(rèn)為查詢某個(gè)cell耗時(shí)由其內(nèi)要素個(gè)數(shù)和查詢單要素耗時(shí)決定；進(jìn)一步假設(shè)在同一層級(jí)l查詢單個(gè)要素所需時(shí)間相同，表示為ΔTl，則查詢時(shí)間Tk可表達(dá)為式(2)

(2)

則最小化K次查詢所需要的總耗時(shí)可以表示為式(3)

(3)

假設(shè)某一地理范圍的空間索引層級(jí)集合為L(zhǎng)，且在L中各cell內(nèi)要素?cái)?shù)量不超過(guò)某一閾值，則查詢單個(gè)cell的時(shí)間與其內(nèi)要素?cái)?shù)量呈線性關(guān)系，式(3)可進(jìn)一步表示為

(4)

(5)

則最優(yōu)空間索引層級(jí)確定問(wèn)題簡(jiǎn)化為選取合適的初始層級(jí)N1和層級(jí)數(shù)量thresh，以盡可能遍歷最少的cell數(shù)量達(dá)到查詢的覆蓋范圍，從而確?？偛樵儠r(shí)間最少。

2.3 多層級(jí)時(shí)空索引樹(shù)

根據(jù)上述最優(yōu)時(shí)空索引層級(jí)確定策略，本文建立多層級(jí)時(shí)空索引樹(shù)(multi-level tree)，如圖8所示，其中1級(jí)節(jié)點(diǎn)為粒度較大的時(shí)間信息節(jié)點(diǎn)，對(duì)應(yīng)Row Key中分區(qū)鍵中的時(shí)間信息編碼，由Ti節(jié)點(diǎn)表示；2級(jí)節(jié)點(diǎn)為cell級(jí)別，對(duì)應(yīng)分區(qū)鍵中的空間信息編碼，由Ci節(jié)點(diǎn)表示；第3級(jí)節(jié)點(diǎn)為粒度較小的時(shí)間節(jié)點(diǎn)，對(duì)應(yīng)分區(qū)排序鍵的時(shí)間信息編碼，由Ti+1節(jié)點(diǎn)表示。此3級(jí)為初始劃分，其他層級(jí)可根據(jù)數(shù)據(jù)時(shí)空分布特征自適應(yīng)劃分，由Ci+1，2，…節(jié)點(diǎn)表示，對(duì)應(yīng)分區(qū)排序鍵的空間信息編碼。

圖8 多層級(jí)時(shí)空索引樹(shù)Fig.8 Multi-level temporal-spatial tree

基于時(shí)空層級(jí)確定算法及多層級(jí)時(shí)空索引樹(shù)的組織方式，本文構(gòu)建MLS3索引，流程如圖9所示。

在MLS3算法構(gòu)建multi-level tree的過(guò)程中，節(jié)點(diǎn)的剖分操作僅允許在葉子節(jié)點(diǎn)發(fā)生，流程如圖10所示。

該樹(shù)作為索引策略存儲(chǔ)在相應(yīng)的元數(shù)據(jù)中，用于查詢時(shí)進(jìn)行查詢范圍劃分為若干cell區(qū)域查詢的依據(jù)。遍歷查找時(shí)間復(fù)雜度O(n)，n為查詢范圍內(nèi)cell數(shù)量。

3 試驗(yàn)與分析

3.1 試驗(yàn)數(shù)據(jù)與試驗(yàn)環(huán)境

為了驗(yàn)證本文所提時(shí)空索引算法MLS3的有效性和合理性，將本文索引算法與XZ3時(shí)空索引算法在相同數(shù)據(jù)集、相同測(cè)試環(huán)境下進(jìn)行比較。模擬實(shí)際生產(chǎn)環(huán)境搭建Cassandra集群，采用P2P架構(gòu)，共5個(gè)數(shù)據(jù)庫(kù)節(jié)點(diǎn)，冗余備份因子為2，單節(jié)點(diǎn)的性能為：IBM X3850服務(wù)器，內(nèi)存大小16 GB、CPU共16核，主頻為2.294 GHz，存儲(chǔ)空間120 GB。試驗(yàn)數(shù)據(jù)集采用微軟亞洲研究院提供的2008年2月2日至2月8日北京市10 357輛出租車(chē)的GPS軌跡(點(diǎn)要素)數(shù)據(jù)(TDrive Dataset)[23-24]，約1500萬(wàn)條數(shù)據(jù)，里程約900×106km，以及Open Street Map(OSM)提供的北京市2017年11月至2018年3月共5個(gè)月份的數(shù)據(jù)，包括建筑物(面要素)227 258條、公路(線要素)309 314條(OSM DataSet)[25-26]。

圖9 多層級(jí)時(shí)空索引樹(shù)構(gòu)建流程Fig.9 Flowchart of multi-level temporal-spatial tree construction

為了測(cè)試不同并發(fā)訪問(wèn)的應(yīng)用場(chǎng)景，本文對(duì)上述兩個(gè)數(shù)據(jù)集分別生成時(shí)空查詢窗口：①TDrive數(shù)據(jù)集。隨機(jī)選擇2008年2月2日至2008年2月8日早7時(shí)至晚9時(shí)時(shí)間段內(nèi)的200個(gè)時(shí)間種子點(diǎn)，時(shí)間窗口大小限制為≤2 h，空間查詢窗口為北京市行政區(qū)劃內(nèi)隨機(jī)生成的200個(gè)矩形窗口，時(shí)間窗口及空間矩形隨機(jī)組合構(gòu)成200個(gè)時(shí)空查詢窗口。②OSM數(shù)據(jù)集。時(shí)空查詢窗口生成方式與TDrive數(shù)據(jù)集類(lèi)似，不再贅述。時(shí)空查詢窗口如圖11所示。

圖10 葉結(jié)點(diǎn)剖分流程(流程B)Fig.10 Flowchart of leaf node splitting

3.2 層級(jí)劃分合理性驗(yàn)證

為驗(yàn)證層級(jí)劃分算法的合理性，本文選取TDrive Dateset進(jìn)行試驗(yàn)驗(yàn)證。對(duì)1500多萬(wàn)條GPS數(shù)據(jù)進(jìn)行隨機(jī)采樣，采樣率為20%，cell剖分閾值splitthresh設(shè)為樣本的30%。由MLS3算法得到該數(shù)據(jù)集最適宜初始劃分層級(jí)為9級(jí)，樹(shù)深度閾值為2，即多層級(jí)的劃分范圍為9～11級(jí)。

為驗(yàn)證上述索引層級(jí)的合理性，本文在同一數(shù)據(jù)集下，設(shè)置6、7、8、9、10、11、12等7個(gè)不同層級(jí)作為初始層級(jí)，并以200次時(shí)空查詢平均耗時(shí)最低的層級(jí)作為7個(gè)層次中的最優(yōu)層次劃分。試驗(yàn)結(jié)果如圖12所示，可以發(fā)現(xiàn)隨著索初始層級(jí)的增加，查詢平均耗時(shí)先降后升，從6級(jí)到9級(jí)平均耗時(shí)逐步降低，在9級(jí)時(shí)達(dá)到最低耗時(shí)117.17 ms；但是從9級(jí)到12級(jí)，平均耗時(shí)逐步上升，在12級(jí)時(shí)達(dá)到了3520 ms。

統(tǒng)計(jì)本文方法在確定GPS軌跡數(shù)據(jù)、公路數(shù)據(jù)及建筑物數(shù)據(jù)最優(yōu)索引層級(jí)的耗時(shí)，分別為1601 ms、314 ms和182 ms，各占索引構(gòu)建總時(shí)間的11%、13%和9%。此外，目前該算法已經(jīng)應(yīng)用到智慧臨沂、智慧淄博等時(shí)空信息云平臺(tái)建設(shè)項(xiàng)目中，經(jīng)大量實(shí)際生產(chǎn)數(shù)據(jù)驗(yàn)證，一級(jí)cell的數(shù)據(jù)量閾值設(shè)定為200個(gè)為宜，由此得到國(guó)家級(jí)圖層(如中國(guó)范圍)最適宜劃分層級(jí)為4～5級(jí)，省級(jí)范圍圖層(如山東省范圍)最適宜劃分層級(jí)為7～8級(jí)，市級(jí)范圍圖層(如北京市范圍)最適宜劃分層級(jí)為9～10級(jí)。

圖11 200個(gè)時(shí)空查詢窗口Fig.11 200 query windows：TDrive and OSM data set spatio-temporal query windows

圖12 不同劃分層級(jí)參數(shù)平均耗時(shí)Fig.12 Average time-consuming at different levels

3.3 索引性能對(duì)比分析

因S2索引不包含時(shí)間索引，故選擇XZ3時(shí)空索引算法作為對(duì)比算法，從索引查詢效率、構(gòu)建效率和空間利用率3個(gè)維度檢驗(yàn)本文算法的性能。

3.3.1 查詢效率

XZ3時(shí)空索引默認(rèn)采用單線程、page size為1，故本文首先對(duì)默認(rèn)參數(shù)條件下兩種算法的性能進(jìn)行比較。試驗(yàn)數(shù)據(jù)為T(mén)Drive DataSet和OSM DataSet兩個(gè)數(shù)據(jù)集，設(shè)置1、5、10、15、20、25、30、35和40等多組并發(fā)查詢?cè)L問(wèn)粒度。試驗(yàn)結(jié)果如表2所示。

從整體上看，隨著并發(fā)查詢?cè)L問(wèn)任務(wù)的增加，MLS3算法與XZ3索引算法查詢耗時(shí)均有所增加，但MLS3算法的耗時(shí)均低于XZ3算法。如表2所示，對(duì)于GPS軌跡點(diǎn)數(shù)據(jù)，XZ3算法的查詢耗時(shí)為本文算法查詢耗時(shí)的1.7～3.4倍；對(duì)于線、面等非點(diǎn)要素，MLS3算法查詢效率提升更為明顯，XZ3算法的查詢耗時(shí)分別為本文算法查詢耗時(shí)的1.2～5.0倍和4～7倍?？傮w來(lái)說(shuō)，在相同試驗(yàn)參數(shù)設(shè)置下，本文算法耗時(shí)約為XZ3算法的1/7～1/2，表明本文提出的顧及數(shù)據(jù)分布特征的MLS3算法能夠保證查詢范圍盡可能限定在有效的cell區(qū)域內(nèi)，有效緩解了高并發(fā)條件下的復(fù)雜時(shí)空查詢操作的壓力。

表2 在不同數(shù)量任務(wù)并發(fā)下平均查詢耗時(shí)對(duì)比

同時(shí)，調(diào)優(yōu)本文索引方法參數(shù)與XZ3作進(jìn)一步對(duì)比分析。MLS3采用5線程，page size為1024，XZ3采用GeoMesa提供的默認(rèn)參數(shù)，其試驗(yàn)效果如圖13—圖15所示。可以看出，對(duì)于點(diǎn)、線、面3種類(lèi)型的數(shù)據(jù)，XZ3查詢耗時(shí)均有較大浮動(dòng)，其原因不僅與查詢條件所涵蓋的數(shù)據(jù)量有關(guān)，同時(shí)也與索引算法所采用的SFC有關(guān)。XZ3索引基于Z-Order曲線構(gòu)建，該曲線存在編碼相鄰的數(shù)據(jù)其空間關(guān)系會(huì)發(fā)生跳變的特點(diǎn)，而本文索引算法采用Hilbert曲線進(jìn)行空間信息編碼表示，可以保證空間相鄰的要素其編碼也是連續(xù)的，從而確保查詢區(qū)域中數(shù)據(jù)最大程度的位于相同分區(qū)，減少了分區(qū)掃描時(shí)無(wú)效數(shù)據(jù)的查詢和比較，縮短了查詢時(shí)間。對(duì)于GPS軌跡點(diǎn)數(shù)據(jù)，XZ3算法在20～10 134 ms間浮動(dòng)，而MLS3算法在2000 ms以內(nèi)浮動(dòng)(圖13)；對(duì)于路網(wǎng)數(shù)據(jù)，XZ3算法在1201～3079 ms間浮動(dòng)，而MLS3算法在630 ms以內(nèi)浮動(dòng)(圖14)；對(duì)于建筑物面數(shù)據(jù)，XZ3算法在1000～3500 ms間浮動(dòng)，而MLS3算法在500 ms以內(nèi)浮動(dòng)(圖15)?？傮w來(lái)看，MLS3算法在采用多線程和適當(dāng)page size情況下，性能有大幅度提升，查詢效率提升4～7倍左右，并且查詢耗時(shí)穩(wěn)定，更適合應(yīng)用于實(shí)際場(chǎng)景。

圖13 TDrive Data Set GPS點(diǎn)圖層單次查詢耗時(shí)對(duì)比Fig.13 Query time-consuming comparison of GPS points in TDrive data set

圖14 OSM Data Set建筑物圖層單次查詢耗時(shí)對(duì)比Fig.14 Query time-consuming comparison of road layer in OSM data set

圖15 OSM Data Set建筑物圖層單次查詢耗時(shí)對(duì)比Fig.15 Query time-consuming comparison of building layer in OSM data set

3.3.2 索引構(gòu)建效率和空間利用率

以索引生成時(shí)間作為構(gòu)建效率，以索引數(shù)據(jù)量大小占其對(duì)應(yīng)矢量數(shù)據(jù)大小的比例作為空間利用率，對(duì)兩種索引方法的性能作進(jìn)一步比較，各項(xiàng)指標(biāo)值如表3所示。可以發(fā)現(xiàn)，對(duì)于點(diǎn)、線、面3種要素，兩種索引方法的空間利用率基本一致，本文方法所占存儲(chǔ)比例略高，較XZ3索引分別增加了7.49%、1.54%和3.02%。然而兩種索引方法的數(shù)據(jù)量大小均占總存儲(chǔ)空間的0.5%左右，相較于現(xiàn)有硬件存儲(chǔ)環(huán)境，空間利用率在可接受范圍。此外，在索引構(gòu)建效率方面，本文方法構(gòu)建耗時(shí)相對(duì)高于XZ3，增加的時(shí)間與數(shù)據(jù)要素?cái)?shù)量呈正相關(guān)關(guān)系。這是因?yàn)閄Z3僅僅計(jì)算Row Key值，而MLS3需要構(gòu)建多層級(jí)索引樹(shù)，同時(shí)進(jìn)行索引級(jí)別的自動(dòng)劃分和選擇，然而，兩種索引方法構(gòu)建過(guò)程所需時(shí)間不超過(guò)數(shù)據(jù)導(dǎo)入總時(shí)間的1/10。

表3 索引空間利用率及構(gòu)建效率對(duì)比

Tab.3 Comparison of index space utilization rate and construction efficiency

指標(biāo)索引方法TDrive taxi(點(diǎn))OSM roads(線)OSM buildings(面)空間利用率/(%)XZ331.147.3710.68MLS338.638.9113.70構(gòu)建效率/sXZ36332MLS31472319

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)時(shí)空索引存在的時(shí)間、空間查詢難以同時(shí)顧及,以及非點(diǎn)要素?zé)o法有效表達(dá)且最優(yōu)索引層級(jí)難以確定等問(wèn)題，本文通過(guò)地理實(shí)體時(shí)間粒度及空間密度等特征確定最優(yōu)索引層級(jí)，并構(gòu)建了時(shí)空索引MLS3。大量實(shí)際數(shù)據(jù)驗(yàn)證表明，在查詢效率方面，MLS3索引的查詢效率可提升4～7倍。此外，以Hilbert填充曲線為核心的MLS3索引相較于以Z-Order填充曲線為核心的XZ3索引能夠更好地描述時(shí)空數(shù)據(jù)的連續(xù)性，表現(xiàn)出了更加穩(wěn)定的查詢性能，對(duì)于海量多尺度數(shù)據(jù)的分布式存儲(chǔ)管理具有較強(qiáng)的適用性。然而為了提高查詢效率及穩(wěn)定性，本文犧牲了部分構(gòu)建時(shí)間及空間利用率，但相較于現(xiàn)有硬件存儲(chǔ)環(huán)境，增加程度在可接受范圍。下一步將優(yōu)化構(gòu)建效率及空間利用率，并研究擴(kuò)展該算法至主從架構(gòu)的分布式NoSQL數(shù)據(jù)庫(kù)中。