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

在審

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

技術領域

本發明屬于云計算、大數據領域，涉及一種在分布式環境下可以有效提高查詢效率的MapReduce索引。

背景技術

MapReduce是一種目前流行的基于云平臺的編程框架，它可以處理及生成大型數據集，其利用無共享集群來支持數據密集型的應用。處理步驟具體為：在分布式緩存系統中，由MapReduce任務在處理一個鍵/值對時，是在map函數中生成一組中間鍵/值對，根據相同的中間鍵來合并所有的中間值，每個map都獨立于其他操作，即所有maps就可以并行執行。MapReduce的一組“reducers”可以執行歸約操作，具有相同key的Map操作的輸出同時可以歸約到同一個reducer。然而單獨運行一個歸約過程可能會使得效率低下；

MapReduce可用于支持比傳統的商業服務器集群更大規模的數據處理,它可以在僅僅幾小時內即可處理一個PB數量的數據，使用MapReduce進行數據索引具有較好的應用前景。然而，現有的索引算法由于不能適應MapReduce的并行處理，構建索引的時間耗費不夠理想，可擴展性不佳，因而有必要構建一種索引方法，其能夠適用于并行處理，以能夠提高檢索效率。

發明內容

為了提高現有數據查詢方法索引效率，構建一種基于分布式的時空索引方法，本發明提供如下方案:

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

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的文件系統。

在所述步驟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₁中；