[發明專利]構建倒排泰森多邊形的分布式索引方法

在審

• 申請號: 201710975997.6
• 申請日: 2017-10-19
• 公開（公告）號: CN107741983A
• 公開（公告）日: 2018-02-27
• 發明（設計）人: 季長清;秦靜;汪祖民;金錫哲;劉暢;吳銳
• 申請（專利權）人: 大連大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連智高專利事務所(特殊普通合伙)21235
• 代理人: 畢進

1.一種構建倒排泰森多邊形的分布式索引方法，其特征步驟如下：

S1.d維空間中給定兩個數據集R和S，Hadoop進行分片，部分mappers同時并行運行，在MapReduce任務中，使用默認的reducer，在啟動map函數之前，使用預聚類算法得到代表點p,并加載到每個map的主存中；

S2.在每一個map處理進程中，依次利用TextInputForma來讀取輸入的分片，TextInputFormat從文件讀取數據到Mapper的實例中，分別計算數據集R中的m個對象r與各代表點p之間的距離、數據集S中的n個對象s與代表點p之間的距離，并將距離數據集R中的第i個對象r與數據集S中的第j個對象s_j的最接近的代表點P_ij選出并聚集在Voronoi單元格VC_i中，形成m個VC的分區VC1～VCm，所述的i順序取遍1～m，并且，當i順序取1～m中的一個具體值時，在i的該值下，j順序取遍1～n的所有值，得到m個存儲最接近的代表點的Voronoi單元格；輸出<VC_i，List(P_ij)>對；

已知查詢點p，判別其最鄰近的VC_i或最一些鄰近的VC_i集，由mapper輸出所述最鄰近的VC_i或最一些鄰近的VC_i集對應的原始數據集R和/或S中的r、s對象，并輸出最鄰近的VC_i或最一些鄰近的VC_i集的id；

S3.將mapper輸出到Hadoop的文件系統。

2.如權利要求1所述的構建倒排泰森多邊形的分布式索引方法，其特征在于，在所述步驟S2中，所述的將距離數據集R中的第i個對象r與數據集S中的第j個對象s_j的最接近的代表點P_ij選出并聚集在Voronoi單元格VC_i中，形成m個VC的分區VC1～VCm的過程如下：

數據集R中第一個對象r₁與數據集S中的第一個對象s₁的最接近的代表點為P₁₁，數據集R中第一個對象r₁與數據集S中的第二個對象s₂的最接近的代表點為P₁₂，……，數據集R中第一個對象r₁與數據集S中的第n個對象s_n的最接近的代表點為P_1n，該n個最接近的代表點選出并聚集在Voronoi單元格V₁中；

數據集R中第一個對象r₁與數據集S中的第一個對象s₁的最接近的代表點為P₁₁，數據集R中第一個對象r₁與數據集S中的第二個對象s₂的最接近的代表點為P₁₂，……，數據集R中第一個對象r₁與數據集S中的第n個對象s_n的最接近的代表點為P_1n，該n個最接近的代表點選出并聚集在Voronoi單元格V₁中；

……

數據集R中第m個對象r_m與數據集S中的第一個對象s₁的最接近的代表點為P_m1，數據集R中第m個對象r_m與數據集S中的第二個對象s₂的最接近的代表點為P_m2，……，數據集R中第m個對象r_m與數據集S中的第n個對象s_n的最接近的代表點為P_mn，該n個最接近的代表點選出并聚集在Voronoi單元格V_m中。

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