徐江峰，譚玉龍

（鄭州大學信息工程學院，鄭州450001）

0 引言

隨著無線和移動技術(shù)的進展，對移動性的需求日益增加，基于位置的服務（Location-Based Service，LBS）利用移動設(shè)備的能力，通過移動網(wǎng)絡提供用戶當前的地理位置。它們允許移動用戶搜索他們的環(huán)境，并使他們能夠立即訪問個性化和本地化的內(nèi)容。目前，移動用戶可以使用各種各樣的LBS，包括路由映射應用程序、交互式城市指南、位置感知營銷、對象跟蹤和監(jiān)控，以及基于鄰近［1］查找對象。LBS對底層支持平臺提出了廣泛的需求，包括對多維數(shù)據(jù)建模、處理數(shù)百萬用戶的高速更新以及對大量數(shù)據(jù)進行實時分析。

通過利用內(nèi)置的索引功能和豐富的查詢處理語言，傳統(tǒng)關(guān)系數(shù)據(jù)庫管理系統(tǒng)（Relational Database Management System，RDBMS）可以在多維數(shù)據(jù)上提供高效和快速的復雜查詢處理。這些索引功能是通過在關(guān)系存儲之上創(chuàng)建額外的索引層來提供的。例如，Oracle spatial 支持基于R-tree［2］和四叉樹［3］的索引。然而，這些集中的系統(tǒng)會產(chǎn)生單一的故障點，實現(xiàn)起來成本很高，而且隨著數(shù)據(jù)量和用戶數(shù)量的增長，會遇到可伸縮性瓶頸。

分布式鍵值存儲成為一種提供彈性數(shù)據(jù)管理服務的新范式，可以根據(jù)不同應用程序的需求進行伸縮。當前的鍵值存儲（BigTable［4］、HBase［5］和Cassandra［6］）被設(shè)計成高可用性、高容錯性和保持高更新吞吐量支持數(shù)百萬用戶；但是，這些鍵值存儲只能處理單個屬性的高效精確匹配查詢，因為它們?nèi)狈υL問多個屬性的內(nèi)置索引機制。對于查詢多個屬性，有兩個設(shè)計選項可用：第一種選擇是為每個屬性創(chuàng)建單獨的索引，但是，在管理大量數(shù)據(jù)時，創(chuàng)建多個索引表會給系統(tǒng)帶來巨大的額外負載；第二種選擇是使用MapReduce［7］范式的并行處理來掃描整個數(shù)據(jù)集，然而，LBS 需要實時的查詢處理，因此，對整個數(shù)據(jù)集進行并行掃描并不是很有用。

本文提出了一種新的數(shù)據(jù)分布和多維索引框架New-grid來支持云平臺上的LBS。由于鍵值存儲的優(yōu)點，使用它們作為存儲后端是很自然的選擇。然而，在鍵值存儲之上開發(fā)這樣的索引框架的關(guān)鍵挑戰(zhàn)是：如何對多維數(shù)據(jù)進行有效建模，并為其提供高效處理復雜多維查詢的能力。New-grid 采用基于Hilbert 曲線［8］的線性化技術(shù)解決前一個問題，然后將其與改進的覆蓋網(wǎng)絡P-Grid［9］進行集成。優(yōu)化的New-grid 通過預先計算并將子空間分配給網(wǎng)絡中的節(jié)點，成為一個靜態(tài)網(wǎng)絡。Hilbert 曲線在保持數(shù)據(jù)局部性的同時，將多維屬性映射到一維。另一方面，P-Grid 以虛擬二進制形式呈現(xiàn)的節(jié)點進行排列，并將多維搜索空間劃分為子空間。前綴結(jié)構(gòu)充當?shù)讓渔I值存儲之上的靜態(tài)路由索引層，并充當多維搜索的入口點。因此，本文主要工作之一就是建立這個P-Grid覆蓋網(wǎng)絡，然后由New-grid 根據(jù)P-Grid 前綴的路由機制在集群中進行分布復雜的查詢。綜上所述，本文的主要工作如下：

1）提出一種新的數(shù)據(jù)分布和多維索引框架New-grid，它可以有效地索引和處理點、范圍和K 最近鄰（K-Nearest Neighbors，KNN）查詢。

2）利用基于Hilbert 空間填充曲線的線性化技術(shù)將多維數(shù)據(jù)轉(zhuǎn)換為一維數(shù)據(jù)，同時保持了數(shù)據(jù)的局部性。

3）提出一種利用改進的P-Grid 前綴路由機制動態(tài)處理線性化值上的點、范圍和KNN 查詢的算法，以消除創(chuàng)建和維護單獨索引表的開銷。

4）在Amazon EC2 上進行實驗來測量insert 吞吐量以及點、范圍和KNN 查詢，以展示本文的框架相比MD-Hbase 的有效性。

1 相關(guān)技術(shù)

1.1 空間填充曲線的線性化

線性化是一種將多維屬性映射到一維空間上的降維方法?？臻g填充曲線是一種線性化技術(shù)，它是在不重疊的情況下，通過訪問n 維超立方體中的每個點來構(gòu)造連續(xù)曲線。它們的優(yōu)勢是：在映射之后，在n 維空間中的相鄰點在一維空間中也保持鄰近。因此，空間填充曲線在圖像處理［10］、科學計算［11］、地理信息系統(tǒng)［12］等需要順序訪問數(shù)據(jù)集的應用中得到了廣泛的應用。在New-grid 中，本文使用Hilbert 空間填充曲線索引底層一維鍵值存儲中的多維點，以提高查詢效率。

Hilbert 曲線是一種連續(xù)的空間填充曲線，它在多維數(shù)據(jù)點上產(chǎn)生順序排列。形式上，希爾伯特曲線是一個一對一的函數(shù)：

其中n 是2m×2m 空間維度的數(shù)量，n ≥2，m ＞1。這個函數(shù)決定了Hilbert 值（H 值）的原始坐標空間中的每個點的H值∈(0，2mn-1)。圖1 展示了二維空間中的坐標及其一階等效Hilbert 曲線。遞歸構(gòu)造階數(shù)i ＞1 曲線，將一階曲線的每個頂點旋轉(zhuǎn)或反射后，替換為i-1階曲線，以適應新的曲線［13］。

遞歸構(gòu)造過程也可以表示為一個樹形結(jié)構(gòu)（圖3），用二進制符號［14］表示坐標點n 與H 值的對應關(guān)系。樹的深度等于曲線的階數(shù)，根節(jié)點對應圖1 的一階曲線。同時，任意樹級的節(jié)點集合i 描述了i 階曲線，以點（10，11）為例，用圖3 所示的樹結(jié)構(gòu)來演示二維二階H 值的計算。在第一步中，將點（10，11）坐標的頂端位串聯(lián)起來，形成n點11。在根節(jié)點上，這個n點對應于子空間10。在下一步中，沿著根的子空間10，從樹的第1 層下降到第2 層。把這個點坐標的后兩位連起來形成n 點01。在樹的第2 層，n 點對應于子空間01。由于沒有更多的層可以下降，H 值的計算就結(jié)束了。點（10，11）的最終H 值由在每個步驟中從根節(jié)點開始的子空間的值串聯(lián)而成，即1001。使用樹結(jié)構(gòu)生成點的H 值需要每個屬性的基數(shù)相等。然而，在LBS 中，屬性的基數(shù)可能是不相等的。因此，在Newgrid 中，使用文獻［15］中給出的算法計算H 值，該算法使用邏輯運算高效地計算Hilbert 曲線上屬性不相等的點的直接映射和逆映射。

圖1 二維空間及其等效一階希爾伯特曲線Fig.1 Two-dimensional space and its equivalent first order Hilbert curve

圖2 二維二階Hilbert曲線Fig.2 Two-dimensional second-order Hilbert curve

圖3 二維二階Hilbert曲線的樹表示Fig.3 Tree representation of two-dimensional second order Hilbert curve

1.2 P-Grid

P-Grid［16］是一種基于分布式散列表的可伸縮自組織結(jié)構(gòu)化覆蓋網(wǎng)絡，它的訪問結(jié)構(gòu)是基于虛擬二叉樹的。二叉樹結(jié)構(gòu)用于為精確匹配和范圍查詢實現(xiàn)基于前綴的路由策略。P-Grid 為每個節(jié)點n 分配一個二進制位串，表示其在整個字典樹中的位置，稱為節(jié)點的路徑（n），該路徑包含從葉子到根的序列。圖4 為P-Grid 二叉樹的示意圖。存儲一個數(shù)據(jù)項，P-Grid 使用保哈希函數(shù)將數(shù)據(jù)項的標識符轉(zhuǎn)換成一個二進制關(guān)鍵key(key ∈[0，1])。數(shù)據(jù)項被路由到該節(jié)點的路徑與key最長公共前綴。例如，圖4 中節(jié)點2 的路徑為01，因此它存儲了所有鍵值以01開頭的數(shù)據(jù)項。

圖4 P-Grid字典樹示例Fig.4 Example of P-Grid trie

P-Grid 采用一種完全分散并行的構(gòu)造算法，可以構(gòu)造出延時較短的覆蓋網(wǎng)絡。構(gòu)建過程嚴格基于本地對等交互，這種交互是通過在已有的非結(jié)構(gòu)化覆蓋網(wǎng)絡上發(fā)起隨機遍歷來完成的。P-Grid 中的每個節(jié)點都維護一個路由表，該表存儲關(guān)于網(wǎng)絡中其他節(jié)點的路徑的信息。具體地說，對于每個位置，它維護至少一個節(jié)點的地址，而且該節(jié)點的路徑在該位置上具有相反的位。該信息以[path(n)，F(xiàn)QDN(n)]的形式存儲在路由表中，其中FQDN(n)是節(jié)點的全限定域名。具體構(gòu)造算法見文獻［17］。

2 New-grid數(shù)據(jù)分布和索引框架

New-grid 索引框架由從云端租用的無共享節(jié)點集群組成。New-grid 的主要目標是通過一個真正分散的P2P 架構(gòu)來支持LBS，該架構(gòu)可以相應地進行擴展。New-grid通過采用簡單的兩層架構(gòu)來實現(xiàn)。上層是基于P-Grid 的覆蓋網(wǎng)絡，該網(wǎng)絡負責路由查詢并為計算節(jié)點分配子空間，而下層則根據(jù)數(shù)據(jù)模型的類型使用底層鍵值存儲（HBase）來維護數(shù)據(jù)。Newgrid 中的節(jié)點有兩個用途：一個節(jié)點是P-Grid 中的節(jié)點，因為它維護其路由表中所有其他節(jié)點的子空間信息；另一個節(jié)點是HBase 集群的一部分，它存儲實際數(shù)據(jù)。New-grid 的體系結(jié)構(gòu)將查詢處理分為兩個階段：在第一階段中，通過搜索路由表來確定存儲子空間的節(jié)點。路由表包含所有其他節(jié)點的引用，這是通過將節(jié)點安排在一個虛擬二進制樹結(jié)構(gòu)中來實現(xiàn)的。在第二階段，查詢被轉(zhuǎn)發(fā)到本地處理它的負責節(jié)點上。

New-grid 系統(tǒng)架構(gòu)如圖5 所示。本文使用自底向上的方法構(gòu)造New-grid，其中節(jié)點首先被安排在HBase 集群中，然后加入覆蓋網(wǎng)絡。建設(shè)是在一個離線的過程中完成，并有一個小的一次性設(shè)置成本。數(shù)據(jù)插入可以在任何節(jié)點上完成。為了插入數(shù)據(jù)，首先計算多維點的H值，并根據(jù)給出的數(shù)據(jù)模型進行插入，底層使用Apache HBase［5］來存儲多維點的H 值，將其用作唯一的行鍵。

2.1 數(shù)據(jù)插入和點查詢

數(shù)據(jù)插入和點查詢可以通過使用P-Grid的搜索機制來執(zhí)行，將插入或查詢請求轉(zhuǎn)發(fā)到負責節(jié)點。本文的算法（算法1和算法2）利用鍵值存儲提供直接數(shù)據(jù)訪問的能力，各自高效地插入數(shù)據(jù)和處理點查詢。在算法1 中，插入一個點，首先計算該點（第1）行）的二進制H 值（rowkey）。然后，對于每個節(jié)點模型的表，插入操作分為兩個階段：在第一階段，搜索路由表ρ，找到名稱為（FQDN）節(jié)點的路徑的最長公共前綴行鍵（第2）行）。此模型將數(shù)據(jù)存儲在一個表中，該表的名稱設(shè)置為節(jié)點的名稱，此步驟足以找到負責存儲該點的表的名稱。在第二階段，按照標準的insert 操作在表中插入rowkey（第3）行），對于表共享模型，可以很容易地在預定義的共享表中插入rowkey（第5）行）。

Algorithm 1：Data Insert（point p，value v）

1） rowkey←compute H-value（p）

//Table per Node//

2） n.Table=PrefixMatchingBinarySearch(ρ，rowkey)

3） n.Table.insert（rowkey，value v）

4） return true

//Table Share//

5） sharedTable.insert（rowkey，value v）

6） return true

圖5 New-grid系統(tǒng)架構(gòu)Fig.5 New-grid system architecture

算法2 是查詢處理算法，對于每個節(jié)點模型的表，查詢處理分為兩個階段。給定d 維點p=(p1，p2，…)，點查詢策略試圖識別與p 關(guān)聯(lián)的值v。為了處理查詢，首先計算該點的H 值來計算行鍵（第1）行）。在第一階段，搜索路由表ρ，找到名稱為（FQDN）的節(jié)點，這個節(jié)點路徑與rowkey是最長的公共前綴（第2）行）。在第二個階段，通過檢索到v，在表上實現(xiàn)鍵查找操作。

Algorithm 2：Point Query Processing(p)

Input：query point p

Output：value v associated with p

1） rowkey←compute H-value（p）

//Table per Node//

2） n.Table=PrefixMatchingBinarySearch(ρ，rowkey)

3） return（v←lookup(rowkey，n.Table))

//Table Share//

4） return（v←lookup（rowkey，sharedTable））

2.2 范圍查詢處理

范圍查詢是檢索某個屬性位于上下邊界之間的所有記錄的查詢類型，在形式上分為兩種類型。范圍查詢是由上下邊界坐標(l1，l2，…，ln)和(u1，u2，…，un)構(gòu)成的超矩形區(qū)域，其中min ≤li≤ui≤max。LBS 中的另一個形式是“獲取z 半徑內(nèi)（x經(jīng)度，y緯度）附近的所有值”。P-Grid基于二叉樹的分區(qū)將線性化后的空間劃分為大小相等的子空間，并根據(jù)節(jié)點的路徑將子空間分配給節(jié)點。范圍查詢區(qū)域與一個或多個子空間相交。一個簡單的范圍查詢策略將通過在查詢下限和上限相交的子空間之間搜索來檢索查詢區(qū)域中包含的所有點。本文算法將范圍查詢處理分為以下兩個階段：

1）在第一階段中，將原始的范圍查詢劃分為更小的子查詢，每個子查詢區(qū)域與之相交的子空間都有一個子查詢，通過計算查詢區(qū)域內(nèi)每個子空間中點的最小H值來實現(xiàn)。將該點稱為下一個匹配點，并將其計算為calculate-next-match（）的函數(shù)。

2）在第二階段中，根據(jù)P-Grid 的搜索機制處理每個子查詢，該搜索機制將子查詢轉(zhuǎn)發(fā)給路徑與子查詢的上下界相交的所有節(jié)點。

例如，考慮圖6 所示的范圍查詢Q1。它的下界和上界坐標是A（01，01）和F（11，10）。等效H 值范圍這個查詢的值是［0010，1011］。二進制樹將空間劃分為大小相等的四個象限，即00、01、10 和11。要搜索的第一個子空間由下界H 值確定，下界H 值為00。為了得到范圍查詢中包含的點，需要搜索位于上下子空間之間的所有后續(xù)子空間。例如，簡單查詢策略將搜索00、01 和10 個子空間。子空間11 雖然與查詢相交，但是將被跳過。

圖6 映射到二維Hilbert曲線的二階點的范圍查詢示例Fig.6 Example of a range query on points mapped to two-dimensional second order Hilbert curve

該算法迭代地確定在樹的任意節(jié)點上與當前查詢區(qū)域相交的最小子空間。在每次迭代中，將丟棄一半的子空間，并沿著樹的正確分支下行，直到在葉級找到下一個匹配。同樣，這種下降是一個迭代過程，在每次迭代中，都用搜索子空間的邊界來限制用戶定義的搜索空間。

Algorithm 3：Range Query Processing

Input：query lower point ql，query higher point qh

Output：result set Rq

1） Rq←?

2） Sr←?

3） Hl←compute

4） Hh←compute H-value（qh）

5） Sr←calculateSubRanges

6） for each s ∈Srdo

7） Rq←PGrid.Search(s)

8） end for each

9） return Rq

2.3 KNN查詢處理

在一個d 維空間S，給定一組點N，根據(jù)一個距離函數(shù)，查詢處理算法返回一組k ∈N 的點，這些點鄰近于q。由于之前的結(jié)構(gòu)對節(jié)點間的數(shù)據(jù)分布是不可伸縮的，而且基于MapReduce 框架對大量數(shù)據(jù)進行KNN 查詢的解決方案會導致很高的查詢延遲。為了緩解這些問題，提出了一個簡單的查詢處理策略。KNN 查詢處理算法以遞增的搜索區(qū)域迭代執(zhí)行范圍搜索，直到檢索到k 個點為止。算法4 給出了KNN查詢算法的步驟。在第2）行中，首先構(gòu)造一個范圍r，集中在查詢點和初始半徑δ=Dk/k，Dk表示查詢點q 和它的K 最近鄰點的估計距離。Dk可以用式（1）［18］估計：

其中：Γ(x+1)=xΓ(x)，Γ(1)=1，Γ(1/2)=π/2，d 是維度，N 是基數(shù)。

Algorithm 4：K Nearest Neighbors(q，k)

Input：query point q，number of nearest neighbors k

Output：k nearest neighbors

1） Qresult←?

2） δ ←estimateRadius(k)

3） r ←δ

4） while true do

5） ql←q-r

6） qh←q+r

7） Qresult←RangeSearch

8） if|Qresult|≥k then

9） return top k results of Qresult

10） else

11） r ←r+δ

12） end if

13）end while

3 性能分析

在Amazon EC2 上實現(xiàn)了New-grid，集群大小為4、8 和16個節(jié)點。每個節(jié)點都是EC2 的一個中型實例，由4 個虛擬內(nèi)核、15.7 GB 內(nèi)存、配置為1 TB 硬盤和Centos 6.4 OS 組成；節(jié)點通過1 GB 的網(wǎng)絡鏈路連接。數(shù)據(jù)存儲層使用Hadoop 1.2.1和HBase 0.94.10實現(xiàn)。點、范圍和KNN查詢的實驗是在一個包含4 億個點的合成數(shù)據(jù)集上進行的。該數(shù)據(jù)集是使用基于網(wǎng)絡的移動對象生成器生成的，該生成器模擬了舊金山灣區(qū)地圖上40 000 個對象的移動。每個對象移動10 000步，并在連續(xù)的時間戳上報告其位置（經(jīng)度、緯度）。該數(shù)據(jù)集遵循一個傾斜分布，因為模擬器使用真實世界的公路網(wǎng)。本文運行一個簡單的MapReduce（MR）作業(yè)來計算數(shù)據(jù)集中點的最小值和最大值（區(qū)域邊界），并根據(jù)這些點的H 值的公共前綴設(shè)置節(jié)點的路徑。這有助于通過匹配預定義的子空間，使用行鍵在節(jié)點之間高效地分布數(shù)據(jù)集。行鍵將使用匹配的預定義子空間插入到正確的節(jié)點中。

在二維和三維數(shù)據(jù)集上進行了大量的實驗，以證明Newgrid的TPN和TS數(shù)據(jù)模型的有效性。以沒有覆蓋層的Hilbert曲線（H 階）作為索引層實現(xiàn)為基線。還針對MD-HBase［19］索引方案的TPB（MDH-TPB）和TS（MDH-TS）數(shù)據(jù)模型評估了New-grid 的性能。此外，還將范圍查詢的性能與MapReduce進行了比較。

3.1 插入的性能

LBS 不斷增長的趨勢，使其對可伸縮性的需求越來越明顯。使用YCSB［20］基準測試工具評估了New-grid的可伸縮性。圖7 將插入吞吐量的性能描述為包含4、8 和16 個節(jié)點的集群上的系統(tǒng)負載的函數(shù)。將工作負載生成器的數(shù)量從2 變化到96，其中每個工作負載根據(jù)Zipfian 分發(fā)版每秒生成10 000 個插入。在不同的節(jié)點上同時運行工作負載生成器并聚合結(jié)果。對于TS 模型，根據(jù)HBase 提供的水平可伸縮性，插入吞吐量幾乎隨工作負載生成器數(shù)量的增加而線性增長；但是，TPN 模型的插入吞吐量會隨著插入趨勢先增大后減小。對于位置更新60 s的間隔，TS模型達到峰值吞吐量約每秒840 000插入；然而，TPN 模型達到一個峰值吞吐量約每秒660 000 插入。兩種設(shè)計的性能都超過了MD-HBase，并且隨著節(jié)點數(shù)量的增加，差距也越來越大。

圖7 更改工作負載生成器數(shù)量的效果Fig.7 Effect of varying the number of workload generators

3.2 點查詢和范圍查詢的性能

多維點查詢和范圍查詢是LBS 中最常見的查詢。Newgrid通過直接查詢HBase表來處理點查詢。另一方面，范圍查詢的處理方法是首先將其劃分為多個子查詢，然后使用覆蓋層將每個子查詢同時轉(zhuǎn)發(fā)到負責節(jié)點。圖8 顯示了改變節(jié)點數(shù)量會對TPN、TS和H階模型的三維點查詢性能產(chǎn)生的影響。當增加節(jié)點數(shù)量時，所有模型的平均響應時間都增加了，尤其是TPN 模型。TS 和H 階模型的響應時間相同，因為它們都使用相同的查詢策略；但是，TPN 模型的響應時間比其他模型要長，這是因為需要通過搜索路由表并找到相關(guān)節(jié)點的成本較高。

圖8 點查詢性能(D=3)Fig.8 Performance of point query(D=3)

圖9 和圖10 分別顯示了不同選擇性和節(jié)點數(shù)量的TPN、TS、H 階和MR 模型的二維范圍查詢的性能。隨著節(jié)點數(shù)量的增加，TPN、TS 和H 階模型的查詢響應時間幾乎線性增加（圖9）；相反，MR 在對數(shù)據(jù)集進行全掃描以執(zhí)行查詢時，其響應時間是恒定的，因此其響應時間與選擇性無關(guān)。TS 和TPN模型的性能優(yōu)于其他模型，特別是對于選擇性較大的查詢，由于搜索區(qū)域較大的范圍查詢將與更多的子空間相交，從而產(chǎn)生多個子查詢。從圖10 中可以看出增加節(jié)點數(shù)量和同時保持10%的選擇性對平均范圍查詢響應時間的影響。隨著節(jié)點數(shù)量的增加，平均查詢響應時間會減少，因為節(jié)點數(shù)量的增加會導致數(shù)據(jù)的有效分布。此外，TPN 模型的性能優(yōu)于TS 模型，因為TPN 模型將所有數(shù)據(jù)本地存儲在節(jié)點上，而TS 模型將數(shù)據(jù)分布在集群中。

圖9 范圍查詢的性能(節(jié)點數(shù)為4，D=2)Fig.9 Performance of range query（number of nodes is 4，D=2）

圖10 范圍查詢的性能（選擇性=10%，D=2）Fig.10 Performance of range query（selectivity=10%，D=2）

在三維數(shù)據(jù)集上進行實驗的結(jié)果如圖11 和圖12 所示。圖11顯示了在4個節(jié)點集群上作為選擇性函數(shù)三維范圍查詢的性能。當增加選擇性時，TPN 和TS 模型的平均查詢響應時間會增加。在本實驗中，除了H 階模型和MR 模型外，還將TPN 和TS 模型的結(jié)果與MD-HBase 的TPB 和TS 數(shù)據(jù)模型進行了比較。比較結(jié)果表明，即使在選擇性較大的情況下，TPN和TS 模型的性能也較好。這是因為，在MD-HBase 中使用額外的索引層來修剪結(jié)果集，而在本文的方案中沒有這樣的開銷。

圖11 范圍查詢的性能（節(jié)點數(shù)為4，D=3）Fig.11 Performance of range query（number of nodes is 4，D=3）

圖12 范圍查詢的性能（選擇性=10%，D=3）Fig.12 Performance of range query（selectivity=10%，D=3）

3.3 KNN查詢的性能

New-grid 迭代處理k 個最近鄰居（KNN）查詢。首先利用式（1）估計查詢點與其第k 個近鄰之間的距離，即初始搜索半徑；然后，執(zhí)行范圍搜索來檢索k個結(jié)果，如果k個結(jié)果沒有返回，通過增加搜索空間并再次執(zhí)行范圍搜索。圖13 顯示了通過在4 個節(jié)點集群中將k 的值從1 增加到10 000，KNN 查詢在2 維數(shù)據(jù)集上對TPN、TS 和H 階模型的性能?？梢钥闯觯S著k值的增加，所有模型的KNN 查詢平均響應時間都在增加，因為隨著k值的增加，查詢空間也在增加。

圖13 KNN查詢的性能（節(jié)點數(shù)為4，D=2）Fig.13 Performance of KNN query（number of nodes is 4，D=2）

當然，這種平均響應時間的增加并不是指數(shù)級的，因為具有更大搜索空間的范圍查詢會使用更多的節(jié)點進行處理。將k 的值設(shè)置為10 000，節(jié)點數(shù)量從4 增加到16，得到的結(jié)果如圖14 所示。實驗結(jié)果表明，隨著集群中節(jié)點數(shù)量的增加，平均查詢響應時間會降低，因為更大的范圍查詢會與更多的子空間相交，從而涉及到更多的節(jié)點。在這兩個實驗中，TPN 和TS 模型的性能都比H 階設(shè)計的性能提高了4 到5 倍。在三維數(shù)據(jù)集上進行的一組實驗的結(jié)果如圖15 和圖16 所示。圖15顯示了參數(shù)k 的變化對4 個節(jié)點簇的影響，與MD-HBase 和H階設(shè)計進行對比，可以看出TPN 和TS模型的平均響應時間隨著參數(shù)k的增大而增大。然而，與二維相比，三維KNN查詢需要更多的時間來處理，因為執(zhí)行范圍查詢的復雜性隨著維數(shù)的增加而增加。

圖14 KNN查詢性能（k=10 000，D=2）Fig.14 Performance of KNN query（k=10 000，D=2）

圖15 KNN查詢的性能（節(jié)點數(shù)為4，D=3）Fig.15 Performance of KNN query（number of nodes is 4，D=3）

圖16 KNN查詢性能（k=10 000，D=3）Fig.16 Performance of KNN query（k=10 000，D=3）

4 結(jié)語

本文提出并評估了一個面向云平臺上位置感知服務的多維數(shù)據(jù)分布和索引框架New-grid。New-grid是一個可伸縮的、完全分散的、獨立于平臺的索引框架，可以有效地處理點、范圍和KNN 查詢。New-grid首先在修改后的P-Grid覆蓋網(wǎng)絡中安排從云租用的節(jié)點，該網(wǎng)絡實際上以二叉樹結(jié)構(gòu)劃分整個空間。其次，為了有效地存儲和檢索多維數(shù)據(jù)，利用基于Hilbert空間填充曲線的線性化技術(shù)將多維數(shù)據(jù)轉(zhuǎn)換為一維二進制鍵。這種技術(shù)允許我們根據(jù)對等點的路徑將鍵映射到它們，同時保留數(shù)據(jù)局部性。我們還設(shè)計并開發(fā)了算法來動態(tài)處理范圍和KNN 查詢，從而消除了創(chuàng)建和維護單獨索引表的限制。在Amazon EC2 上使用4、8 和16 個普通節(jié)點的集群進行了廣泛的實驗，結(jié)果表明，New-grid 的性能相比MD-Hbase更優(yōu)。

在未來，我們希望通過提供以動態(tài)方式處理數(shù)據(jù)偏斜度的能力來擴展該框架，并支持更廣泛的多維查詢，包括skyline和spatial-join；還希望開發(fā)高效的子空間分裂算法來實現(xiàn)負載均衡，并開發(fā)高效的數(shù)據(jù)復制算法來提高New-grid 的容錯能力；同時還想評估P-Ring P2P網(wǎng)絡［21］，看看它是否能夠滿足我們模型的所有要求，或者如何進行相應的修改，以及它與P-Grid在性能上的比較。