劉義

一種基于序列計(jì)算的最近似K對(duì)數(shù)據(jù)搜索方案

劉義

多種應(yīng)用場合需要尋找給定數(shù)據(jù)庫中相似度最大的前k對(duì)數(shù)據(jù)。然而，由于應(yīng)用領(lǐng)域需要處理的數(shù)據(jù)規(guī)模呈上升趨勢，計(jì)算這樣的最相似k對(duì)數(shù)據(jù)，難度非常大。提出了一種基于序列計(jì)算的最相似k對(duì)數(shù)據(jù)搜索方案，首先，將所有數(shù)據(jù)對(duì)分割成多個(gè)組，然后，提出了所有數(shù)據(jù)對(duì)分組算法和核心數(shù)據(jù)對(duì)分組算法，通過單獨(dú)計(jì)算每個(gè)組中的最近似k對(duì)數(shù)據(jù)，從所有組的最近似k對(duì)數(shù)據(jù)中選擇相似度最高的k對(duì)數(shù)據(jù)，進(jìn)而正確地確定最近似k對(duì)數(shù)據(jù)。最后基于合成數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，性能評(píng)估結(jié)果驗(yàn)證了本文算法的有效性和可擴(kuò)展性。

數(shù)據(jù)庫；相似度；序列計(jì)算；數(shù)據(jù)搜索；分組

0 引言

在分子生物學(xué)、醫(yī)療成像和時(shí)序分析等諸多應(yīng)用中，經(jīng)常需要檢測出哪些數(shù)據(jù)的相似度較高[1]。這些應(yīng)用領(lǐng)域首先需要從原始對(duì)象中提取出多維向量（又稱為特征），然后存儲(chǔ)于數(shù)據(jù)庫中以進(jìn)行相似度檢索。最近人們發(fā)現(xiàn)，可以基于單次相似度搜索來代替大量的相似度檢索來處理多維數(shù)據(jù)庫相似度搜索和數(shù)據(jù)挖掘算法。比如，采用分層聚類算法[2]，在開始時(shí)將每個(gè)點(diǎn)都看成是一個(gè)聚類，然后基于距離函數(shù)（如歐幾里德距離或曼哈頓距離）計(jì)算相似度，進(jìn)而獲得最相似的聚類，它們被不斷合并，直到我們獲得了所需數(shù)量的聚類。

基于相似度的方法的主要缺點(diǎn)在于，給定一個(gè)相似度函數(shù)后，相似數(shù)據(jù)搜索函數(shù)需要用戶提供最小相似度閾值。然而，因?yàn)殚撝蹬c應(yīng)用場合有關(guān)，所以許多應(yīng)用情況下該閾值難以事先確定。更可行的方案是按相似度降序排列，計(jì)算最相似的k對(duì)數(shù)據(jù)。與傳統(tǒng)的相似數(shù)據(jù)搜索方法相反，最相似k對(duì)數(shù)據(jù)搜索不需要我們提供最小相似度閾值。為此，本文研究了基于序列計(jì)算的最近似k對(duì)數(shù)據(jù)并行搜索方案。

1 相關(guān)工作

最近似數(shù)據(jù)對(duì)搜索問題是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)問題之一，相繼有眾多的研究者對(duì)此問題展開了深入廣泛的研究，例如，Corral等人[4]提出了空間數(shù)據(jù)庫的最近似k對(duì)數(shù)據(jù)搜索算法，以克服考察所有數(shù)據(jù)對(duì)的盲目搜索算法帶來的二次方復(fù)雜度。他們的算法針對(duì)空間和低維數(shù)據(jù)進(jìn)行了專門改進(jìn)，使用了R -樹等高效的基于spatial disk索引技術(shù)； 設(shè)有n個(gè)d維數(shù)據(jù)，Pereira等人[5]提出了基于分治法的二維數(shù)據(jù)相似性查詢算法，其計(jì)算復(fù)雜度為；Yang等人[6]提出了處理高維數(shù)據(jù)的相似性查詢算法，其計(jì)算復(fù)雜度為；Salowe[7]和Lenhof[8]等人都分別提出了最近似k對(duì)數(shù)據(jù)搜尋算法，其中文獻(xiàn)[7]得出的L∞距離的計(jì)算復(fù)雜度為；文獻(xiàn)[9,10]提出了二維數(shù)據(jù)搜索算法。其中，文獻(xiàn)[9]通過Voronoi圖來反復(fù)降低搜索空間，而文獻(xiàn)[10]使用R-樹索引對(duì)樹進(jìn)行高效修剪。然而當(dāng)增加數(shù)據(jù)維度d時(shí)，這些數(shù)據(jù)的計(jì)算復(fù)雜度均會(huì)呈指數(shù)上升。

另外，文獻(xiàn)[11,12]分別提出了基于閾值的相似數(shù)據(jù)搜索算法，這些算法使用倒排索引進(jìn)行數(shù)據(jù)修剪；為了利用Jaccard系數(shù)、余弦距離和重疊相似度等相似度指標(biāo)進(jìn)行最近似k對(duì)數(shù)據(jù)查詢，文獻(xiàn)[13]提出了一種基于反轉(zhuǎn)列表的搜索算法。然而，這些算法都假設(shè)所有數(shù)據(jù)均可存儲(chǔ)于主存儲(chǔ)器中，對(duì)大型數(shù)據(jù)不具有可行性。為了實(shí)現(xiàn)相似數(shù)據(jù)并行搜索，Vernica等人[14]通過對(duì)文獻(xiàn)[13]中的PPJoin+算法進(jìn)行拓展，提出了基于MapReduce的新算法。然而，該算法只適用于集合數(shù)據(jù)，難以推廣到本文多維數(shù)據(jù)最近似k對(duì)數(shù)據(jù)搜索問題。鑒于此，本文在現(xiàn)有工作的基礎(chǔ)上，提出了一種基于序列計(jì)算的最近似K對(duì)數(shù)據(jù)搜索算法，并通過仿真實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

2 問題描述

3 基于序列計(jì)算的最相似k對(duì)數(shù)據(jù)搜索算法

對(duì)最相似k對(duì)數(shù)據(jù)搜索問題，盲目搜索算法TopK-B[14]計(jì)算每一對(duì)數(shù)據(jù)點(diǎn)的距離，計(jì)算復(fù)雜度為O( d?log k? n2)。本節(jié)基于分而治之和分支-定界的思想，提出了兩種新的數(shù)據(jù)搜索算法，下面將詳細(xì)闡述。

3.1 TopK-D：分而治之算法

我們對(duì)文獻(xiàn)[15]中只能搜索一組最近似數(shù)據(jù)對(duì)的分而治之算法進(jìn)行改進(jìn)，并將經(jīng)過改進(jìn)的最近似k對(duì)數(shù)據(jù)搜索算法稱為TopK-D算法。

給定數(shù)據(jù)點(diǎn)D，我們利用超平面分割D中的數(shù)據(jù)點(diǎn)，重復(fù)搜索每邊最近似k對(duì)數(shù)據(jù)。為了計(jì)算橫跨超平面數(shù)據(jù)對(duì)的距離，文獻(xiàn)[15]中的算法基于下一分割維度調(diào)用迭代過程，直到只剩下一個(gè)維度未被分割，此時(shí)當(dāng)我們計(jì)算橫跨超平面數(shù)據(jù)對(duì)的距離時(shí)對(duì)每個(gè)數(shù)據(jù)點(diǎn)只需考慮固定數(shù)量的距離計(jì)算任務(wù)即可。在計(jì)算d維數(shù)據(jù)最相似數(shù)據(jù)對(duì)時(shí)，文獻(xiàn)[15]已經(jīng)證明，當(dāng)我們計(jì)算橫跨超平面數(shù)據(jù)對(duì)的距離時(shí)，每一對(duì)數(shù)據(jù)的距離大于最近距離的數(shù)據(jù)點(diǎn)數(shù)量有O(4d)個(gè)。因此，當(dāng)我們搜索最近似k對(duì)數(shù)據(jù)時(shí)，對(duì)每一數(shù)據(jù)點(diǎn)p，我們可以保證，有O( k+4d)個(gè)數(shù)據(jù)點(diǎn)距離p點(diǎn)距離小于等于第k對(duì)最相近數(shù)據(jù)對(duì)的距離。

TopK-D算法的偽代碼如圖1所示：

圖1 TopK-D算法步驟

遞歸函數(shù)的輸入為數(shù)據(jù)點(diǎn)分組時(shí)的維度m，k，(d?m+1)個(gè)數(shù)組Xm,...,Xd。所有數(shù)組Xi（m≤i≤d）包含相同的數(shù)據(jù)點(diǎn)，根據(jù)數(shù)據(jù)點(diǎn)的第i個(gè)坐標(biāo)進(jìn)行排序。首先，TopK-D算法檢查邊界條件是否小于等于2。如果條件滿足，就返回該對(duì)數(shù)據(jù)。否則，算法將輸入數(shù)據(jù)點(diǎn)分割成兩部分，對(duì)每部分重復(fù)調(diào)用自身函數(shù)。在第6-9行，我們將每個(gè)數(shù)組Xi分割成大小相同的兩個(gè)數(shù)組和且中的數(shù)據(jù)點(diǎn)在xm=l超平面的左邊，在xm=l超平面的右邊。

設(shè)H和δ分別是xm=l每一邊重復(fù)調(diào)用函數(shù)所返回的數(shù)據(jù)對(duì)和H中第k組最相似數(shù)據(jù)對(duì)的距離?，F(xiàn)在我們將要針對(duì)第m個(gè)坐標(biāo)與l的距離小于δ的數(shù)據(jù)點(diǎn)重復(fù)調(diào)用自身，以計(jì)算橫跨xm=l的數(shù)據(jù)對(duì)距離。設(shè)Bi（m≤i≤d）是第m個(gè)坐標(biāo)在[l?δ,l+δ]范圍內(nèi)的數(shù)據(jù)點(diǎn)，且Bi按照第i個(gè)坐標(biāo)升序排列。遞歸調(diào)用以m+1，k和Bi（m+1≤i≤d ）為輸入。當(dāng)m+1=d時(shí)，我們沿著最后一個(gè)坐標(biāo)的數(shù)組使用滑動(dòng)窗口來計(jì)算距離。

時(shí)間復(fù)雜度：設(shè)每次遞歸時(shí)有n個(gè)數(shù)據(jù)點(diǎn)且分割維度為m，第6-9行分割(d?m+1)個(gè)數(shù)組Xm,...,Xd需要耗時(shí)O( d? n)，第28-30行選擇范圍在[l?δ,l+δ]內(nèi)的數(shù)據(jù)點(diǎn)需要耗時(shí)O( d? n)。因?yàn)槊看芜f歸調(diào)用兩次遞歸函數(shù)時(shí)以n/2個(gè)數(shù)據(jù)點(diǎn)和第p個(gè)分割維度為輸入，調(diào)用其他遞歸函數(shù)時(shí)以O(shè)( n)個(gè)數(shù)據(jù)點(diǎn)和p?1個(gè)分割維度為輸入，遞歸操作耗時(shí)為T( n, p)=2T( n/2,p)+O( d? n)+T( n, p ?1)。在第1行，n=2時(shí)的邊界條件是T(2,p)=Θ(1)；在第15-27行，因?yàn)槲覀儺?dāng)m+1=d時(shí)有p=2，滿足的邊界條件是T( n,2)=O(logk?(k+4d)?n)。有了遞歸和邊界條件，我們有T( n)=O(logk?(k+4d)?n(logn)d?1)，該遞歸問題的解見文獻(xiàn)[16]。

3.2 TopK-T: 分支-限界算法

本節(jié)我們將提出另一種最相似k對(duì)數(shù)據(jù)搜索算法TopK-T。在該算法中，我們不是存儲(chǔ)LlS，而是利用空間為Θ(n)的最小堆QlS，以便我們可準(zhǔn)確按照訪問LlS的次序挨個(gè)訪問下一最相似數(shù)據(jù)對(duì)。于是，我們只將每個(gè)數(shù)據(jù)點(diǎn)的下一最相似數(shù)據(jù)對(duì)存儲(chǔ)到最小堆Ql中。當(dāng)我們把點(diǎn)pi的最相似數(shù)據(jù)對(duì)從Ql中提取并刪除時(shí)，我們將再次插入點(diǎn)pi的下一最相似數(shù)據(jù)對(duì)。

對(duì)每個(gè)維度l，我們首先按照D中數(shù)據(jù)點(diǎn)第l個(gè)坐標(biāo)創(chuàng)建所有數(shù)據(jù)點(diǎn)升序列表Sl。設(shè)Sl[i ]是列表Sl第l個(gè)坐標(biāo)的第i個(gè)點(diǎn)，Sl[i ](l)是Sl[i ]的第l個(gè)坐標(biāo)。當(dāng)我們剛開始創(chuàng)建最小堆Ql時(shí)，對(duì)每個(gè)點(diǎn)Sl[i ]（1≤i≤n?1），我們把

堆使用的鍵。請(qǐng)注意，如果對(duì)Ll中的每一對(duì)數(shù)據(jù)pi,pj∈D施加條件i＜j，則從第i個(gè)坐標(biāo)距離角度來說，在Sl[i ]的所有不同數(shù)據(jù)對(duì)中，Sl[i+1]是數(shù)據(jù)點(diǎn)Sl[i ]的最相似近鄰。

當(dāng)我們每次迭代把最上面元素(dist, p, q)從最小堆Ql中刪除時(shí)，被使用的數(shù)據(jù)對(duì)Sl[p]和Sl[q ]似乎是Ll中基于第l個(gè)坐標(biāo)的下一最相似數(shù)據(jù)對(duì)。于是，考慮到Sl[q+1]是Sl[p ]出現(xiàn)在Sl[p ]之后的下一最相似數(shù)據(jù)點(diǎn)，Sl[p ]作為

TopK-T算法的偽代碼如圖2所示：

圖2 TopK-T算法步驟

TopK-T算法開始時(shí)對(duì)空最大堆TOPk初始化，保存最相似的k對(duì)數(shù)據(jù)。對(duì)1≤l≤d的第l個(gè)坐標(biāo)，我們首先根據(jù)l坐標(biāo)對(duì)D中的每個(gè)數(shù)據(jù)創(chuàng)建有序數(shù)組Sl；對(duì)1≤i≤n?1的每個(gè)i，通過插入數(shù)組(Sl[i](l)?Sl[i+1](l),i, i +1)來創(chuàng)建最小堆Ql。While循環(huán)迭代一直持續(xù)到TOPk中有至少k對(duì)數(shù)據(jù)為止，且TOPk中第k對(duì)最相似數(shù)據(jù)的最大距離只能為未知數(shù)據(jù)對(duì)的距離下限T。當(dāng)Ql沒有更多元素時(shí)也可以停止循環(huán)。通過調(diào)用GetMaxDistance(TOPk)，獲得TOPk中第k對(duì)最相似數(shù)據(jù)的距離。每次While循環(huán)時(shí)，我們首先調(diào)用>PopMin( Ql)，從Ql中提取出最上端的數(shù)組(Sl[p](l)?Sl[q](l),p, q )并將其從Ql中刪除，用Sl[p](l)?Sl[q ](l)來更新ul，然后用ul更新T。此時(shí)，由于第l坐標(biāo)與Sl[p ](l)最相似的下一數(shù)據(jù)點(diǎn)是Sl[q+1]，只要q+1≤n條件滿足，我們就將(Sl[p](l)?Sl[q+1](l),p, q +1)插入Ql。如果我們退出while循環(huán)，則TOPk中的數(shù)據(jù)對(duì)就可作為最相似k對(duì)數(shù)據(jù)如圖3所示：

(a) D (b)有序數(shù)組圖3 TopK-T算法的數(shù)據(jù)和有序數(shù)組示例

例如，考慮圖3(a)中的數(shù)據(jù)集合D。假設(shè)我們想得出D中歐氏距離最相似的兩對(duì)數(shù)據(jù)。我們首先生成列表S1, S2,S3，如圖3(b)。初始時(shí)，對(duì)D中的每個(gè)數(shù)據(jù)p，Qi保存了點(diǎn)p與Si中下一個(gè)數(shù)據(jù)點(diǎn)的第i個(gè)坐標(biāo)差值。于是，Q1為{(0.01,4,5),(0.02,5,6),(0.2,2,3),(0.24,1,2),(0.26,3,4)}。例如，Q1包含(0.01,4,5)是因?yàn)閜5在S1中的數(shù)組下標(biāo)是4，p5的下一數(shù)據(jù)點(diǎn)是p1，p1在S1中的數(shù)組下標(biāo)是5。第一次訪問Q1返回第一個(gè)坐標(biāo)值之差為0.01的數(shù)據(jù)對(duì)(p5,p1)。(p5,p1)的距離計(jì)算后為0.02，我們將該對(duì)數(shù)據(jù)插入TOPk。因?yàn)閜6在S1中排在p1之后，我們選擇加入Q1的對(duì)象不是剛從Q1中提取出來的(p5,p1)，而是數(shù)據(jù)對(duì)(p5,p6)的值(0.03,4,6)。首次訪問Q1后，T為0.01。下次訪問Q2返回?cái)?shù)據(jù)對(duì)(p6,p1)的(0.01,3,4)，距離為。數(shù)據(jù)對(duì)插入TOPk，且對(duì)數(shù)據(jù)對(duì)(p6,p5)，(0.01,3,5)插入Q2，理由是p5在列表中位于p1之后。因?yàn)門OPk中有兩對(duì)數(shù)據(jù)而且第2對(duì)數(shù)據(jù)的距離大于，我們繼續(xù)執(zhí)行while循環(huán)。對(duì)下次訪問，我們返回Q1，用類似方法繼續(xù)執(zhí)行迭代步驟。在第7次訪問時(shí)，我們從Q1中得到數(shù)據(jù)對(duì)(p,p)，且。當(dāng)前TOPk中的第2對(duì)最相近數(shù)據(jù)是距離為的數(shù)據(jù)對(duì)(p1, p6)。因?yàn)門大于TOPk中第2對(duì)最相近數(shù)據(jù)的距離，我們停止while循環(huán)。最后，兩對(duì)最相似數(shù)據(jù)是(p1,p5)和(p1,p6)。

時(shí)間復(fù)雜度：每次迭代計(jì)算新數(shù)據(jù)對(duì)距離和更新Ql時(shí)，需要耗時(shí)O( d+logk+log n)。LlS的總大小為O( dn2)，訪問LlS的所有元素時(shí)TopK-T算法的時(shí)間復(fù)雜度為O( d2n2+dn2logk+dn2log n)。

綜上所述，為了在每次分組時(shí)用化簡函數(shù)找出最相似k對(duì)數(shù)據(jù)，我們可以使用TopK-B (盲目搜索)，TopK-D (分而治之) 或TopK-T(分支-邊界)算法中的任意一種。當(dāng)我們?cè)趥鹘y(tǒng)背景下只使用一臺(tái)機(jī)器時(shí)，我們有兩種選擇，要么不進(jìn)行分組，要么進(jìn)行核心數(shù)據(jù)對(duì)分組。于是，我們有6種算法組合如見圖4所示：

圖4 不同算法示例

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

本節(jié)對(duì)本文算法進(jìn)行性能評(píng)估。所有實(shí)驗(yàn)基于20個(gè)節(jié)點(diǎn)集群，配置Intel(R) Core(TM)2 Duo CPU 2.66GHz 2GB內(nèi)存，Linux操作系統(tǒng)。所有算法用Java編譯器1.6實(shí)現(xiàn)。所有實(shí)驗(yàn)使用歐氏距離作為距離度量。本節(jié)圖形以對(duì)數(shù)標(biāo)度來顯示運(yùn)行時(shí)間。實(shí)驗(yàn)數(shù)據(jù)采用合成數(shù)據(jù)，我們生成的合成數(shù)據(jù)在每一維上的數(shù)值均為實(shí)數(shù)且在0和1之間。為了生成逼真的合成數(shù)據(jù)集，我們讓合成數(shù)據(jù)遵守Zipfian分布，如文獻(xiàn)[17]所示，包含距離小于0.01的數(shù)據(jù)對(duì)的數(shù)據(jù)集群規(guī)模服從Zipfian分布，其中x是規(guī)模的秩，γ是確定數(shù)據(jù)點(diǎn)分布的參數(shù)。我們以γ=1.5默認(rèn)值生成合成數(shù)據(jù)。此外，我們生成10和20維多種合成數(shù)據(jù)集，數(shù)據(jù)點(diǎn)數(shù)量從10,000 增加至10,000,000，生成數(shù)據(jù)的體積從95 MB 上升至3.8 GB。我們還將含有1,000,000個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集的維度從2維增加至100維。

4.2 實(shí)驗(yàn)結(jié)果

TopK-B, TopK-D,TopK-T,TopKFB,TopK-FD和TopK-FT算法的性能，如圖5所示：

圖5 不同算法的實(shí)驗(yàn)結(jié)果對(duì)比

這些算法是沒有運(yùn)用MapReduce技術(shù)的主存儲(chǔ)器算法。默認(rèn)參數(shù)為：數(shù)據(jù)點(diǎn)數(shù)量n=50,000，維度數(shù)量d=10，擬搜索的最相似數(shù)據(jù)對(duì)數(shù)量k=50。對(duì)核心數(shù)據(jù)對(duì)分組，我們使用默認(rèn)參數(shù)r=60，該值是每一維度區(qū)間的數(shù)量。

改變參數(shù)n：我們將參數(shù)n從5000增加至100,000，運(yùn)行時(shí)間見圖5（a）。當(dāng)數(shù)據(jù)點(diǎn)規(guī)模范圍在10000到20000之間時(shí)，TopK-T的性能最優(yōu)。然而，當(dāng)數(shù)據(jù)規(guī)模大于20000時(shí)，TopK-FT的性能最優(yōu)，且速度是TopK-T的2倍。此外，當(dāng)數(shù)據(jù)規(guī)模大于50000時(shí)，TopK-FB的性能優(yōu)于TopK-T。因此，我們可以看出，本文核心數(shù)據(jù)對(duì)分組策略搜索到最相似k對(duì)數(shù)據(jù)的效率非常高。

改變參數(shù)d：下面實(shí)驗(yàn)中，我們將維數(shù)d從2維增加至100維。圖5（b）給出了運(yùn)行時(shí)間。d＞10時(shí)算法TopK-D和TopK-FD的運(yùn)行時(shí)間超過2小時(shí)，所以本文沒有給出它們運(yùn)行時(shí)間曲線。對(duì)于維度d為2-10維的數(shù)據(jù)集合，TopK-T的速度最快。然而，當(dāng)d從10增加至100時(shí)，TopK-T的運(yùn)行時(shí)間迅速上升。當(dāng)50≤d時(shí)TopK-FB的速度是TopK-T的1.5倍。這一結(jié)果表明，低維數(shù)據(jù)最應(yīng)選用TopK-T算法，且核心數(shù)據(jù)對(duì)分組對(duì)高維數(shù)據(jù)非常有效。

改變參數(shù)k：當(dāng)k從2增加至100時(shí)，我們?cè)趫D5（c）中繪出了算法的運(yùn)行時(shí)間。當(dāng)k變化較大時(shí)，TopK-FT的性能最優(yōu)。在k的所有區(qū)間上，TopK-FT的速度大約是TopK-B的40倍，是TopK-D的5倍。因此，我們可以看出，核心數(shù)據(jù)對(duì)分組非常高效，且TopK-FT和TopK-FB基本不受參數(shù)k的影響。

5 總結(jié)

多種應(yīng)用場合需要尋找給定數(shù)據(jù)庫中相似度最大的前k對(duì)數(shù)據(jù)。然而，計(jì)算這樣的最相似k對(duì)數(shù)據(jù)，難度非常大，因?yàn)閼?yīng)用領(lǐng)域需要處理的數(shù)據(jù)規(guī)模呈上升趨勢。.本文研究了基于序列計(jì)算的最相似k對(duì)數(shù)據(jù)搜索問題，提出了一種新的算法用于最相似k對(duì)數(shù)據(jù)搜索，最后通過實(shí)驗(yàn)結(jié)果證明了本文方案的有效性和可拓展性。我們下一步工作的重點(diǎn)是將MapReduce技術(shù)用于大數(shù)據(jù)處理中，研究一種用于大數(shù)據(jù)分析服務(wù)的啟發(fā)式云爆發(fā)算法。

[1] B?hm C, Braunmüller B, Krebs F, et al. Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data[C]. ACM SIGMOD Record. ACM, 2001, 30(2): 379-388

[2] 李朝鵬，李肯立，成運(yùn)，李朝建. 基于數(shù)據(jù)預(yù)處理的并行分層聚類算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2010,27（1）: 71-73

[3] Lee K H, Lee Y J, Choi H, et al. Parallel data processing with MapReduce: a survey[J]. ACM SIGMOD Record, 2012, 40(4): 11-20

[4] Corral A, Manolopoulos Y, Theodoridis Y, et al. Algorithms for processing K-closest-pair queries in spatial databases [J]. Data & Knowledge Engineering, 2004, 49(1): 67-104

[5] Pereira J C, Lobo F G. An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case [J]. Journal of Computer Science and Technology, 2012, 27(4): 891-896

[6] Yang S W, Choi Y, Jung C K. A divide-and-conquer Delaunay triangulation algorithm with a vertex array and flip operations in two-dimensional space [J]. International Journal of Precision Engineering and Manufacturing, 2011, 12(3): 435-442

[7] Salowe J S. Enumerating interdistances in space [J]. International Journal of Computational Geometry & Applications, 1992, 2(01): 49-59

[8] Lenhof H P, Smid M. Sequential and parallel algorithms for the k closest pairs problem [J]. International Journal of Computational Geometry & Applications, 1995, 5(03): 273-288

[9] Katoh N, Iwano K. Finding k farthest pairs and k closest farthest bichromatic pairs for points in the plane[C]. Proceedings of the eighth annual symposium on Computational geometry. ACM, 1992: 320-329

[10] Qi S, Bouros P, Mamoulis N. Efficient Top-k Spatial Distance Joins [M]. Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg, 2013: 1-18

[11] Chaudhuri S, Ganti V, Kaushik R. A primitive operator for similarity joins in data cleaning[C]. Data Engineering, 2006. ICDE'06. Proceedings of the 22nd International Conference on. IEEE, 2006: 5-10

[12] Sarawagi S, Kirpal A. Efficient set joins on similarity predicates[C]. Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM, 2004: 743-754

[13] Xiao C, Wang W, Lin X, et al. Efficient similarity joins for near-duplicate detection[J]. ACM Transactions on Database Systems (TODS), 2011, 36(3): 15

[14] Vernica R, Carey M J, Li C. Efficient parallel set-similarity joins using MapReduce[C]. Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 2010: 495-506

[15] Bentley J L, Shamos M I. Divide-and-conquer in multidimensional space[C]. Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976: 220-230

[16] Monier L. Combinatorial solutions of multidimensional divide-and-conquer recurrences [J]. Journal of Algorithms, 1980, 1(1): 60-74

[17] Palmer C R, Faloutsos C. Density biased sampling: an improved method for data mining and clustering [M]. ACM, 2000

The Top-K Closest Pairs of Data Search Scheme Based on Serial Computation

Liu Yi
(Dalian Vocational & Technical College, Dalian116035, China)

There is a wide range of applications that require finding the top-k most similar pairs of records in a given database. However, computing such top-k similarity joins is a challenging problem today, as there is an increasing trend of applications that expect to deal with vast amounts of data. This paper proposes a top-k closest pairs data search scheme based on serial computation, firstly, the proposed scheme splits conceptually all pairs of points into partitions, and then the all pair partitioning and the essential pair partitioning methods are proposed, we can correctly find the top-k closest pairs by computing the top-k closest pairs in each partition separately and selecting the top-k closest pairs among the top-k closest pairs from all partitions. We finally perform the experiments with the synthetic datasets. Our performance study confirms the effectiveness and scalability of our algorithms.

Database; Similarity; Serial Computation; Data Search; Partitioning

TP391

A

2014.06.06）

劉義（1973-），男，漢族，遼寧建昌人，大連職業(yè)技術(shù)學(xué)院，碩士，講師，主要研究方向：數(shù)據(jù)挖掘，網(wǎng)絡(luò)安全，大連，116035

1007-757X(2014)08-0037-05