基于卡方分布的高維數(shù)據(jù)相似性連接查詢算法

馬友忠 賈世杰 張永新

摘要：為了解決高維數(shù)據(jù)相似性連接查詢中存在的維度災(zāi)難和計(jì)算代價(jià)高等問(wèn)題，基于p穩(wěn)態(tài)分布，將高維數(shù)據(jù)映射到低維空間。根據(jù)卡方分布的性質(zhì)，證明了如果低維空間的距離大于kε，則原始空間距離大于ε的概率具有一定的下界，從而可以在低維空間以較低的計(jì)算代價(jià)進(jìn)行有效過(guò)濾。在此基礎(chǔ)上，提出了基于卡方分布的高維數(shù)據(jù)相似性連接查詢算法。為了進(jìn)一步提高查詢效率，提出了基于雙重過(guò)濾的高維數(shù)據(jù)相似性連接查詢算法。利用真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提方法具有較好的性能?；诳ǚ椒植嫉南嗨菩赃B接查詢算法召回率可以達(dá)到90%以上?；陔p重過(guò)濾的相似性連接查詢算法可以進(jìn)一步提高性能，但是會(huì)損失一定的召回率。對(duì)時(shí)間性能要求比較高、對(duì)召回率要求不太嚴(yán)格的查詢?nèi)蝿?wù)可以采用基于雙重過(guò)濾的相似性連接查詢算法；反之，可以采用基于卡方分布的相似性連接查詢算法。

關(guān)鍵詞：

相似性連接查詢；高維數(shù)據(jù)；卡方分布；p穩(wěn)態(tài)分布；召回率

中圖分類號(hào)： TP311.13 文獻(xiàn)標(biāo)志碼：A

0引言

高維數(shù)據(jù)相似性連接查詢是一種十分重要且應(yīng)用廣泛的操作，是許多數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)任務(wù)的基礎(chǔ)操作，如圖片聚類、視頻副本檢測(cè)、文檔去重等。由于維度災(zāi)難的存在，高維數(shù)據(jù)的相似性連接查詢面臨巨大挑戰(zhàn)，傳統(tǒng)的以樹形索引結(jié)構(gòu)為基礎(chǔ)的查詢算法已無(wú)法奏效。

經(jīng)過(guò)深入分析和推理，作者發(fā)現(xiàn)基于穩(wěn)態(tài)分布和卡方分布的特點(diǎn)，可以將數(shù)據(jù)從高維空間映射到低維空間，并且可以通過(guò)計(jì)算低維空間的距離來(lái)進(jìn)行過(guò)濾，同時(shí)保證如果低維空間的距離大于kε，則原始空間距離大于ε的概率具有一定的下界。本文基于該重要觀察提出了一種基于卡方分布的高維數(shù)據(jù)相似性連接查詢算法，主要貢獻(xiàn)如下：

1）提出了基于穩(wěn)態(tài)分布的降維方法，并證明了利用低維空間距離進(jìn)行過(guò)濾的概率下界，具有較好的過(guò)濾效果；

2）提出了基于卡方分布的相似性連接算法和基于雙重過(guò)濾的相似性連接查詢算法；

3）針對(duì)真實(shí)數(shù)據(jù)集做了深入細(xì)致的實(shí)驗(yàn)，對(duì)本文所提出的方案進(jìn)行了認(rèn)真分析。實(shí)驗(yàn)結(jié)果表明，本文所提方案具有較好的性能。

1相關(guān)工作

目前已經(jīng)有很多學(xué)者對(duì)相似性連接查詢工作進(jìn)行了深入研究，出現(xiàn)了很多有代表性的學(xué)術(shù)成果。龐俊等[1-2]對(duì)相似性連接查詢關(guān)鍵技術(shù)進(jìn)行了全面綜述，對(duì)不同數(shù)據(jù)類型（字符串、集合、向量、圖）、不同查詢類型（閾值連接查詢、KNN（KNearest Neighbors）連接查詢、Topk連接查詢）和不同計(jì)算模式（集中模式、并行模式）的算法進(jìn)行了深入、細(xì)致分析。

文獻(xiàn)[3]提出了一種基于εKDB（KDimensional Btree）的高維數(shù)據(jù)相似性連接查詢算法。其核心思想是基于選定的某個(gè)維度，將全部數(shù)據(jù)劃分成等寬（ε）的部分，每個(gè)葉子節(jié)點(diǎn)僅與相鄰的兩個(gè)節(jié)點(diǎn)進(jìn)行連接操作。為了保證運(yùn)行的效率，該算法要求有足夠的內(nèi)存空間來(lái)存儲(chǔ)相鄰節(jié)點(diǎn)的數(shù)據(jù)。

文獻(xiàn)[4]提出了EGO（Epsilon Grid Order）方法，可以用來(lái)處理大規(guī)模高維數(shù)據(jù)的相似性連接查詢。該方法將整個(gè)數(shù)據(jù)空間劃分成等寬（ε）的若干個(gè)格子，并按照一定的機(jī)制將所有的格子進(jìn)行編號(hào)排序，最后采取一定的算法對(duì)這些格子內(nèi)的數(shù)據(jù)進(jìn)行一一比較。由于該方法不需要額外的內(nèi)存來(lái)存儲(chǔ)索引結(jié)構(gòu)，因此具有較好的擴(kuò)展性。

文獻(xiàn)[5]在EGO[4]的基礎(chǔ)上提出了一種改進(jìn)算法——SuperEGO。該算法主要采用基于數(shù)據(jù)驅(qū)動(dòng)的維度重排序機(jī)制，設(shè)計(jì)了一種新穎的EGO策略，能夠大大地減少不必要的計(jì)算；同時(shí)也開(kāi)發(fā)了并行版本，具有較好的執(zhí)行效率。

隨著數(shù)據(jù)規(guī)模的增加，單機(jī)算法無(wú)法有效處理海量高維數(shù)據(jù)的相似性連接查詢問(wèn)題，因此，有一些學(xué)者嘗試基于MapReduce并行計(jì)算框架[6]來(lái)解決該問(wèn)題。文獻(xiàn)[7]提出了一種基于網(wǎng)格劃分的大規(guī)模向量相似性連接方法。該方法的主要思想是：首先對(duì)數(shù)據(jù)進(jìn)行等寬的網(wǎng)格劃分；然后根據(jù)幾何性質(zhì)，對(duì)于選定的某個(gè)網(wǎng)格，確定需要與其進(jìn)行比較的其他網(wǎng)格；在選擇待比較網(wǎng)格的過(guò)程中，作者提出了一系列優(yōu)化、過(guò)濾方案，大大減少了重復(fù)比較的次數(shù)。該方法具有良好的并行特性，很容易在MapReduce框架下實(shí)現(xiàn)；但是該算法也有較大的局限性，一旦維度過(guò)高，性能會(huì)急劇下降。

為了解決文獻(xiàn)[7]中存在的問(wèn)題，文獻(xiàn)[8]又提出了一種新的基于MapReduce的連接方案——PHiDJ（Parallel HighDimensional Join）。為了克服維度增加帶來(lái)的性能急劇下降缺點(diǎn)，PHiDJ首先提出了維度劃分方案。基本思想是將所有維度按照一定的規(guī)則劃分成若干個(gè)子空間，然后針對(duì)每個(gè)子空間，再重新執(zhí)行文獻(xiàn)[7]中的算法；同時(shí)，為了解決均勻劃分可能存在的數(shù)據(jù)傾斜問(wèn)題，文獻(xiàn)[8]提出了變長(zhǎng)的網(wǎng)格劃分方案，其性能得到了極大的提高。

文獻(xiàn)[9]基于時(shí)間序列中的分段累積近似法（Piecewise Aggregate Approximation， PAA）提出了一種新的降維方法，可以將高維數(shù)據(jù)降到低維空間，并且低維空間的距離是原始距離的下界?；谠撔再|(zhì)，可以以較低的代價(jià)進(jìn)行有效過(guò)濾。同時(shí)，作者將該技術(shù)并行化，提出了兩種基于MapReduce框架的并行連接查詢算法，能夠有效地處理大規(guī)模高維數(shù)據(jù)。

文獻(xiàn)[10]提出了一種基于泰森多邊形的高維數(shù)據(jù)KNN連接解決方案。Zhang等[11]基于線性化技術(shù)，在MapReduce框架下提出了一種近似的高維數(shù)據(jù)KNN連接查詢方案。

除了上述基于歐幾里得距離的高維數(shù)據(jù)相似性連接查詢工作外，還有很多針對(duì)其他類型數(shù)據(jù)的并行相似性連接查詢算法，如集合相似性連接查詢[12-16]、空間數(shù)據(jù)相似性連接查詢[17]、概率數(shù)據(jù)相似性連接查詢[18-19]等。這些算法雖然不能直接用來(lái)解決高維數(shù)據(jù)的相似性連接查詢問(wèn)題，但仍具有重要的借鑒意義。

2預(yù)備知識(shí)

2.1問(wèn)題定義

定義1相似性連接查詢。給定兩個(gè)數(shù)據(jù)集合Q和S，分別包含n1和n2個(gè)來(lái)自d維歐幾里得空間Rd的點(diǎn)。距離函數(shù)為dist，距離閾值為ε，Q和S的相似性連接查詢就是找到所有距離小于或等于ε的數(shù)據(jù)對(duì)，即：Q∞S={〈q，s〉|q∈Q，s∈S，dist（q，s）≤ε}。其中：Q={q1，q2，…，qn1}，S={s1，s2，…，sn2}，qi此處的qi是矢量、向量或矩陣嗎？請(qǐng)明確。是集合Q中的第i個(gè)數(shù)據(jù)點(diǎn)，qi=〈qi1，qi2，…，qid〉，兩個(gè)d維的數(shù)據(jù)點(diǎn)qi和sj的歐幾里得距離dist定義為：

2.2p穩(wěn)態(tài)分布與卡方分布

定義2p穩(wěn)態(tài)分布。對(duì)于一個(gè)分布D，如果存在p≥0，對(duì)任何d個(gè)實(shí)數(shù)v1，v2，…，vd和d個(gè)滿足D分布的獨(dú)立同分布的變量X1，X2，…，Xd，隨機(jī)變量∑iviXi與（∑di=1vpi）1/pX具有相同的分布，其中X是服從D分布的一個(gè)隨機(jī)變量，則稱D是一個(gè)p穩(wěn)態(tài)分布。

當(dāng)p∈（0，2]時(shí)都存在p穩(wěn)態(tài)分布，當(dāng)p=2時(shí)，高斯分布（即正態(tài)分布）就是2穩(wěn)態(tài)分布。

根據(jù)定義2可知，基于p穩(wěn)態(tài)分布可以對(duì)高維向量進(jìn)行有效的近似，并且能夠在保持原始距離的同時(shí)，對(duì)高維向量進(jìn)行降維。其核心思想是：產(chǎn)生一個(gè)d維的隨機(jī)向量a，隨機(jī)向量a的每一個(gè)元素都服從p穩(wěn)態(tài)分布。對(duì)于一個(gè)d維的向量v，由定義2可知，隨機(jī)變量a·v與（∑di=1vpi）1/pX具有相同的分布，因此可以用a·v來(lái)估算向量v的長(zhǎng)度‖v‖p。本文的主要目的并不是用來(lái)估算向量的長(zhǎng)度，而是通過(guò)p穩(wěn)態(tài)分布對(duì)原始高維向量進(jìn)行降維，用降維后兩個(gè)向量之間的距離來(lái)估算原始高維向量之間的距離，從而實(shí)現(xiàn)以較低的計(jì)算代價(jià)來(lái)進(jìn)行過(guò)濾。

定義3卡方分布。如果X1，X2，…，Xm是服從標(biāo)準(zhǔn)正態(tài)分布N（0，1）的獨(dú)立、同分布隨機(jī)變量，令S2=∑mi=1X2i，則S2服從自由度為m的卡方分布，記為：S2～χ2（m）。

2.3常用符號(hào)說(shuō)明

常用符號(hào)說(shuō)明如表1所示。

3基于卡方分布的相似性連接查詢

3.1相關(guān)定理

令g（v）=v·a，其中向量a的每一個(gè)元素都是服從標(biāo)準(zhǔn)正態(tài)分布N（0，1）的獨(dú)立、同分布隨機(jī)變量。可得如下引理。

引理1對(duì)任意兩個(gè)d維向量v1，v2∈Rd，則g（v1）-g（v2）服從正態(tài)分布N（0，dist2（v1，v2））。

定理2的含義是：如果向量v1，v2的m維映射的距離大于kε，則v1和v2的歐氏距離大于ε的概率大于1-P（χ2>k2）?；谠撔再|(zhì)，可以將高維向量v1，v2映射到低維空間內(nèi)，通過(guò)計(jì)算低維空間的距離來(lái)進(jìn)行過(guò)濾，從而降低過(guò)濾的計(jì)算代價(jià)。

3.2基于卡方分布的相似性連接查詢

基于定理2，可以得到基于卡方分布的相似性連接查詢方案，處理框架如圖1所示。

處理流程主要分為3個(gè)階段：第1階段是降維，主要任務(wù)是利用m個(gè)隨機(jī)向量a1，a2，…，am根據(jù)文中的描述，此處a1，a2，…，am是否應(yīng)該是矢量、向量或矩陣？請(qǐng)明確。，與原始d維向量v進(jìn)行點(diǎn)積運(yùn)算，從而將向量v從d維空間降低到m維空間；第2階段是過(guò)濾階段，該階段在m維空間內(nèi)計(jì)算兩個(gè)向量之間的距離，根據(jù)定理2，如果Δm（v1，v2）>kε，則就把〈v1，v2〉過(guò)濾掉；第3階段是驗(yàn)證階段，由于通過(guò)過(guò)濾階段的候選對(duì)不一定滿足查詢要求，因此需要在該階段計(jì)算候選對(duì)的原始?xì)W氏距離，據(jù)此進(jìn)行最后的判斷。詳細(xì)執(zhí)行過(guò)程如算法1所示。

算法1基于卡方分布的相似性連接算法。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：S，n，ε，m，此處有5個(gè)變量，但后面的說(shuō)明中卻只有4個(gè)，是否說(shuō)明有遺漏？請(qǐng)明確?；貜?fù)：是新向量集合，在算法第1）行已有說(shuō)明，為排版美觀，在這沒(méi)有再作說(shuō)明。//數(shù)據(jù)集合、數(shù)據(jù)規(guī)模、距離閾值、映射空間維度

輸出：相似向量對(duì)和距離。

1）

=，Q=；//新向量集合和結(jié)果集合

2）

隨機(jī)選擇m個(gè)向量a1，a2，…，am，e∈ai～N（0，1）；

3）

對(duì)于S中的每一個(gè)向量v

4）

計(jì)算πm（v）=〈g1（v），g2（v），…，gm（v）〉；

5）

← 〈πm（v），v〉；//映射向量和原始向量組合成新的向量集合

6）

對(duì)于中的每一個(gè)向量對(duì)（1，2）

7）

計(jì)算映射空間距離Δm（πm（v1），πm（v2））；

8）

如果 Δm（πm（v1），πm（v2））≤kε//過(guò)濾

9）

計(jì)算原始距離dist（v1，v2）；

10）

如果 dist（v1，v2）≤ε

11）

Q ← 〈（v1，v2），dist（v1，v2）〉；

12）

輸出結(jié)果集合Q；

程序后

3.3基于雙重過(guò)濾的相似性連接查詢

定理 3如果Δm（v1，v2）>kε，則出現(xiàn)偽正例的概率小于或等于：1-P（χ2>k2），即：P（dist（v1，v2）≤ε）≤1-P（χ2>k2）。

證明過(guò)程如定理2。

由定理2可知，如果Δm（v1，v2）>kε，則成功過(guò)濾的概率下界是1-P（χ2>k2）。一般情況下，為了增強(qiáng)過(guò)濾效果，1-P（χ2>k2）的值會(huì)取得比較大，如90%；但是，這種情況下，出現(xiàn)偽正例的概率上界也是90%，即出現(xiàn)偽正例的概率可能會(huì)比較大。由此分析可以得出，在k值固定的情況下，過(guò)濾效果的下界和偽正例的上界存在矛盾。為了既能夠保證較好的過(guò)濾效果，又能夠降低偽正例的概率上界，可以采用雙重過(guò)濾算法，即第1次過(guò)濾采用過(guò)濾條件Δm（v1，v2）>k1ε，第2次過(guò)濾采用過(guò)濾條件Δm（v1，v2）>k2ε，且k1>k2。這樣就可以達(dá)到同時(shí)降低偽反例和偽正例的效果。

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

本章將對(duì)提出的基于卡方分布的相似性連接查詢（chisquare distributionbased Similarity Join Query， χ2SJQ）算法和基于雙重過(guò)濾的相似性連接查詢（Similarity Join Query based on Double Filtering DFχ2SJQ）算法與嵌套循環(huán)連接（Nested Loop Join， NLJ）算法對(duì)比進(jìn)行實(shí)驗(yàn)驗(yàn)證。驗(yàn)證指標(biāo)主要包括算法運(yùn)行時(shí)間（run time）和召回率（recall）。由于最終的結(jié)果都經(jīng)過(guò)驗(yàn)證階段，所以準(zhǔn)確率（precision）為100%。

4.1實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)環(huán)境實(shí)驗(yàn)運(yùn)行的計(jì)算機(jī)配置如下：CPU為Intel Core i54210H 2.90GHz，內(nèi)存為8GB，磁盤為1TB，操作系統(tǒng)為64bit Windows 7。實(shí)驗(yàn)中的相關(guān)參數(shù)如表2所示，加下劃線的數(shù)字表示默認(rèn)值。

4.2距離閾值變化（ε）

圖2顯示了距離閾值的變化對(duì)運(yùn)行時(shí)間和召回率的影響。從圖2中可以看出，在距離閾值小于0.3時(shí)，算法 χ2SJQ和算法DFχ2SJQ的性能差別不大；但是，隨著距離閾值的增大，結(jié)果數(shù)量也會(huì)急劇增加，此時(shí)，算法DFχ2SJQ的性能更好；但是，算法DFχ2SJQ的性能是以犧牲一定的召回率來(lái)?yè)Q得的，因此，實(shí)際應(yīng)用中需要在運(yùn)行時(shí)間和召回率之間進(jìn)行適當(dāng)?shù)臋?quán)衡。

4.3維度變化（d）

圖3顯示了算法性能與向量維度之間的關(guān)系。直觀上分析，隨著維度的增加，運(yùn)行時(shí)間應(yīng)該增大；但是，從圖3中看出，部分節(jié)點(diǎn)出現(xiàn)異常。通過(guò)對(duì)結(jié)果進(jìn)行深入分析發(fā)現(xiàn)，實(shí)驗(yàn)中統(tǒng)計(jì)的運(yùn)行時(shí)間包括計(jì)算時(shí)間和把運(yùn)行結(jié)果寫入文件的時(shí)間。維度越大，計(jì)算時(shí)間肯定越大；但是數(shù)據(jù)寫入花費(fèi)的時(shí)間卻不一定。從實(shí)驗(yàn)結(jié)果看出，d=256時(shí)，結(jié)果數(shù)據(jù)量分別是425551814，421966225和393140173；而d=960時(shí)，最終的計(jì)算結(jié)果數(shù)量分別是4444884，4190456和2704272，因此，才會(huì)出現(xiàn)圖3中所示的情況。

4.4數(shù)據(jù)集大小變化（n）

圖4顯示了數(shù)據(jù)集大小對(duì)算法性能的影響。從圖4可以看出，隨著數(shù)據(jù)集的增大，3種算法的運(yùn)行時(shí)間都不斷增加，嵌套循環(huán)連接（Nested Loop Join， NLJ算法增加最快，算法DFχ2SJQ增加最為緩慢，并且性能最好；但是其召回率也低于算法χ2SJQ。

4.5映射空間維度變化（m）

圖5描述了映射空間維度對(duì)算法性能的影響。整體來(lái)看，映射空間維度越大，算法DFχ2SJQ的運(yùn)行時(shí)間也會(huì)越長(zhǎng)，而算法χ2SJQ的運(yùn)行時(shí)間卻逐步下降，但仍大于前者。

4.6過(guò)濾效果概率下界對(duì)性能的影響

圖6顯示了過(guò)濾效果下界對(duì)算法性能的影響。從運(yùn)行結(jié)果可以看出，隨著概率下界的逐漸增大，算法χ2SJQ的執(zhí)行時(shí)間有明顯的增加，而算法DFχ2SJQ的執(zhí)行時(shí)間相對(duì)比較平穩(wěn)，但是后者的召回率普遍低于前者的召回率。

5結(jié)語(yǔ)

高維數(shù)據(jù)的相似性連接查詢是一種計(jì)算代價(jià)較高的操作。本文基于p穩(wěn)態(tài)分布，將原始d維數(shù)據(jù)映射到m維（m

未來(lái)將對(duì)本文方案作進(jìn)一步的優(yōu)化：目前在m維空間進(jìn)行距離計(jì)算的時(shí)候，采取的是窮舉法，即所有的m維向量?jī)蓛蛇M(jìn)行比較，未來(lái)可以對(duì)m維空間（低維空間）的距離計(jì)算進(jìn)行優(yōu)化；另外，本文所處理的數(shù)據(jù)集規(guī)模比較有限，未來(lái)將結(jié)合目前流行的云計(jì)算平臺(tái)，重點(diǎn)研究并行化方案，用于處理大規(guī)模數(shù)據(jù)集的相似性連接查詢；同時(shí)，未來(lái)還將對(duì)其他類型的相似性連接查詢問(wèn)題進(jìn)行研究，如KNN連接查詢、Topk連接查詢等。

參考文獻(xiàn)：

[1]

龐俊，谷峪，許嘉，等.相似性連接查詢技術(shù)研究進(jìn)展[J].計(jì)算機(jī)科學(xué)與探索，2013，7（1）：1-13.（PANG J， GU Y， XU J， et al. Research advance on similarity join queries [J]. Journal of Frontiers of Computer Science and Technology， 2013， 7（1）： 1-13.）

[2]

龐俊，于戈，許嘉，等.基于MapReduce框架的海量數(shù)據(jù)相似性連接研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，2015，42（1）：1-5.（PANG J， YU G， XU J， et al. Similarity joins on massive data based on MapReduce framework [J]. Computer Science， 2015， 42（1）： 1-5.）

[3]

SHIM K， SRIKANT R， AGRAWAL R. Highdimensional similarity joins [J]. IEEE Transactions on Knowledge and Data Engineering， 2002， 14（1）： 156-171.

[4]

BHM C， BRAUNMLLER B， KREBS F， et al. Epsilon grid order： an algorithm for the similarity join on massive highdimensional data [C]// Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2001： 379-388.

[5]

KALASHNIKOV D. SuperEGO： fast multidimensional similarity join [J]. The VLDB Journal， 2013， 22（4）： 561-585.

[6]

DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [C]// Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation. San Francisco： USENIX Association， 2004： 137-150.

[7]

SEIDL T， FRIES S， BODEN B. MRDSJ： distancebased selfjoin for largescale vector data analysis with MapReduce [C]// Proceedings of the 15th BTW Conference on Database Systems for Business， Technology， and Web. Berlin： Springer， 2013： 37-56.

[8]

FRIES S， BODEN B， STEPIEN G， et al. PHiDJ： parallel similarity selfjoin for highdimensional vector data with MapReduce [C]// Proceedings of the 30th IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE， 2014： 796-807.

[9]

LUO W， TAN H， MAO H， et al. Efficient similarity joins on massive highdimensional datasets using MapReduce [C]// Proceedings of the 13th IEEE International Conference on Mobile Data Management. Piscataway， NJ： IEEE， 2012： 1-10.

[10]

LU W， SHEN Y， CHEN S， et al. Efficient processing of k nearest neighbor joins using MapReduce [J]. Proceedings of the VLDB Endowment， 2012， 5（10）： 1016-1027.

[11]

ZHANG C， LI F， JESTES J. Efficient parallel kNN joins for large data in MapReduce [C]// Proceedings of the 15th International Conference on Extending Database Technology. New York： ACM， 2012： 38-49.

[12]

VERNICA R， CAREY M， LI C. Efficient parallel setsimilarity joins using MapReduce [C]// Proceedings of the ACM SIGMOD International Conference on Management of Data. New York： ACM， 2010： 495-506.

[13]

RONG C， LU W， WANG X， et al. Efficient and scalable processing of string similarity join [J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（10）： 2217-2230.

[14]

ELSAYED T， LIN J， OARD D. Pairwise document similarity in large collections with MapReduce [C]// Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics. Stroudsburg， PA： Association for Computer Linguistics， 2008： 265-268.

[15]

METWALLY A， FALOUTSOS C. VSMARTJoin： a scalable MapReduce framework for allpair similarity joins of multisets and vectors [C]// Proceedings of the VLDB Endowment， 2012， 5（8）： 704-715.

[16]

BARAGLIA R， MORALES G， LUCCHESE C. Document similarity selfjoin with MapReduce [C]// Proceedings of the 10th IEEE International Conference on Data Mining. Piscataway， NJ： IEEE， 2010： 731-736.

[17]

劉義，陳犖，景寧，等.海量空間數(shù)據(jù)的并行Topk連接查詢[J].計(jì)算機(jī)研究與發(fā)展，2011，48（z2）：163-172.（LIU Y， CHEN L， JING N， et al. Parallel topk spatial join query processing on massive spatial data [J]. Journal of Computer Research and Development， 2011， 48（z2）： 163-172.）

[18]

雷斌，許嘉，谷峪，等.概率數(shù)據(jù)上基于EMD距離的并行Topk相似性連接算法[J].軟件學(xué)報(bào)，2013，24（S2）：188-199.（LEI B， XU J， GU Y， et al. Parallel topk similarity join algorithm on large probabilistic data based on earth movers distance [J]. Journal of Software， 2013， 24（S2）： 188-199.）

[19]

HUANG J， ZHANG R， BUYYA R， et al. MELODYJOIN： efficient earth movers distance similarity joins using MapReduce [C]// Proceedings of the 30th IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE， 2014： 808-819.