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

在審

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

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)數(shù)據(jù)庫領(lǐng)域中度量空間下的連接處理技術(shù)，特別是涉及一種基于MapReduce的度量空間相似連接處理方法。

背景技術(shù)

度量空間相似連接是指：在給定的度量空間中兩個(gè)數(shù)據(jù)集之間的笛卡爾積中找到所有相似性高于(或者距離小于)給定閾值的數(shù)據(jù)對。度量空間相似連接處理被廣泛地應(yīng)用在社會(huì)的各個(gè)領(lǐng)域中，其中包括重復(fù)數(shù)據(jù)檢測和刪除。

隨著以社交網(wǎng)絡(luò)、電子商務(wù)為代表的新型信息發(fā)布方式的不斷涌現(xiàn)，以及云計(jì)算、物聯(lián)網(wǎng)計(jì)算機(jī)技術(shù)的興起，數(shù)據(jù)正以前所未有的速度不斷地增長和累積，隨之而來是以MapReduce為代表的各類大數(shù)據(jù)分布式系統(tǒng)蓬勃發(fā)展，大數(shù)據(jù)的時(shí)代已經(jīng)到來。在這樣一個(gè)大數(shù)據(jù)時(shí)代，傳統(tǒng)集中式的相似連接算法已經(jīng)漸漸滿足不了當(dāng)前快速地對海量數(shù)據(jù)進(jìn)行重復(fù)數(shù)據(jù)檢測和刪除的要求。因此，設(shè)計(jì)一個(gè)具有高可擴(kuò)展性、高效率的分布式相似連接處理方法成為了學(xué)術(shù)界與工業(yè)界的迫切需求。

針對基于MapReduce的度量空間相似連接處理方法，目前國內(nèi)外學(xué)者已經(jīng)做出了一些工作。其中，最具代表性的算法是基于球形劃分技術(shù)的MAPSS方法和基于二分超平面劃分技術(shù)的ClusterJoin方法。然而，這些方法主要有兩個(gè)缺陷：(1)這些方法隨機(jī)地選擇劃分的中心點(diǎn)，這可能導(dǎo)致數(shù)據(jù)劃分不均衡，需要對數(shù)據(jù)進(jìn)行進(jìn)一步的重劃分；(2)這些方法只關(guān)注數(shù)據(jù)劃分方案，而忽略了數(shù)據(jù)劃分完成后，對各劃分內(nèi)部數(shù)據(jù)之間進(jìn)行相似度計(jì)算時(shí)，設(shè)計(jì)剪枝策略以提高效率的方式。我們的方法很好地彌補(bǔ)了上述兩個(gè)缺陷，提升了相似連接處理的效率，高效地對重復(fù)數(shù)據(jù)進(jìn)行檢測和刪除。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)的不足，本發(fā)明提供一種基于MapReduce的度量空間相似連接處理方法，該方法基于MapReduce分布式計(jì)算框架，先在Map階段對給定的數(shù)據(jù)集進(jìn)行劃分，而后在Reduce階段進(jìn)行相似性計(jì)算以得到重復(fù)數(shù)據(jù)結(jié)果，進(jìn)而進(jìn)行刪除。

為了達(dá)到上述目的，本發(fā)明所采用技術(shù)方案如下：一種基于MapReduce的度量空間相似連接處理方法，具體包括如下步驟：一種基于MapReduce的度量空間相似連接處理方法，該方法的步驟如下：

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

(2)對得到的樣本數(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)中得到的空間劃分，對步驟(3)中得到的整個(gè)數(shù)據(jù)集進(jìn)行劃分；

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

進(jìn)一步的，所述步驟(2)具體為：

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

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

進(jìn)一步的，所述步驟(3)具體為：對于每一個(gè)在度量空間中的數(shù)據(jù)，計(jì)算與步驟(2)中得到的支樞點(diǎn)之間的距離，并以求得的距離作為向量空間中各維度的坐標(biāo)值，以得到度量空間數(shù)據(jù)在向量空間中的坐標(biāo)。

進(jìn)一步的，所述的步驟(4)具體為：對步驟(3)中得到的樣本數(shù)據(jù)，構(gòu)建KD樹，得到的KD樹中包含數(shù)據(jù)點(diǎn)個(gè)數(shù)相等的葉子節(jié)點(diǎn)，各葉子節(jié)點(diǎn)對應(yīng)的空間區(qū)域即為空間劃分的結(jié)果。

進(jìn)一步的，所述的步驟(5)在Map階段，將步驟(3)中得到的映射至向量空間后的整個(gè)數(shù)據(jù)集劃分至步驟(4)中得到的相應(yīng)空間劃分中去。

進(jìn)一步的，所述步驟(6)具體為：

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

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

進(jìn)一步的，所述區(qū)域過濾技術(shù)是指：若兩個(gè)數(shù)據(jù)對象在向量空間任意維度上的差值大于給定的距離閾值，則它們不可能成為最終結(jié)果，從而可以不經(jīng)過度量空間距離計(jì)算就被剪掉。