姚遠(yuǎn) 肖銳

摘? 要：隨著地理數(shù)據(jù)量的不斷增大，傳統(tǒng)的空間數(shù)據(jù)庫(kù)已經(jīng)無(wú)法滿(mǎn)足實(shí)際應(yīng)用的需要。為此，該文圍繞矢量數(shù)據(jù)的Top-K頻繁關(guān)鍵字問(wèn)題，設(shè)計(jì)了一個(gè)分布式空間數(shù)據(jù)庫(kù)系統(tǒng)。主要內(nèi)容為分布式矢量數(shù)據(jù)存儲(chǔ)模型設(shè)計(jì)，基于Hilbert排列碼的矢量數(shù)據(jù)劃分策略，分布式空間數(shù)據(jù)的索引結(jié)構(gòu)以及索引算法設(shè)計(jì)。

關(guān)鍵詞：分布式數(shù)據(jù)庫(kù);矢量數(shù)據(jù);關(guān)鍵字查詢(xún)

中圖分類(lèi)號(hào)：TP393.04? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）19-0007-05

Abstract：With the increasing amount of geographic data，the traditional spatial database has been unable to meet the needs of practical application. For this reason，this paper designs a distributed spatial database system around Top-K frequent keyword of vector data. The main contents are the design of distributed vector data storage model，vector data partition strategy based on Hilbert permutation code，index structure of distributed spatial data and index algorithm design.

Keywords：distributed database;vector data;keyword query

1? 問(wèn)題描述

空間Top-K頻繁關(guān)鍵字查詢(xún)定義。

輸入：

（1）數(shù)據(jù)：空間對(duì)象集合D={O1，O2，…，On}，Oi=（loci，kwi，1，…，kwi，m）包含位置loci和一組關(guān)鍵字kwi，1，…，kwi，m。

（2）查詢(xún)：Q=（RQ，k），RQ是查詢(xún)范圍，k是正整數(shù)。

輸出：在查詢(xún)范圍RQ內(nèi)的對(duì)象中出現(xiàn)頻率最大的k個(gè)關(guān)鍵字。

2? 系統(tǒng)設(shè)計(jì)

本文設(shè)計(jì)的系統(tǒng)是分布式的，即對(duì)于一個(gè)空間查詢(xún)Q，不再單單是在一個(gè)計(jì)算節(jié)點(diǎn)上的R樹(shù)中查找與查詢(xún)Q相交的或包含的范圍內(nèi)的前k個(gè)關(guān)鍵字，而是針對(duì)整個(gè)分布式系統(tǒng)各個(gè)節(jié)點(diǎn)上存儲(chǔ)的所有數(shù)據(jù)進(jìn)行查詢(xún)。系統(tǒng)的總體架構(gòu)如圖1所示。

2.1? 數(shù)據(jù)存儲(chǔ)

2.1.1? 數(shù)據(jù)劃分

基于Hilbert空間排列碼的空間劃分策略進(jìn)行劃分。空間數(shù)據(jù)劃分方法是多維數(shù)據(jù)分布式存儲(chǔ)的基礎(chǔ)，目的是通過(guò)一定的數(shù)據(jù)劃分規(guī)則，將多維數(shù)據(jù)集分割成多個(gè)獨(dú)立的數(shù)據(jù)分片，分布式存儲(chǔ)在集群中的計(jì)算節(jié)點(diǎn)上。

本系統(tǒng)采用的是一種空間填充曲線(xiàn)的劃分方法，主要思想是使用一條連續(xù)的曲線(xiàn)穿過(guò)空間中的每個(gè)離散單元，且只穿過(guò)一次，然后將每個(gè)空間數(shù)據(jù)按照填充曲線(xiàn)的規(guī)則進(jìn)行編碼，然后將編碼值相近的空間數(shù)據(jù)對(duì)象劃分到同一數(shù)據(jù)塊中，以此來(lái)對(duì)空間數(shù)據(jù)進(jìn)行降維。在空間上相鄰的離散單元，在填充曲線(xiàn)上依然是相鄰的。Hilbert曲線(xiàn)是目前比較常用的空間填充曲線(xiàn)，具有良好的空間連續(xù)性。由于每個(gè)對(duì)象包含的關(guān)鍵字個(gè)數(shù)不同，所以它們的數(shù)據(jù)量大小可能不同，但可以通過(guò)數(shù)據(jù)預(yù)處理，將一些數(shù)據(jù)大小過(guò)大的對(duì)象去除。在劃分空間數(shù)據(jù)集時(shí)，這里只考慮每個(gè)數(shù)據(jù)分片的空間對(duì)象個(gè)數(shù)，假設(shè)一個(gè)數(shù)據(jù)分片的總大小與其空間中對(duì)象個(gè)數(shù)成正比。

對(duì)于Hilbert空間編碼，確定合理的編碼階數(shù)是提高劃分效果的關(guān)鍵步驟。本系統(tǒng)采用雙層格網(wǎng)的Hilbert空間編碼構(gòu)建數(shù)據(jù)劃分?；舅枷胧牵焊鶕?jù)初始設(shè)定的每個(gè)數(shù)據(jù)分片大小，對(duì)數(shù)據(jù)集進(jìn)行初始格網(wǎng)劃分，然后統(tǒng)計(jì)每個(gè)格網(wǎng)的對(duì)象個(gè)數(shù)，對(duì)初始格網(wǎng)進(jìn)行二次劃分。之后基于復(fù)雜平衡將所有數(shù)據(jù)分片平均分到各個(gè)計(jì)算節(jié)點(diǎn)。具體算法見(jiàn)第3節(jié)的關(guān)鍵算法部分。

2.1.2? 數(shù)據(jù)備份

采用的是類(lèi)似Hadoop的同構(gòu)熱備份方式對(duì)主節(jié)點(diǎn)進(jìn)行備份，主節(jié)點(diǎn)有一個(gè)存儲(chǔ)相同數(shù)據(jù)的備用節(jié)點(diǎn)。當(dāng)主節(jié)點(diǎn)出現(xiàn)故障時(shí)，快速使用備用節(jié)點(diǎn)，防止數(shù)據(jù)錯(cuò)誤發(fā)生。系統(tǒng)中的計(jì)算節(jié)點(diǎn)采用的是異構(gòu)熱備份方式，即在主節(jié)點(diǎn)將數(shù)據(jù)劃分成很多分片后，將每個(gè)分片備份到多個(gè)計(jì)算節(jié)點(diǎn)，一般選擇將一個(gè)分片存儲(chǔ)在3個(gè)不同的計(jì)算節(jié)點(diǎn)上。

主節(jié)點(diǎn)通過(guò)對(duì)各個(gè)計(jì)算節(jié)點(diǎn)進(jìn)行心跳檢測(cè)，更新有效節(jié)點(diǎn)的個(gè)數(shù)，如果某個(gè)計(jì)算節(jié)點(diǎn)出現(xiàn)問(wèn)題，需要根據(jù)其他計(jì)算節(jié)點(diǎn)的負(fù)載，將異常計(jì)算節(jié)點(diǎn)上的數(shù)據(jù)分片存儲(chǔ)在其他有效的計(jì)算節(jié)點(diǎn)上，保證每個(gè)分片至少有3個(gè)備份。

2.1.3? 新數(shù)據(jù)導(dǎo)入

在2.1.1節(jié)中，使用了算法將數(shù)據(jù)集劃分成數(shù)據(jù)分片，并且對(duì)每一個(gè)數(shù)據(jù)分片都有一個(gè)Hilbert空間編碼值。所以當(dāng)有新數(shù)據(jù)導(dǎo)入時(shí)，先要計(jì)算一下新數(shù)據(jù)所對(duì)應(yīng)的空間范圍的Hilbert空間編碼值，將該數(shù)據(jù)發(fā)送其Hilbert編碼值所對(duì)應(yīng)的數(shù)據(jù)分片所在的計(jì)算節(jié)點(diǎn)中。如果某一個(gè)計(jì)算節(jié)點(diǎn)有溢出或崩潰的情況，那么就在新的全體數(shù)據(jù)集上運(yùn)行2.1.1節(jié)中的算法，進(jìn)行數(shù)據(jù)的重劃分。

2.2? 索引結(jié)構(gòu)

本系統(tǒng)采用一個(gè)兩層的索引結(jié)構(gòu)，如圖2所示。

在計(jì)算節(jié)點(diǎn)的本地索引的R樹(shù)上選擇其中的一些節(jié)點(diǎn)作為全局索引，然后將全局索引發(fā)布到各個(gè)計(jì)算節(jié)點(diǎn)的內(nèi)存中去，并且在內(nèi)存中為全局索引創(chuàng)建一棵R樹(shù)，以便后續(xù)查詢(xún)快速找到全局索引。這里將這個(gè)兩層索引結(jié)構(gòu)簡(jiǎn)稱(chēng)為R索引。

2.2.1? R索引結(jié)構(gòu)概述

系統(tǒng)將原始的數(shù)據(jù)集劃分到計(jì)算節(jié)點(diǎn)中，然后計(jì)算節(jié)點(diǎn)Ni存儲(chǔ)分配給它的數(shù)據(jù)Di。對(duì)于每一個(gè)計(jì)算節(jié)點(diǎn)Ni，在其內(nèi)存儲(chǔ)本地?cái)?shù)據(jù)Di和本地索引的R樹(shù)Ti。節(jié)點(diǎn)Ni在本地上建立好一棵R樹(shù)之后，從中選取出一些節(jié)點(diǎn)作為全局索引，全局索引的格式為（ip，port，address，region）。其中，ip是該索引所在計(jì)算節(jié)點(diǎn)的ip地址，port是該索引所在節(jié)點(diǎn)的端口號(hào)，使用ip地址加上端口號(hào)就可以定位到全局索引所在的位置了。Address是全局索引所在R樹(shù)中的位置在計(jì)算節(jié)點(diǎn)外存中的地址。region是索引對(duì)應(yīng)的R樹(shù)中節(jié)點(diǎn)的空間區(qū)域。

全局索引從本地索引中選擇出來(lái)并發(fā)布到計(jì)算節(jié)點(diǎn)中，在全局索引發(fā)布中，被選出的本地索引被添加ip和port等信息，然后再發(fā)給各個(gè)計(jì)算節(jié)點(diǎn)。然后，每一個(gè)計(jì)算節(jié)點(diǎn)接收到全局索引后，將其保存到自己的內(nèi)存中，同時(shí)在內(nèi)存中為全局索引維護(hù)一個(gè)R樹(shù)，便于后面的查詢(xún)快速地查找到相應(yīng)的數(shù)據(jù)。

當(dāng)使用R索引查找數(shù)據(jù)時(shí)，主要分為兩個(gè)階段（全局索引獲取和本地?cái)?shù)據(jù)獲?。?。首先，查詢(xún)?cè)谙到y(tǒng)中的空間劃分找到滿(mǎn)足查詢(xún)空間條件的計(jì)算節(jié)點(diǎn)，然后從計(jì)算節(jié)點(diǎn)的內(nèi)存中提取出在查詢(xún)范圍內(nèi)的全局索引。然后，根據(jù)全局索引的ip和port找到全局索引所在的計(jì)算節(jié)點(diǎn)，找到后，根據(jù)address信息從該點(diǎn)的R樹(shù)中提取出相應(yīng)的數(shù)據(jù)。后面2.2.3節(jié)將會(huì)具體闡述查詢(xún)過(guò)程的處理。

2.2.2? 全局索引到計(jì)算節(jié)點(diǎn)的映射

計(jì)算節(jié)點(diǎn)Ni從本地的R樹(shù)Ti中獲取一個(gè)全局索引的集合S（Ni），然后，計(jì)算節(jié)點(diǎn)將集合S發(fā)布到系統(tǒng)中的一部分計(jì)算節(jié)點(diǎn)中去，對(duì)于每一個(gè)接收到全局索引的計(jì)算節(jié)點(diǎn)，將該全局索引保存到自己的內(nèi)存中，便于后續(xù)查詢(xún)的快速反應(yīng)。首先，將當(dāng)前的數(shù)據(jù)空間劃分到各個(gè)計(jì)算節(jié)點(diǎn)Ni上，即每一個(gè)計(jì)算節(jié)點(diǎn)Ni都會(huì)維護(hù)一個(gè)劃分空間Space（Ni）。

在這個(gè)R索引系統(tǒng)中，對(duì)于一個(gè)給定的全局索引gi（ip，port，address，region），一個(gè)計(jì)算節(jié)點(diǎn)集合N，將全局索引gi映射到那些計(jì)算節(jié)點(diǎn)中的Space（Ni）與全局索引gi中的region相交的計(jì)算節(jié)點(diǎn)。

全局索引映射的形式表述：

對(duì)于一個(gè)全局索引gi=（ip，port，address，region）和計(jì)算節(jié)點(diǎn)集合N，R索引將gi映射到Ns中，其中，Ns= {Ni|Ni∈N，Space（Ni）∩region≠?}。

本系統(tǒng)中，使用一個(gè)接口用于獲取節(jié)點(diǎn)中的劃分空間區(qū)域與給定的gi中的region相交的計(jì)算節(jié)點(diǎn)。該接口記為GetNs（region）。當(dāng)系統(tǒng)要發(fā)布全局索引gi到系統(tǒng)中的各個(gè)計(jì)算節(jié)點(diǎn)中時(shí)，發(fā)布該索引的計(jì)算節(jié)點(diǎn)Ni調(diào)用GetNs（gi.region）接口函數(shù)，獲取要將gi發(fā)布到的計(jì)算節(jié)點(diǎn)集合Ns，然后對(duì)集合Ns中的節(jié)點(diǎn)，將gi插入到節(jié)點(diǎn)內(nèi)存中的全局索引的R樹(shù)中。

2.2.3? R索引查詢(xún)處理

R索引的查詢(xún)處理分為兩個(gè)階段：全局索引搜索和本地?cái)?shù)據(jù)獲取。當(dāng)系統(tǒng)收到一個(gè)查詢(xún)Q（RQ，K）后，查詢(xún)Q被發(fā)送到所有與Q.RQ相交的計(jì)算節(jié)點(diǎn)上去。而對(duì)于每一個(gè)收到查詢(xún)Q的計(jì)算節(jié)點(diǎn)Ni，在Ni的內(nèi)存R樹(shù)中的全局索引返回一個(gè)空間區(qū)域與Q.RQ相交的全局索引gi。然后計(jì)算節(jié)點(diǎn)Ni將查詢(xún)Q發(fā)送到全局索引gi所在的計(jì)算節(jié)點(diǎn)，而收到查詢(xún)Q的計(jì)算節(jié)點(diǎn)在本地的R樹(shù)上對(duì)于Q進(jìn)行查詢(xún)。

如圖3所示，圖中有5個(gè)計(jì)算節(jié)點(diǎn)1，2，3，4，5，其中1包含全局索引A，2包含B，3和4都包含C，5節(jié)點(diǎn)包含D。查詢(xún)RQ與全局索引A，C相交。這樣就將查詢(xún)RQ發(fā)送到所有A的擁有者中，然后在擁有者本地R樹(shù)上對(duì)RQ做查詢(xún)。而對(duì)于全局索引C，由于其與多個(gè)計(jì)算節(jié)點(diǎn)相交，所以3，4節(jié)點(diǎn)都會(huì)向擁有C的節(jié)點(diǎn)發(fā)送消息，這樣就造成了通信代價(jià)，所以這里采取讓離RQ更近的節(jié)點(diǎn)向擁有C的節(jié)點(diǎn)發(fā)送RQ查詢(xún)。

查詢(xún)算法：

輸入：查詢(xún)Q（RQ，K），計(jì)算節(jié)點(diǎn)集合N。

輸出：所有與查詢(xún)空間相交的本地節(jié)點(diǎn)的STL。

（1）判斷與RQ相交的全局索引gi和gi所在的節(jié)點(diǎn)Ni;

（2）將查詢(xún)Q通過(guò)全局索引gi=（ip，port，address，region）利用節(jié)點(diǎn)Ni發(fā)送到位置信息為ip+port的計(jì)算節(jié)點(diǎn)上;

（3）在本地索引R樹(shù)上進(jìn)行Q查詢(xún)，利用3.2節(jié)計(jì)算節(jié)點(diǎn)的Top-K頻繁關(guān)鍵字算法計(jì)算出每一個(gè)全局索引所在節(jié)點(diǎn)的所有STL;

（4）對(duì)于第3步中的STL，運(yùn)用3.3節(jié)的FT算法進(jìn)行查詢(xún)算法。

2.2.4? 全局索引的選擇策略

首先，全局索引的選擇需要滿(mǎn)足以下條件：第一，每一個(gè)計(jì)算節(jié)點(diǎn)的全局索引的數(shù)量要有一定的限制，因?yàn)樵摲植际较到y(tǒng)各節(jié)點(diǎn)內(nèi)的內(nèi)存空間是有限的，如果全局索引的數(shù)量過(guò)多，就會(huì)造成內(nèi)存裝不下的情況;第二，對(duì)于R樹(shù)中的每一個(gè)葉子節(jié)點(diǎn)n，或選擇n，或選擇包含節(jié)點(diǎn)n的父節(jié)點(diǎn)，保證選取的索引空間能夠覆蓋整個(gè)R樹(shù)，使查詢(xún)結(jié)果具有完整性;第三，R樹(shù)的節(jié)點(diǎn)n或n的祖先節(jié)點(diǎn)最多一個(gè)被選中為全局索引，這是因?yàn)橹貜?fù)選擇相互覆蓋的區(qū)域會(huì)造成不必要的全局索引的內(nèi)存開(kāi)銷(xiāo)，從而降低計(jì)算性能。

由于選擇全局索引的算法是一個(gè)NP問(wèn)題，所以采用貪心算法去選擇R樹(shù)中的全局索引。首先，假設(shè)內(nèi)存的全局索引限制大小為k1，取集合G作為選擇的全局索引的集合，當(dāng)限制大小未到k1時(shí)，自根節(jié)點(diǎn)開(kāi)始，一直沿R樹(shù)向下擴(kuò)展，如果子節(jié)點(diǎn)加入集合G并且父節(jié)點(diǎn)從集合G被刪除后的大小仍然小于全局索引限制k1，就將全局索引向下擴(kuò)展，并將當(dāng)前遇到的子節(jié)點(diǎn)放入集合G。否則，不進(jìn)行擴(kuò)展，到此節(jié)點(diǎn)結(jié)束。

3? 關(guān)鍵算法

3.1? 基于Hilbert空間排列碼的空間劃分策略

Algorithm1 Hilbert-partition（M，B，λ）：

輸入：空間對(duì)象集M，預(yù)期每個(gè)數(shù)據(jù)分片的大小B，閾值λ。

輸出：數(shù)據(jù)分片集合D。

（1）遍歷M，得到對(duì)象總數(shù)據(jù)量sum以及M的最小外接矩形空間R;

（2）第一次網(wǎng)格劃分的階數(shù)為n0=[log4sum/B];

（3）根據(jù)R，構(gòu)造2n0*2n0的初始網(wǎng)格，然后M中每個(gè)元素映射到初始格網(wǎng);

（4）遍歷空間格網(wǎng)單元，得到格網(wǎng)中單元最大數(shù)據(jù)量Gmax，如果存在數(shù)據(jù)量大于B*λ的單元，標(biāo)記該單元，并且對(duì)初始格網(wǎng)進(jìn)行階數(shù)為n1=[log4Gmax/B*λ]的二次優(yōu)化。如果沒(méi)有，則n1=0;

（5）構(gòu)造出n0+n1階的Hilbert填充曲線(xiàn)，對(duì)最終的空間格網(wǎng)進(jìn)行編碼;

（6）初始i=0，對(duì)于標(biāo)記單元，將該單元內(nèi)的數(shù)據(jù)對(duì)象按照編碼從小到大的順序添加到當(dāng)前數(shù)據(jù)塊di，若di的大小大于B，則i=i+1;對(duì)于未標(biāo)記的單元，將整個(gè)單元的數(shù)據(jù)對(duì)象添加到當(dāng)前數(shù)據(jù)分片di，若數(shù)據(jù)塊di的大小大于B，則i=i+1。即標(biāo)記單元中的數(shù)據(jù)可以存在不同的數(shù)據(jù)分片中，但未標(biāo)記的單元不可以。

3.2? 計(jì)算節(jié)點(diǎn)的Top-K頻繁關(guān)鍵字算法

節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)如下。

（1）葉子節(jié)點(diǎn)n1的STL中存儲(chǔ)Rn1對(duì)象的關(guān)鍵字聚集頻率，并按頻率降序排列。

（2）n1的STL大小為：|Vn1|，Vn1={Uo∈D，o.loc∈Rn1o.Terms}。對(duì)于Vn1中的關(guān)鍵字t，STL中存儲(chǔ)的項(xiàng)為<t，t.ObjectEntries，t.Freq>;

（3）t.ObjectEntries中包含nl中包括t的對(duì)象，每一項(xiàng)格式為<Loc，F(xiàn)req>，分別表示該對(duì)象的位置和包含t的頻率;

（4）t.Freq為t.ObjectEntries中所有項(xiàng)的Freq分量之和。

如圖4所示，是一個(gè)R樹(shù)中STL和R樹(shù)的示例，其中前兩層為R樹(shù)空間范圍，最后一層是包含對(duì)象O的編號(hào)。其中每個(gè)對(duì)象O包含的關(guān)鍵字如表1所示，R樹(shù)中R3葉子節(jié)點(diǎn)的STL如表2所示。

Algorithm2計(jì)算節(jié)點(diǎn)Top-K查詢(xún)算法（RQ）：

輸入：查詢(xún)空間RQ。

輸出：Top-K頻繁關(guān)鍵字以及他們的頻率值。

（1）從根節(jié)點(diǎn)開(kāi)始，向下查找所有與RQ相交的葉子節(jié)點(diǎn)（n1，…，nm）;

（2）如果葉子節(jié)點(diǎn)n1完全包含于RQ，則n1的STL全部用于后續(xù)計(jì)算;如果葉子節(jié)點(diǎn)n1部分相交于RQ，則n1的STL中與RQ相交的部分用于后續(xù)計(jì)算;

（3）對(duì)于每個(gè)<t，t.ObjectEntries，t.Freq>，利用ObjectEntries中的<Loc，F(xiàn)req>計(jì)算RQ內(nèi)的t.Freq;

（4） 為t在葉子節(jié)點(diǎn)與RQ相交部分出現(xiàn)的次數(shù)，利用所有參與計(jì)算的STL，使用RA或者NRA算法計(jì)算Top-K結(jié)果，Top-K計(jì)算函數(shù)為? 。

3.3? 基于FT算法的Top-K頻繁關(guān)鍵字的查詢(xún)算法

對(duì)于分布式系統(tǒng)來(lái)說(shuō)，關(guān)鍵是如何將各個(gè)計(jì)算節(jié)點(diǎn)的結(jié)果整合到Master節(jié)點(diǎn)。

本系統(tǒng)選擇了FT算法作為分布式系統(tǒng)Top-K頻繁關(guān)鍵字的查詢(xún)算法。先介紹兩個(gè)概念，第一個(gè)是每個(gè)關(guān)鍵字的和（Ssum），關(guān)鍵t的和Ssum（t）=S1（t）+S2（t）+…Sk（t），如果第i個(gè)節(jié)點(diǎn)已經(jīng)將它本地的關(guān)鍵詞t的頻率Pi（t）發(fā)到了中心節(jié)點(diǎn)則Si（t）=Pi（t），否則Si（t）=0。第二個(gè)是閾值Hi，其中Hi表示節(jié)點(diǎn)i中排名第k的關(guān)鍵字的出現(xiàn)次數(shù)，作為后續(xù)該節(jié)點(diǎn)排名k以后的關(guān)鍵詞出現(xiàn)次數(shù)的閾值。

Algorithm3 FT（RQ）算法如下。

（1）每個(gè)計(jì)算節(jié)點(diǎn)i將排名前k個(gè)關(guān)鍵詞、數(shù)值和Hi發(fā)送給Master，Master計(jì)算收到的所有關(guān)鍵字的Ssum，然后根據(jù)Ssum對(duì)關(guān)鍵字進(jìn)行降序排序，取第k名的Ssum作為閾值P1。之后根據(jù)Hi計(jì)算第k后的關(guān)鍵字的上限值Usum（其中Ssum（t）=S1（t）+S2（t）+…Sk（t），Si（t）=Pi（t）或Hi），將Usum小于P1的關(guān)鍵字削減掉。

（2）Master將沒(méi)有被削減的關(guān)鍵字（包括排名前k）再次發(fā)送到計(jì)算節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)接收到關(guān)鍵字列表后，找到列表中還未發(fā)送給Master的關(guān)鍵字j，并將j和j的值發(fā)送給Master。中心節(jié)點(diǎn)對(duì)收到的所用關(guān)鍵字再次進(jìn)行求和，然后取第k名的數(shù)值作為閾值P2。如果P2≥H1+H2+…Hm（假設(shè)有m個(gè)計(jì)算節(jié)點(diǎn)），那么算法就結(jié)束了。否則（可能存在某個(gè)關(guān)鍵字在所有節(jié)點(diǎn)中都不排在前k，但總和排在前k），繼續(xù)進(jìn)行步驟（3）和步驟（4）。

（3）Master中令M=P2/m，循環(huán)比較所有Hi與M，如果Hi

（4）類(lèi)似第二階段，Master將沒(méi)有被削減的關(guān)鍵字（包括排名前k）再次發(fā)送到計(jì)算節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)接收到關(guān)鍵字列表后，找到列表中還未發(fā)送給Master的關(guān)鍵字j，并將j和j的值發(fā)送給Master。中心節(jié)點(diǎn)對(duì)收到的所用關(guān)鍵字再次進(jìn)行求和，然后前k名的關(guān)鍵字即為精確解。

4? 系統(tǒng)流程

主要分成數(shù)據(jù)建立和數(shù)據(jù)查詢(xún)兩個(gè)過(guò)程。

建立過(guò)程：首先，對(duì)于給定的空間中的數(shù)據(jù)集D，分布式計(jì)算節(jié)點(diǎn)個(gè)數(shù)k，利用基于Hilbert空間排列碼的空間劃分策略，將數(shù)據(jù)集D中的點(diǎn)分配到k個(gè)計(jì)算節(jié)點(diǎn)上，每一個(gè)計(jì)算節(jié)點(diǎn)維護(hù)一個(gè)區(qū)域劃分。然后，在本地節(jié)點(diǎn)上利用本地?cái)?shù)據(jù)建立一棵R樹(shù)，R樹(shù)的葉子節(jié)點(diǎn)上存儲(chǔ)STL。然后，從各個(gè)計(jì)算節(jié)點(diǎn)的本地索引R樹(shù)中取出一些點(diǎn)作為全局索引。再將全局索引分配到相應(yīng)的計(jì)算節(jié)點(diǎn)的內(nèi)存當(dāng)中，其中內(nèi)存中也為全局索引維護(hù)一個(gè)R樹(shù)。

查詢(xún)過(guò)程：以上的工作做完后，系統(tǒng)收到一個(gè)查詢(xún)Q （RQ，K），將Q發(fā)送到所有空間區(qū)域與Q.RQ相交的計(jì)算節(jié)點(diǎn)中。每一個(gè)收到Q.RQ的節(jié)點(diǎn)在自己的內(nèi)存中搜索全局索引，再根據(jù)全局索引gi（ip，port，address，region）中的ip，port和address信息找到gi所在的計(jì)算節(jié)點(diǎn)中的外存中的地址，隨后在本地R樹(shù)中運(yùn)行獲取當(dāng)前查詢(xún)對(duì)應(yīng)R樹(shù)的葉子的所有STL信息。最后，利用對(duì)各個(gè)計(jì)算節(jié)點(diǎn)上的STL進(jìn)行全局的Top-K過(guò)程，得到目標(biāo)的Top-K輸出，查詢(xún)過(guò)程如圖5所示。

5? 結(jié)? 論

在空間數(shù)據(jù)量越來(lái)越大的情況下，使用分布式框架可以有效節(jié)約計(jì)算資源，靈活存儲(chǔ)數(shù)據(jù)。本文設(shè)計(jì)了基于Hilbert兩層格網(wǎng)劃分方法的分布式空間數(shù)據(jù)庫(kù)集群，并且設(shè)計(jì)了兩層索引結(jié)構(gòu)，在索引算法中充分將大量計(jì)算工作分給計(jì)算節(jié)點(diǎn)。目前給出的算法和系統(tǒng)框架在理論上可以解決空間數(shù)據(jù)庫(kù)Top-K頻繁關(guān)鍵字的問(wèn)題，具體實(shí)現(xiàn)整個(gè)系統(tǒng)并且調(diào)優(yōu)測(cè)試，還有待今后進(jìn)一步研究。

參考文獻(xiàn)：

[1] 王金寶.云計(jì)算系統(tǒng)中索引與查詢(xún)處理技術(shù)研究 [D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[2] AHMED P，HASAN M，KASHYAP A，et al. Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges [C]//Acm International Conference on Management of Data.New York，USA：ACM，2017.

[3] 李雷，李曉東，劉欣陽(yáng).分布式網(wǎng)絡(luò)中的一種高效top-k求解方法研究 [J].計(jì)算機(jī)工程與應(yīng)用，2010，46（18）：89-92.

[4] 余利峰.面向分布式空間數(shù)據(jù)庫(kù)的矢量數(shù)據(jù)存儲(chǔ)與查詢(xún)處理關(guān)鍵技術(shù)研究 [D].杭州：浙江大學(xué)，2018.

作者簡(jiǎn)介：姚遠(yuǎn)（1998.06-），男，漢族，黑龍江大慶人，就讀于計(jì)算機(jī)學(xué)院，本科在讀，主要研究方向：大數(shù)據(jù)科學(xué)。