對等網絡下自適應層級的矢量數據時空索引構建方法

吳 政，武鵬達，李成名

中國測繪科學研究院，北京 100830

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

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

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

綜上所述，本文在“去中心化”的對等網絡下，基于S2索引，提出一種自適應層級的時空索引構建方法，實現對時空數據的時空聯合查詢、合理表達以及高效檢索。

1 自適應層級的時空索引原理

NoSQL數據庫中的時空索引本質上是一種在Row Key中編碼時空信息的方式。本文基于S2空間索引，構建一種自適應層級時空索引方法。基本思路為：首先采用分粒度、分層級的方法對時空信息進行聯合編碼；其次，依據地理要素空間分布方式對點及非點要素進行時空表達；最后，提出時空最優層級確定算法，并基于多層級時空索引樹構建MLS3(multi-level sphere 3)時空索引。

1.1 時空信息聯合編碼

1.1.1 時間信息編碼

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

表1 時間信息編碼

定義Tbase為起算基點，Tcurrent為當前時間至Tbase的毫秒數，即Tcurrent=T(g5)-Tbase，則以當前時間對應時間粒度gi的整數部分作為分區鍵，記為Tpartition(gi)，而排序鍵Tsort(gi)=Tcurrent-Tpartition(gi)，得到時間信息在Row Key中編碼如圖1所示。

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

1.1.2 空間信息編碼

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

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

本文對S2空間索引進行擴展，根據各個格網內的地理要素空間分布疏密情況，對格網作進一步剖分，從而將矢量數據空間信息表示為多層級的Hilbert編碼。假設某個要素所在層級為Lm—Ln(0≤m

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

1.1.3 唯一標識信息編碼

采用要素唯一標識(feature identification，FID)對同一格網內的多個要素進行區分，基本思路為采用Twitter的SnowFlake算法，按照ID生成的時間自增排序。FID編碼包括5部分：標識位位于最高位，表示符號位；時間戳為第2部分，精確到毫秒級；對等網路中節點集群標識(cluster identification，CID)和集群中節點標識(node identification，NID)分別為第3和第4部分；最后部分由12位的計數順序號構成，支持每個機器節點每毫秒產生4096個ID序號，如圖4所示。

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

1.1.4 Row Key編碼組織方式

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

圖5 Row Key內編碼組織方式Fig.5 Design of Row Key

1.2 索引編碼

1.2.1 點要素的時空表達

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

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

圖6 點要素的Row Key表示Fig.6 Row Key of point element

1.2.2 非點要素的時空表達

對于非點要素(線要素和面要素)，一個要素的空間信息可能由多個空間網格表示，即一個要素對應多個鍵值。分區鍵及分區內排序鍵組織形式同點要素一致。

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

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

2 時空索引構建算法

對于矢量數據時空索引，根據其時空特征自適應確定最優索引級別一直是難點所在。本文構建MLS3索引，通過地理實體時間劃分間隔及空間密度特征確定最優索引層級。基本思想為：①最優時間層級。若T時間內，在指定的采樣間隔下多個數據獲取源產生的數據量為P2P網絡下數據庫內最優分區數據塊大小，則表1中涵蓋時間范圍T的最小時間粒度為最優時間層級。②最優空間層級。設定一個初始格網劃分數量閾值，若在第N層級上，圖層范圍內的地物被近似該閾值的格網全覆蓋，則N為空間最優初始層級，進而根據N級上每個格網內的要素稀疏程度對格網做多層級剖分，獲取該圖層的最優空間層級。

2.1 時間粒度確定

對于靜態離散的時空數據，采用數據的更新周期作為分區鍵的時間粒度，比如年份或月份；對于動態連續的時空數據，其時間粒度根據其采樣頻率及數據大小設定。以Cassandra數據庫為例，Cassandra數據庫單個分區數據塊超過100 MB后，在進行壓縮、集群擴容等操作時會對Cassandra帶來較大的Garbage Collection(GC)壓力，數據庫性能下降，為此本文以數據庫內最優分區數據塊大小作為約束計算最優時間粒度。定義時間間隔(時間粒度)總長度為T(ms)，采樣間隔為I(ms)，傳感器個數為N(個)，存儲單條記錄所需的空間大小為S(MB)，則滿足式(1)的時間間隔T為最優時間粒度

(1)

2.2 空間格網層級確定

最優空間格網層級的確定需要顧及要素的分布、存儲代價以及查詢時間代價。假設Ecell表示一個單元格(cell)中所包含或相交的要素集合，Equery表示查詢范圍內所包含或相交的要素集合。

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

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

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

(2)

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

(3)

假設某一地理范圍的空間索引層級集合為L，且在L中各cell內要素數量不超過某一閾值，則查詢單個cell的時間與其內要素數量呈線性關系，式(3)可進一步表示為

(4)

(5)

則最優空間索引層級確定問題簡化為選取合適的初始層級N1和層級數量thresh，以盡可能遍歷最少的cell數量達到查詢的覆蓋范圍，從而確保總查詢時間最少。

2.3 多層級時空索引樹

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

圖8 多層級時空索引樹Fig.8 Multi-level temporal-spatial tree

基于時空層級確定算法及多層級時空索引樹的組織方式，本文構建MLS3索引，流程如圖9所示。

在MLS3算法構建multi-level tree的過程中，節點的剖分操作僅允許在葉子節點發生，流程如圖10所示。

該樹作為索引策略存儲在相應的元數據中，用于查詢時進行查詢范圍劃分為若干cell區域查詢的依據。遍歷查找時間復雜度O(n)，n為查詢范圍內cell數量。

3 試驗與分析

3.1 試驗數據與試驗環境

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

圖9 多層級時空索引樹構建流程Fig.9 Flowchart of multi-level temporal-spatial tree construction

為了測試不同并發訪問的應用場景，本文對上述兩個數據集分別生成時空查詢窗口：①TDrive數據集。隨機選擇2008年2月2日至2008年2月8日早7時至晚9時時間段內的200個時間種子點，時間窗口大小限制為≤2 h，空間查詢窗口為北京市行政區劃內隨機生成的200個矩形窗口，時間窗口及空間矩形隨機組合構成200個時空查詢窗口。②OSM數據集。時空查詢窗口生成方式與TDrive數據集類似，不再贅述。時空查詢窗口如圖11所示。

圖10 葉結點剖分流程(流程B)Fig.10 Flowchart of leaf node splitting

3.2 層級劃分合理性驗證

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

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

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

圖11 200個時空查詢窗口Fig.11 200 query windows：TDrive and OSM data set spatio-temporal query windows

圖12 不同劃分層級參數平均耗時Fig.12 Average time-consuming at different levels

3.3 索引性能對比分析

因S2索引不包含時間索引，故選擇XZ3時空索引算法作為對比算法，從索引查詢效率、構建效率和空間利用率3個維度檢驗本文算法的性能。

3.3.1 查詢效率

XZ3時空索引默認采用單線程、page size為1，故本文首先對默認參數條件下兩種算法的性能進行比較。試驗數據為TDrive DataSet和OSM DataSet兩個數據集，設置1、5、10、15、20、25、30、35和40等多組并發查詢訪問粒度。試驗結果如表2所示。

從整體上看，隨著并發查詢訪問任務的增加，MLS3算法與XZ3索引算法查詢耗時均有所增加，但MLS3算法的耗時均低于XZ3算法。如表2所示，對于GPS軌跡點數據，XZ3算法的查詢耗時為本文算法查詢耗時的1.7～3.4倍；對于線、面等非點要素，MLS3算法查詢效率提升更為明顯，XZ3算法的查詢耗時分別為本文算法查詢耗時的1.2～5.0倍和4～7倍。總體來說，在相同試驗參數設置下，本文算法耗時約為XZ3算法的1/7～1/2，表明本文提出的顧及數據分布特征的MLS3算法能夠保證查詢范圍盡可能限定在有效的cell區域內，有效緩解了高并發條件下的復雜時空查詢操作的壓力。

表2 在不同數量任務并發下平均查詢耗時對比

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

圖13 TDrive Data Set GPS點圖層單次查詢耗時對比Fig.13 Query time-consuming comparison of GPS points in TDrive data set

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

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

3.3.2 索引構建效率和空間利用率

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

表3 索引空間利用率及構建效率對比

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

指標索引方法TDrive taxi(點)OSM roads(線)OSM buildings(面)空間利用率/(%)XZ331.147.3710.68MLS338.638.9113.70構建效率/sXZ36332MLS31472319

4 結束語

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