基于Hilbert-R樹分級索引的時空查詢算法

侯海耀，錢育蓉，英昌甜,2，張 晗，盧學(xué)遠(yuǎn)，趙 燚

(1.新疆大學(xué) 軟件學(xué)院，烏魯木齊830008； 2.新疆大學(xué) 電氣工程學(xué)科博士后流動站，烏魯木齊 830046；3.新疆大學(xué) 信息科學(xué)與工程學(xué)院， 烏魯木齊 830046)(*通信作者電子郵箱qyr@xju.edu.cn)

0 引言

矢量時空數(shù)據(jù)高效組織管理是空間數(shù)據(jù)應(yīng)用的關(guān)鍵技術(shù)，空間索引是實現(xiàn)矢量時空數(shù)據(jù)高效檢索的關(guān)鍵[1-3]。空間、時間、屬性作為時空大數(shù)據(jù)的三個基本特征[4]，如何描述和表達(dá)空間實體及其相互關(guān)系的時空變化，成為亟待解決的熱點問題。

近年來，樹形空間索引技術(shù)結(jié)合聚類技術(shù)來探討空間索引技術(shù)的研究成為熱門，對空間數(shù)據(jù)集進(jìn)行有效聚類，其結(jié)果對構(gòu)造高效的空間索引具有很大幫助[5]，但從時空查詢角度出發(fā)，同時考慮所查詢數(shù)據(jù)的時間維特征及各空間要素合理組織的研究較少，還不能很好地滿足時空應(yīng)用中對時空高效查詢的需求。文獻(xiàn)[6-8]側(cè)重從空間數(shù)據(jù)分布的特點出發(fā)，采用聚類算法與R樹結(jié)合構(gòu)建索引，提高了空間查找效率；文獻(xiàn)[9]提出基于Redis的緩存敏感R+樹(Cache Conscious R+Tree，CCR+)，其查詢效率較Oracle 10g的管理系統(tǒng)有較大的提升，但這些研究均未考慮對時間維建立索引。

基于以上問題，本文利用Hilbert曲線較為穩(wěn)定的離散度分布特點[10]，分割并編碼空間要素；利用動態(tài)確定K值的聚類算法，將聚類結(jié)果參與到Hilbert-R樹構(gòu)建當(dāng)中，對矢量時空數(shù)據(jù)采用Redis豐富的數(shù)據(jù)結(jié)構(gòu)進(jìn)行分層組織存儲；結(jié)合時間和聚類結(jié)果分層結(jié)構(gòu)建立分級索引機制。在此基礎(chǔ)上，進(jìn)行數(shù)據(jù)密集型測試、時空范圍查詢及目標(biāo)矢量對象查詢，在真實數(shù)據(jù)集上進(jìn)行，結(jié)果表明，提出的時間結(jié)合聚類分層組織存儲及分級索引機制在時空查詢性能方面較CCR+樹有顯著提升。

1 基礎(chǔ)建模

1.1 時空數(shù)據(jù)建模

時空數(shù)據(jù)是用來描述現(xiàn)實世界中空間實體及各實體間隨時間發(fā)展變化的過程和規(guī)律，它是描述矢量數(shù)據(jù)組織和設(shè)計空間數(shù)據(jù)庫的基礎(chǔ)[11]。本文參照國際標(biāo)準(zhǔn)化組織(Open GIS Consortium，OGC)制定的簡單要素規(guī)范對矢量時空數(shù)據(jù)進(jìn)行組織。每個時空要素有以下重要特征：

1)空間特征。指實際地物的幾何特征(如形狀、大小和位置)，以及各地物間的位置關(guān)系，通常用坐標(biāo)(x,y)表示經(jīng)緯度。

2)時間特征。通常指時空數(shù)據(jù)的空間特征和屬性特征隨時間而變化，本文數(shù)據(jù)集中的時間指采集該時空要素的時刻。

3)屬性特征?？臻g實體的類別和屬性。

基于以上特征，對時空要素可表示為[x,y,t,attrs]，其中：x、y分別表示要素橫、縱坐標(biāo)，采用經(jīng)、緯度值代替；t表示采集該要素的時間；attrs表示時空要素的屬性。

1.2 時空數(shù)據(jù)編碼

本文對時空數(shù)據(jù)編碼采用Hilbert曲線，其分形技術(shù)將多維空間區(qū)域等分為眾多網(wǎng)格，并映射為一維區(qū)間，作為Peano族空間填充曲線家族中的分支之一，相對于Z-Order填充曲線，具有較優(yōu)的空間聚類效果[12]。Hilbert曲線對空間相鄰近特征的區(qū)域能夠較好地表達(dá)，即在空間聯(lián)系密切且空間幾何距離相近的位置上，其曲線之間的距離也會較短[13]。如圖1顯示1、2、3階Hilbert曲線，本文選用3階Hilbert曲線進(jìn)行研究。

圖1 Hilbert曲線Fig.1 Hilbert curves

結(jié)合矢量時空數(shù)據(jù)，對Hilbert曲線進(jìn)行描述如下：

1)等分區(qū)域(cell)的大小取決于Hilbert曲線的階數(shù)λ，網(wǎng)格數(shù)m=22λ。

2)encodeNode(x,y)，利用Hilbert編碼規(guī)則將空間S內(nèi)的坐標(biāo)(x,y)轉(zhuǎn)換為Hilbert值。

3)encodeSegment(x1,y1,x2,y2)，將空間區(qū)域內(nèi)的坐標(biāo)范圍(x1,y1,x2,y2)轉(zhuǎn)換為一系列Hilbert范圍值，即一維區(qū)間。

1.3 空間聚類建模

針對時空數(shù)據(jù)空間部分采用樹形空間索引易產(chǎn)生大量重疊和死空間，考慮將空間上相鄰的數(shù)據(jù)存放于同一子樹下，即與聚類技術(shù)結(jié)合的方式，在減少數(shù)據(jù)存儲冗余及I/O尋道時間、提高檢索效率等方面具有重大的研究意義。目前多數(shù)聚類算法的結(jié)果易受初始K值及離群空間數(shù)據(jù)的影響[14]，本文在對空間要素對象進(jìn)行Hilbert曲線編碼后，依據(jù)空間要素分布特點，定義距離函數(shù)和均方差準(zhǔn)則函數(shù)。

定義1 距離函數(shù)。由r1、r2、…、rn組成的n個Rd空間要素集合，設(shè)oj為第j個類的聚類中心，則ri與oj的距離為：

(1)

定義2 均方差準(zhǔn)則函數(shù)。為使聚類效果滿足“類內(nèi)緊湊， 類間分離”的原則，需要聚類測度函數(shù)進(jìn)行衡量，均方差準(zhǔn)則函數(shù)如下：

(2)

其中:k為聚類數(shù)；i為Sj中的數(shù)據(jù)；o為Sj的聚類中心。算法思想：將k=1作為初始聚類，再令k值遞增，每次遞增后，都將通過計算得到新的聚類中心，使所有類中數(shù)據(jù)與聚類中心的距離平方誤差之和最小。遞增k值后，比較函數(shù)值E，若該值收斂，則將k值作為聚類數(shù)；若不收斂，則繼續(xù)遞增k值。經(jīng)分析，該算法的復(fù)雜度為O(nkt)，其中n指空間要素對象的個數(shù)，t指算法迭代次數(shù)。通常k?n且t?n，因此該算法時間復(fù)雜度接近線性，適合處理大規(guī)模的時空數(shù)據(jù)。

2 面向Redis的時空索引

2.1 構(gòu)建基于動態(tài)定值聚類的 Hilbert-R樹

目前，R樹及其變體的構(gòu)建以空間要素逐一插入的動態(tài)過程為多，而此處的Hilbert-R樹是靜態(tài)批次構(gòu)建的過程，在對空間要素進(jìn)行Hilbert編碼之后，根據(jù)定義1的距離函數(shù)選取兩兩距離最大的空間要素作為初始聚類中心，以使類間相似度較低，而類內(nèi)相似度較高。遞增聚類數(shù)K值，遵循層次聚類中的分裂思想，找到距聚類中心最遠(yuǎn)的空間對象及距該空間對象最遠(yuǎn)的另一空間對象，將二者作為新的聚類中心，開始聚類；根據(jù)定義2的均方差準(zhǔn)則函數(shù)，計算并比較K值變化(即每次聚類)后的函數(shù)值，若該值收斂，可將當(dāng)前狀態(tài)視為聚類結(jié)果；否則，繼續(xù)遞增K值。對Hilbert-R樹的構(gòu)建步驟闡述如下：

1)以某個時刻T(t0≤T≤tn)的空間數(shù)據(jù)集為研究對象，計算該數(shù)據(jù)集下所有空間要素的最小包圍矩形(Minimum Bounding Rectangle，MBR)及其中心。

2)調(diào)用聚類算法，產(chǎn)生以空間點要素及空間要素MBR為對象的K個聚類。

3)計算所得各聚類內(nèi)包含空間要素對應(yīng)的Hilbert值，并對該值進(jìn)行升序排序。

4)依據(jù)節(jié)點最大容量M(Msize≤32 MB)，對排列好的空間要素構(gòu)建葉節(jié)點。若聚類內(nèi)空間要素數(shù)小于等于M，則該聚類內(nèi)的所有空間要素構(gòu)成一個葉節(jié)點；反之，則生成多個含有M個空間要素的分組，并按生成順序構(gòu)建葉節(jié)點。

5)依據(jù)生成順序自底向上地構(gòu)建各層中間節(jié)點和根節(jié)點，進(jìn)而生成基于聚類的Hilbert-R樹。葉節(jié)點存放聚類所包含空間要素MBR對應(yīng)的Hilbert值，各層中間節(jié)點則存放其子節(jié)點的Hilbert最大值。

基于動態(tài)定值聚類的Hilbert-R樹構(gòu)建算法如下：

輸入tList=(t0,tn)。

輸出Hilbert-R樹。

Begin

foreachelementintList

element.MBR=cal()

endfor

myKNN_List=myKNN(tList)

my_HilbertValue=statistic(myKNN_List)

my_SortValue=sort(my_HilbertValue)

ifvalue<=Mthen

Hilbert-R=Create_tree(value,my_SortValue)

elseif

myGroup=Group(value,my_SortValue)

Hilbert-R=Create_tree(value,myGroup)

endif

returnHilbert-R

end

圖2 分級索引結(jié)構(gòu)Fig.2 Hierarchical index structure

2.2 建立分級索引結(jié)構(gòu)

經(jīng)上文Hilbert-R樹的構(gòu)建可知，Hilbert-R樹具有中間節(jié)點和葉節(jié)點兩種節(jié)點結(jié)構(gòu)，依據(jù)Redis數(shù)據(jù)庫Key-Value方式對時空數(shù)據(jù)進(jìn)行存儲。

選擇Redis作為時空數(shù)據(jù)存儲數(shù)據(jù)庫的原因如下：Redis是分布式非關(guān)系型數(shù)據(jù)庫之一，是一種具有高性能鍵值對的內(nèi)存數(shù)據(jù)庫。其中，鍵值(key)是Redis存儲數(shù)據(jù)的重要依據(jù)，具有唯一性，同時也作為對數(shù)據(jù)檢索、定位、修改和刪除的根本因素[15]。Redis中的鍵值對類似于關(guān)系數(shù)據(jù)庫中的行和列，不同的是value這一列可以存儲多個條目，而不是只能存儲一個值[18]。Redis支持豐富的數(shù)據(jù)結(jié)構(gòu)，用于滿足不同的矢量時空數(shù)據(jù)存儲要求，包括：string、list、set、zset(sorted set)、hash等多種鍵值數(shù)據(jù)類型。這些數(shù)據(jù)類型都支持取集合的交、并、差等多樣操作，還支持不同方式的排序，并且這些操作都是原子性的。此外，Redis為用戶提供了可靠的持久化方案和主從復(fù)制功能，以確保數(shù)據(jù)的安全性?；谝陨咸匦?，Redis可以保證對矢量時空數(shù)據(jù)的存儲和管理。

本文提出一種分級索引機制，將該時空數(shù)據(jù)庫結(jié)構(gòu)劃分為已聚類的空間部分和時間部分。整個時空數(shù)據(jù)集被周期化的時間值(以小時為單位)所劃分，即每個空間數(shù)據(jù)集對應(yīng)不同的時間值，因此將時間部分的索引建立于第一層索引結(jié)構(gòu)中；對某一時刻T的聚類結(jié)果(即Hilbert-R樹中具有相同時間值的中間節(jié)點)進(jìn)行索引信息的存儲構(gòu)建；而對空間要素的索引建立在Hilbert-R樹的中間節(jié)點之上，即圖2第三層，中間節(jié)點存放其子節(jié)點的最大Hilbert值?；谝陨戏謱臃旨壍乃饕Y(jié)構(gòu)，查詢某個時空數(shù)據(jù)可以先通過時間索引，確定該時刻的空間聚類信息，再利用高效的Hilbert-R樹定位于目標(biāo)對象。具體分層分級索引結(jié)構(gòu)及其在Redis數(shù)據(jù)庫中的存儲方式如圖2所示。

第一層 時間索引信息存儲，采用Redis數(shù)據(jù)庫中的有序集sorted set數(shù)據(jù)結(jié)構(gòu)對時空數(shù)據(jù)集元數(shù)據(jù)信息中唯一對應(yīng)的時間值進(jìn)行組織，可以通過key=Index:T的格式訪問對應(yīng)的數(shù)據(jù)集，將時間值[n,n-1)作為sorted set使用的排序碼，如表1所示。

表1 時間索引信息存儲結(jié)構(gòu)Tab.1 Information storage structure of rime index

第二層 調(diào)用聚類函數(shù)，將某一時刻[n,n-1)下的空間要素(r1,r2,…,rn)進(jìn)行聚類操作，得到K個聚類結(jié)果。統(tǒng)計類中要素的Hilbert值，并升序排列。

第三層 中間節(jié)點索引信息存儲，針對同一時間下不同聚類結(jié)果的索引采用Redis的sets數(shù)據(jù)結(jié)構(gòu)進(jìn)行組織，通過key=Index：T：Index_I可以訪問具體的聚類索引項，即Hilbert-R樹的中間節(jié)點，它們都具有相同的時間屬性，具體結(jié)構(gòu)如表2所示，In數(shù)為Tn時刻的聚類個數(shù)。

表2 分級索引信息存儲結(jié)構(gòu)Tab.2 Information storage structure of hierarchical index

第四層 Hilbert-R樹的葉子節(jié)點，即各聚類內(nèi)所包含的空間要素(r1,r2,…,rn)。

最后將Hilbert-R樹的中間節(jié)點元數(shù)據(jù)信息利用Redis數(shù)據(jù)庫中的sets數(shù)據(jù)結(jié)構(gòu)進(jìn)行組織，用于存放葉子節(jié)點的最大Hilbert值。如表3所示，其中(rh1,rh2,…,rhn)表示各葉子節(jié)點所對應(yīng)的Hilbert值。

表3 中間節(jié)點信息存儲結(jié)構(gòu)Tab.3 Information storage structure of intermediate node

2.3 基于Hilbert-R樹的時空查詢流程

時空范圍查詢的基本思想：根據(jù)查詢空間范圍(x,y)或(x1,y1,x2,y2)調(diào)用函數(shù)encodeNode(x,y)或encodeSegment(x1,y1,x2,y2)并轉(zhuǎn)換為對應(yīng)Hilbert值或Hilbert范圍值；同時結(jié)合所查詢時間值調(diào)用第一級時間索引，確定查詢目標(biāo)所對應(yīng)的Hilbert-R樹中，遞歸調(diào)用Hilbert-R樹索引結(jié)構(gòu)，對樹中空間要素與查詢對象進(jìn)行精準(zhǔn)相交檢測，直到輸出查詢結(jié)果。圖3是時空查詢算法流程。

3 實驗分析

實驗采用Redis 2.6標(biāo)準(zhǔn)版，操作系統(tǒng)為CentOS release 6.5 64 bit，硬件環(huán)境配置為：Intel Core i7-4790 CPU @3.60 GHz，8 GB內(nèi)存，500 GB硬盤。實驗數(shù)據(jù)集采用ShapeFile格式的烏魯木齊市道路交通數(shù)據(jù)，選取了2011—2014年的數(shù)據(jù)?？紤]時空范圍和空間分布兩個因素，分別進(jìn)行了數(shù)據(jù)密集型測試及目標(biāo)矢量對象測試，最后進(jìn)行時空范圍查詢綜合測試，實驗對比文獻(xiàn)[9]中的CCR+樹，并對本文方案技術(shù)特點進(jìn)行驗證如下。

3.1 數(shù)據(jù)密集型測試

本實驗選取相同時空范圍內(nèi)不同空間分布狀況的數(shù)據(jù)集對Hilbert-R樹及CCR+樹[9]對空間索引性能的測試。

在定義1的基礎(chǔ)上，定義P為平均分布狀態(tài)[6]:

(3)

其中：li(i=1,2,…,n)表示空間數(shù)據(jù)的鄰近對象個數(shù)；P值的大小反映了空間分布的密集狀態(tài)。如表4所示數(shù)據(jù)集T1、T2的P值較大，則說明空間分布狀態(tài)較密集；而數(shù)據(jù)集T3、T4的P值接近1，表示二者空間分布較均勻。

表4 空間數(shù)據(jù)分布狀態(tài)Tab.4 Distribution of spatial data

不同空間分布下，Hilbert-R樹與CCR+樹的查詢耗時結(jié)果如圖4所示。在不同密集程度下，經(jīng)聚類后的Hilbert-R樹的查詢耗時約為CCR+樹的一半，說明前者查詢耗時較短，進(jìn)一步驗證了數(shù)據(jù)是否平均分布對本文算法的查詢效率影響不大。這是因為本文算法充分考慮了空間要素的分布特點，動態(tài)確定K值的聚類算法盡可能地將空間分布相近的要素聚為一類，經(jīng)有效聚類后構(gòu)建Hilbert-R樹，提出分層分級的索引結(jié)構(gòu)，將聚類結(jié)果在同一子空間的要素組織在同一子樹下，較大程度上降低中間節(jié)點間的重疊，對分布不均勻的空間要素得以正確處理，從而提高索引操作的性能。

圖3 時空查詢算法流程Fig.3 Flow chart of spatial-temporal query

圖4 不同分布狀態(tài)下CCR+和Hilbert-R的查詢對比Fig.4 Contrast of CCR+ and Hilbert-R in different distribution states

3.2 目標(biāo)矢量對象查詢

為進(jìn)一步分析空間分布相同(分別選取分布密集和均勻的情況下)不同時空范圍下針對目標(biāo)矢量對象的查詢，本實驗數(shù)據(jù)采用時空數(shù)據(jù)生成器(Generator of Spatio Temporal Data， GSTD)生成不同的時空范圍模擬數(shù)據(jù)集，其中:D1～D5的P值都等于3.44，D6～D10的P值都等于1.05，分別選取不同時空范圍的區(qū)域進(jìn)行研究，對應(yīng)矢量對象數(shù)目也不盡相同(如表5所示)。GSTD是一個被廣泛認(rèn)同的目標(biāo)對象數(shù)據(jù)集生成器。利用所生成的諸模擬數(shù)據(jù)集分別查詢目標(biāo)矢量對象，計算各自訪問節(jié)點數(shù)目的平均值，以此反映Hilbert-R樹與CCR+樹的查詢效率。

表5 樣本數(shù)據(jù)集描述Tab.5 Sample data set description

圖5和圖6分別展示了密集分布和均勻分布下，Hilbert-R樹與CCR+樹對目標(biāo)矢量對象查詢時，二者平均訪問節(jié)點數(shù)目的情況：

1)CCR+樹訪問節(jié)點數(shù)與數(shù)據(jù)集的數(shù)量呈正比例增長的趨勢；而Hilbert-R樹無論在分布密集還是均勻的情況下，對節(jié)點訪問數(shù)的增幅都不明顯。

2)隨數(shù)據(jù)集的增大，Hilbert-R樹對節(jié)點訪問的變化率較CCR+樹穩(wěn)定，從而驗證了本文算法查詢效率對數(shù)據(jù)量的變化不敏感，受數(shù)據(jù)分布狀態(tài)的影響不大。

這是因為CCR+樹進(jìn)行查詢時從索引樹的根節(jié)點開始，依次遍歷存儲于其中的空間要素，節(jié)點間被動搜索滿足條件的葉節(jié)點，有可能會遍歷整棵樹。

圖5 密集分布下的訪問節(jié)點數(shù)對比Fig.5 Comparison of access nodes under dense distribution

圖6 均勻分布下的訪問節(jié)點數(shù)對比Fig.6 Comparison of access nodes under uniform distribution

本文在構(gòu)建Hilbert-R樹的過程中充分考慮了實際時空數(shù)據(jù)的分布特點，利用聚類方法使得Hilbert-R樹結(jié)構(gòu)更加緊湊。算法動態(tài)尋找最優(yōu)K值將數(shù)據(jù)對象劃分為多個類，自底向上逐層構(gòu)建樹結(jié)構(gòu)，確保數(shù)據(jù)精準(zhǔn)劃分，迭代重定位使劃分逐步改進(jìn)，同時分層分級索引結(jié)構(gòu)的提出對時間維的查詢更加便捷，避免訪問多余節(jié)點，有利于需要同時考慮空間和時間的目標(biāo)矢量對象的查詢。

3.3 時空范圍查詢

本實驗選取了2013年2月1日—2日的車輛軌跡數(shù)據(jù)(共包含30 177條記錄數(shù))作為實驗數(shù)據(jù)對聚類的Hilbert-R樹及CCR+樹進(jìn)行時空范圍查詢的綜合測試，選中從第5084條記錄數(shù)開始，以平均間隔約5 000條遞增的數(shù)據(jù)量(包括第5084、第10850、第15065、第20037、第25085、第30177條記錄數(shù))分別進(jìn)行10次測試后，取查詢耗時的平均值。

圖7對比了聚類的Hilbert-R樹與CCR+樹在不同數(shù)據(jù)量下的時空范圍查詢效率，可分析得到：

1)Hilbert-R樹的查詢耗時與數(shù)據(jù)記錄數(shù)量的關(guān)系呈線性正相關(guān)；

2)Hilbert-R樹相比CCR+樹的查詢耗時平均縮短了約25%；

3)隨著數(shù)據(jù)量的增大，Hilbert-R樹的查詢響應(yīng)時間優(yōu)勢較CCR+樹更趨明顯。

經(jīng)分析發(fā)現(xiàn)，在對時間范圍方面的查詢時，由于CCR+樹并未考慮時空數(shù)據(jù)的時間屬性，將其歸入空間屬性的另一維，致使整個多維空間數(shù)據(jù)不能協(xié)調(diào)分布，節(jié)點間頻繁訪問，徒增查詢開銷。

圖7 時空范圍查詢結(jié)果Fig.7 Results of spatio-temporal range queries

然而Hilbert曲線本身具有良好的數(shù)據(jù)聚集特性，聚類后的Hilbert-R樹的構(gòu)建對不同分布的空間要素進(jìn)行處理，使相鄰空間要素聚集于相鄰中間節(jié)點之上，減少了R樹節(jié)點間的重疊，使得查詢所需訪問的節(jié)點數(shù)更少，提高了查詢效率；同時本文提出的分層分級索引結(jié)構(gòu)充分考慮了時間屬性，時空數(shù)據(jù)依時間—空間合理組織，對于查詢性能的提升也起到了重要作用。

3.4 結(jié)果分析

為了探索在不同空間分布及時空范圍下，Hilbert-R樹及CCR+樹對矢量時空數(shù)據(jù)的查詢情況，本節(jié)采用ShapeFile格式的烏魯木齊市道路交通數(shù)據(jù)展開實驗，分別對Hilbert-R樹及CCR+樹的數(shù)據(jù)密集型、時空查詢效率和目標(biāo)矢量對象查詢進(jìn)行了測試。分析以上實驗結(jié)果可得出結(jié)論如下：

1)聚類后的Hilbert-R樹分層分級索引結(jié)構(gòu)受數(shù)據(jù)分布狀況的影響不大，因此適用于對空間分布不均且局部密度較大的時空數(shù)據(jù)查詢；

2)隨數(shù)據(jù)量的增加，Hilbert-R樹相對于CCR+樹的時空查詢效率更高，其訪問節(jié)點數(shù)更少，因此適用于時空范圍較大的矢量數(shù)據(jù)。

綜上，采用聚類的Hilbert-R樹分層分級索引結(jié)構(gòu)可開展時空大數(shù)據(jù)存儲及查詢算法的應(yīng)用，在內(nèi)存數(shù)據(jù)庫支持下進(jìn)行多尺度、多類型的時空數(shù)據(jù)查詢，為時空地理信息系統(tǒng)(Geographic Information System, GIS)的發(fā)展奠定理論基礎(chǔ)及方法借鑒。

4 結(jié)語

鑒于時空數(shù)據(jù)的矢量查詢應(yīng)用中缺乏對時間維和空間要素合理組織的考慮，本文從時空數(shù)據(jù)的空間分布出發(fā)，提出基于Hilbert-R樹分級索引的時空查詢算法。該算法利用Redis豐富的數(shù)據(jù)結(jié)構(gòu)對周期化的數(shù)據(jù)集建立時間索引，經(jīng)Hilbert曲線劃分并編碼空間部分，在此基礎(chǔ)上進(jìn)行聚類處理；將空間聚類結(jié)果與時空數(shù)據(jù)的時間屬性結(jié)合，建立Hilbert-R樹的分層分級索引結(jié)構(gòu)。經(jīng)實驗驗證，所提算法有效降低了時空查詢的時間開銷，且對樹節(jié)點的訪問量不大，查詢耗時受不同數(shù)據(jù)分布密度的影響較小，更適合Redis對海量時空數(shù)據(jù)高效查詢處理的需求。

下一步研究工作將優(yōu)化Hilbert-R樹索引構(gòu)建，引入機器學(xué)習(xí)算法對時空軌跡模式挖掘進(jìn)行研究，使時空查詢效率更高。