[發(fā)明專利]基于Voronoi圖的分布式時空索引方法

在審

• 申請?zhí)枺?/td>: 201710976133.6
• 申請日: 2017-10-19
• 公開（公告）號: CN107766495A
• 公開（公告）日: 2018-03-06
• 發(fā)明（設(shè)計）人: 季長清;汪祖民;劉艷;高楊;李澤宇
• 申請（專利權(quán)）人: 大連大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連智高專利事務(wù)所(特殊普通合伙)21235
• 代理人: 畢進

1.一種基于Voronoi圖的分布式時空索引方法，其特征步驟如下：

使用Spark構(gòu)建造倒排Voronoi索引，給定d維空間中兩個數(shù)據(jù)集R和S，Spark按默認機制進行分片，部分mappers同時并行運行，在Spark任務(wù)中使用默認的reducer，在啟動map函數(shù)之前，使用預(yù)聚類算法得到代表點p,并將其加載到每個map的主存中；

在每一個map處理進程中，依次利用TextInputFormat來讀取輸入的分片，TextInputFormat從文件讀取數(shù)據(jù)到Mapper的實例中，分別計算數(shù)據(jù)集R中的每一個對象r，數(shù)據(jù)集S中的每一個對象s對象與代表點p點之間的距離，并將對象r，s分配給最接近的代表點P；R中具有m個對象r，一個對象r與任意對象s的最接近的代表點都被聚集在一個Voronoi單元格中，由此產(chǎn)成m個Voronoi單元格作為分區(qū)，輸出<VCm，List(P_i)>對，給定查詢點p，判別其最鄰近的分區(qū)或最一些鄰近的分區(qū)集，mapper輸出原始數(shù)據(jù)集中的到最鄰近的分區(qū)或最鄰近的分區(qū)集的每一個對象r、s及其分區(qū)VC_m的id；將mapper輸出到Spark的文件系統(tǒng)。

2.如權(quán)利要求1所述的基于倒排泰森多邊形的分布式時空索引方法，其特征在于：Voronoi圖將一個空間劃分為多個不相交的多邊形，在每個多邊形中的某一個點的最近鄰均位于該點所在的Voronoi單元格內(nèi)，圖中的每個多邊形稱為與點p相關(guān)聯(lián)的Voronoi單元格，點p所在的單元格內(nèi)的任何點都是p的最近鄰。

3.如權(quán)利要求1所述的基于倒排泰森多邊形的分布式時空索引方法，其特征在于：倒排Voronoi索引包含兩個部分：主索引，包括所有的聚類中心；第二索引，包括儲存在每個分區(qū)VC的對像隊列。

4.如權(quán)利要求1所述的基于倒排泰森多邊形的分布式時空索引方法，其特征在于：代表點的獲取方法，確定內(nèi)部聚類點與相鄰點，將內(nèi)部聚類點的數(shù)據(jù)聚類，聚類后選出聚類中心進行索引，所需數(shù)據(jù)為與內(nèi)部聚類點連接的相鄰點，以這個內(nèi)部聚類點為圓心，包含相鄰的聚類中心點建立圓，以這個圓為外接圓的三角形作為Delaunay三角形，本方法中將兩個不同的內(nèi)部聚類點分別建立Delaunay三角形，這兩個Delaunay三角形以相鄰點為共同點建立Delaunay三角網(wǎng)，將數(shù)據(jù)對象分割為幾個大分區(qū)，選擇其中一聚類代表點成為代表點，被劃分的每個對象以被聚類在一個Voronoi單元中，每個Voronoi網(wǎng)格中含有對象id。

5.如權(quán)利要求4所述的基于倒排泰森多邊形的分布式時空索引方法，其特征在于：Voronoi圖由VD(p)＝{V(p₁),V(p₂),...,V(p_m)}，其中：VD(p)是關(guān)于P的Voronoi圖合集，V(p₁)是p1的Voronoi圖，給出的與所有的點相關(guān)聯(lián)的集合，被稱為p產(chǎn)生的遵循距離函數(shù)Dist()的Voronoi圖，這里每個p點的Voronoi圖一定包括比其他任何點更接近q的所有點，因而一個查詢點q的近鄰是閉合的Voronoi圖；

Voronoi單元在空間R上，從D維空間中劃分出一個包含n個點的區(qū)域，即P:{p₁,p₂,…,p_n}，分區(qū)VC給出的區(qū)域，即VC分區(qū)關(guān)于點p_i的區(qū)域VC(p_i)，若滿足VC(p_i)＝p|d(p,p_i)≤(p,p_j)，則該區(qū)域被稱為與p相關(guān)聯(lián)的Voronoi單元；

其中：其中p是指定點或查詢點，d(p,p_i)是p和p_i之間的最小歐氏距離，i、j是變量，n≥2，p₁≠p₂，i≠j，i,j∈I_n＝1,..,n，且i取遍1,..,n中的所有值，每取一值時，j取遍1,..,n中除了此時的i取值的所有值。