[發(fā)明專利]一種基于MapReduce的度量空間相似連接處理方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201611173516.1
• 申請(qǐng)日: 2016-12-16
• 公開（公告）號(hào): CN106777133A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 高云君;楊克宇;陳璐;陳剛;陳純
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 杭州求是專利事務(wù)所有限公司33200
• 代理人: 邱啟旺

1.一種基于MapReduce的度量空間相似連接處理方法，其特征在于，該方法的步驟如下：

(1)對(duì)應(yīng)用中給定的度量空間數(shù)據(jù)集進(jìn)行隨機(jī)采樣，得到樣本數(shù)據(jù)。

(2)對(duì)得到的樣本數(shù)據(jù)進(jìn)行支樞點(diǎn)選擇。

(3)將應(yīng)用中給定的整個(gè)數(shù)據(jù)集(包括樣本數(shù)據(jù))從度量空間映射至向量空間。

(4)利用步驟(3)中得到的映射到向量空間的樣本數(shù)據(jù)構(gòu)建KD樹，得到相應(yīng)的空間劃分。

(5)在Map階段，根據(jù)步驟(4)中得到的空間劃分，對(duì)步驟(3)中得到的整個(gè)數(shù)據(jù)集進(jìn)行劃分。

(6)在Reduce階段對(duì)劃分后的數(shù)據(jù)進(jìn)行相似度計(jì)算，得到相似連接的處理結(jié)果。

2.根據(jù)權(quán)利要求1所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述步驟(2)具體為：

(2.1)在樣本數(shù)據(jù)中找出離群點(diǎn)作為支樞點(diǎn)的備選集合；

(2.2)根據(jù)支樞點(diǎn)的選擇目標(biāo)，對(duì)備選集合中的點(diǎn)進(jìn)行增量式的貪心選擇。

3.根據(jù)權(quán)利要求1所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述步驟(3)具體為：對(duì)于每一個(gè)在度量空間中的數(shù)據(jù)，計(jì)算與步驟(2)中得到的支樞點(diǎn)之間的距離，并以求得的距離作為向量空間中各維度的坐標(biāo)值，以得到度量空間數(shù)據(jù)在向量空間中的坐標(biāo)。

4.根據(jù)權(quán)利要求1所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述的步驟(4)具體為：對(duì)步驟(3)中得到的樣本數(shù)據(jù)，構(gòu)建KD樹，得到的KD樹中包含數(shù)據(jù)點(diǎn)個(gè)數(shù)相等的葉子節(jié)點(diǎn)，各葉子節(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域即為空間劃分的結(jié)果。

5.根據(jù)權(quán)利要求1所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述的步驟(5)在Map階段，將步驟(3)中得到的映射至向量空間后的整個(gè)數(shù)據(jù)集劃分至步驟(4)中得到的相應(yīng)空間劃分中去。

6.根據(jù)權(quán)利要求1所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述步驟(6)具體為：

(6.1)在Reduce階段，對(duì)于每個(gè)劃分，將各劃分內(nèi)部的數(shù)據(jù)在隨機(jī)選定的一個(gè)維度上，使用快速排序算法進(jìn)行排序整理；

(6.2)利用平面掃描法，對(duì)排序后的數(shù)據(jù)集進(jìn)行度量空間距離計(jì)算以驗(yàn)證結(jié)果，并結(jié)合區(qū)域過(guò)濾技術(shù)對(duì)距離計(jì)算進(jìn)行剪枝。

7.根據(jù)權(quán)利要求6所述的基于MapReduce的度量空間相似連接處理方法，其特征在于：所述區(qū)域過(guò)濾技術(shù)是指：若兩個(gè)數(shù)據(jù)對(duì)象在向量空間任意維度上的差值大于給定的距離閾值，則它們不可能成為最終結(jié)果，從而可以不經(jīng)過(guò)度量空間距離計(jì)算就被剪掉。