馬友忠,張智輝,林春杰

(1.洛陽師范學院 信息技術學院,河南 洛陽 471934;2.河南省電子商務大數(shù)據(jù)處理與分析重點實驗室(洛陽師范學院),河南 洛陽 471934;3.洛陽鐵路信息工程學校 計算機教研室,河南 洛陽 471900)(*通信作者電子郵箱ma_youzhong@163.com)

0 引言

相似性連接查詢是指給定兩個數(shù)據(jù)對象集合R和S(集合、向量、空間數(shù)據(jù)、字符串等),一個度量函數(shù)sim和一個相似度閾值ε,找出所有分別來自R和S的相似度大于閾值ε的數(shù)據(jù)對象對。相似性連接查詢是一種應用廣泛且非常重要的操作,是很多數(shù)據(jù)分析及數(shù)據(jù)挖掘任務的基本操作,如分類、聚類、異常檢測、重復文檔檢測等。

相似性連接查詢存在兩大挑戰(zhàn):一是相似度計算代價大，尤其是當數(shù)據(jù)類型比較復雜或者是數(shù)據(jù)維度比較高時,兩個數(shù)據(jù)對象之間的相似度的計算將耗費很多時間。二是擴展性問題。隨著大數(shù)據(jù)時代的到來,數(shù)據(jù)的規(guī)模日益增長,傳統(tǒng)的集中式算法或串行算法已經(jīng)不能在可接受的時間內(nèi)完成大規(guī)模數(shù)據(jù)集的相似性連接查詢?nèi)蝿铡Ｒ虼?如何借助最新的計算技術,設計具有良好擴展性的相似性連接查詢算法,成為目前大數(shù)據(jù)相似性連接查詢的重要研究內(nèi)容。MapReduce是一個由Google最先提出的分布式計算軟件框架,具有高可擴展性、高可用性、高容錯性等特點,可以支持大規(guī)模數(shù)據(jù)的分布式處理,目前已經(jīng)成為大數(shù)據(jù)處理的首選平臺。為了解決大規(guī)模復雜數(shù)據(jù)類型的相似性連接查詢問題,很多學者針對基于MapReduce框架的相似性連接查詢算法進行了深入研究,提出了很多創(chuàng)新的解決方案。

根據(jù)分類標準的不同,相似性連接查詢可以有不同的分類方法?？梢园凑諗?shù)據(jù)對象類型、對象集合的動態(tài)性,以及查詢結(jié)果和處理方式的不同等標準來進行劃分。不同分類標準得到的類別之間可能會有重疊,并且不同的數(shù)據(jù)類型,對象之間的相似度度量函數(shù)往往不同,因此所采用的方法也不相同,本文將主要按照不同數(shù)據(jù)對象類型的連接查詢方法進行分別描述。表1描述了不同數(shù)據(jù)類型對應的常用相似度度量函數(shù),其中,集合、向量和字符串的相似度度量有所重疊,部分方法可以通用。為便于描述,本文中集合主要采用杰卡德相似度和余弦相似度,向量主要采用歐氏距離,字符串主要采用編輯距離。

表1 相似度度量函數(shù)

另外,關于集中式的相似性連接查詢方法,文獻[1-3]已經(jīng)進行了綜述,本文不再詳細描述。龐俊等[4]對基于MapReduce框架的海量數(shù)據(jù)相似性連接工作進行了綜述,但是主要包含的是2013年及以前的部分研究工作。還有部分學者[5-6]對典型的基于MapReduce的相似性連接查詢算法進行了實驗驗證和比較。本文將針對截至2017年的云計算環(huán)境下的大數(shù)據(jù)相似性連接查詢技術進行更全面、深入的分析。

1 集合相似性連接查詢

集合相似性連接查詢廣泛應用于文本分類、聚類、重復網(wǎng)頁檢測等應用中,文本、網(wǎng)頁都可以表示成單詞的集合。集合的相似性度量主要包括杰卡德相似度、余弦相似度、重疊相似度和Dice相似度等。隨著數(shù)據(jù)規(guī)模的不斷擴大,單機環(huán)境下的相似性連接算法已經(jīng)不能滿足性能要求,有很多學者基于MapReduce框架,提出了若干種針對大規(guī)模集合數(shù)據(jù)的相似性連接查詢處理方案，如表2所示。

表2 集合相似性連接查詢方案

表2描述了已有的大規(guī)模集合相似性連接查詢方案，并按照采用的技術不同,將其分為六類:窮舉方案、前綴過濾、Word-Count-Like、混合方案、基于劃分的方法和基于位置敏感哈希的方法。各類方案的主要優(yōu)缺點和代表算法詳細描述如下。

1)窮舉方案。

文獻[7]較早利用MapReduce框架對相似性連接查詢問題進行了研究,并提出了Brute force算法和基于索引的算法。其中,Brute force算法通過精確匹配找出所有滿足條件的文本對。該算法在Map階段使用暴力法,計算出每一個文本和其他所有文本的相似度,然后輸出所有相似度不為零的文本對;在Reduce階段,針對每一個文本求出與其相似度最大的k個文本。該算法可以求出精確的結(jié)果,但是計算代價比較大。索引算法可以在一定程度上降低計算代價,提升性能,但是結(jié)果的精度會有所下降。總體來看,Brute force算法沒有進行任何過濾,任意兩個集合都需要比較一次;基于索引的算法雖然可以進行一定程度的過濾,但是過濾效果不理想,重復比較次數(shù)仍然會比較多。

2)前綴過濾。

文獻[8]在MapReduce框架下,提出了一種基于前綴過濾(prefix filtering)技術的大規(guī)模集合數(shù)據(jù)相似性連接查詢方案。文獻[8]中處理的數(shù)據(jù)對象是一些記錄(record)的集合,每一條記錄由記錄標識和其他若干個屬性組成,其中連接屬性是項(token)的集合。前綴過濾是一種很有效的過濾方法,其基本思想是:假設數(shù)據(jù)集中所有的項(token)按照其出現(xiàn)頻度由低到高進行排序,得到一個序列O,數(shù)據(jù)集中的每一個集合都按照序列O進行排列,集合A的p-前綴就是集合A的前p個項。假定相似性度量采用杰卡德相似度,閾值為t,則如果J(A,B)≥t,那么A的(|A|-「t·|A|?+1)-前綴和B的(|B|-「t·|B|?+1)-前綴至少含有一個公共的項(token)。即如果兩個集合的前綴沒有公共的項,則這兩個集合肯定不相似。根據(jù)上述基本思想,文獻[8]在MapReduce框架下實現(xiàn)了前綴過濾方案。該方案主要分為三個階段,分別為項排序(Token Ordering)、相似對生成(RID-Pair Generation)和最終結(jié)果生成(Record Join),每個階段由一個或多個MapReduce Job來完成。項排序階段的主要目的是通過計算數(shù)據(jù)集合的相關統(tǒng)計信息,得到具有較好過濾效果的集合前綴,具體方法是計算出集合中所有項(token)出現(xiàn)的頻率,然后按照出現(xiàn)頻率將所有項進行升序排列,作者分別提出了基本排序法(basic token ordering)和一階段排序法(using one phase to order tokens)來完成排序任務。相似對生成階段主要是根據(jù)連接的屬性,找出相似度大于給定閾值的記錄對,該階段由一個MapReduce Job完成。在Map階段,針對每一個輸入記錄,首先抽取出其ID和連接屬性,然后根據(jù)前一階段得到的項序列,計算出連接屬性的前綴,接著根據(jù)連接屬性的前綴構(gòu)建倒排索引。針對每一個記錄,會生成若干個〈key,value〉對的集合,其中:key是記錄前綴中的每一個項;value包括該記錄的ID和連接屬性。在Reduce階段,具有相同key值的value組合在一起,發(fā)送到同一個reducer中。同一個key就對應著包含該key的記錄列表,這些記錄有可能相似,針對這些記錄,作者提出了嵌套循環(huán)鏈接和PPJoin+兩種方法來計算相似度大于閾值t的記錄對,包括記錄ID和相似度。在最終結(jié)果生成階段,將前一階段得到的相似對集合與原始數(shù)據(jù)集合進行連接,獲取記錄的完整信息,得到最終結(jié)果。文獻[9]的解決思路與文獻[8]類似,改進之處在于文獻[9]除了前綴過濾之外,又增加了長度過濾,這樣就可以進一步提高性能。

為了進一步提高過濾效果,減少候選對的數(shù)量,文獻[10]中提出了一種基于多前綴的集合相似性連接方案。文獻[8]中所使用的前綴過濾技術雖然在一定程度上減少了候選對的數(shù)量,但是在候選對中仍然有很多是不相似的,因為即使兩個對象的前綴有公共的項,這兩個對象也不一定相似。文獻[10]通過分析、觀察發(fā)現(xiàn),集合的前綴是按照某個項的排序生成的,不同的排序,所產(chǎn)生的前綴就不一樣?；谠撍枷?文獻[10]為每個對象按照不同的排序生成多個不同的前綴,其中用第一個前綴來建立倒排索引,用其他的前綴來進行進一步的過濾,最終通過過濾的候選對才需要進行最后的驗證,從而大大減少了計算的代價。同時,文獻[10]還提出了一個代價模型,來確定序列(即前綴)的數(shù)量,并提出了多種排序方案,主要包括隨機選擇(random selection)、基于反序列的隨機選擇(random selection with reverse ordering)和基于詞頻的全局排序(TF as the first global ordering)。作者還在單機環(huán)境及MapReduce框架下分別對該算法進行了實現(xiàn)及驗證,實驗結(jié)果表明,基于多前綴的集合相似性連接方法具有較好的性能。

但是基于前綴過濾技術的方案也存在一些不足之處：a)網(wǎng)絡傳輸代價較大。每個集合都要復制多次,復制的次數(shù)等于前綴的長度,因此對于較長的集合來講,數(shù)據(jù)復制率太高,會導致網(wǎng)絡傳輸代價比較大。b)重復比較次數(shù)比較多。對于任意兩個集合,如果它們的前綴中有k個公共項,則會重復比較k次。

3)Word-Count-Like方案。

為了克服前綴方案中存在的缺點,文獻[11]中提出了一種“Word-Count-Like”的解決方案Pairwise Join,之所以取名為“Word-Count-Like”,是因為該方案充分利用了MapReduce框架的特性,基本思路類似于Word-Count程序。文獻[11]主要解決的是文檔的相似性連接問題,每一個文檔可以被表示成一個詞的權(quán)重的向量,相似性度量采用的是權(quán)重向量的內(nèi)積來表示。該方案主要分兩個階段來完成,第一階段主要生成倒排索引,第二階段用來計算任意兩個文檔的相似度,每個階段均由一個MapReduce Job來實現(xiàn)。在Job 1中:Map階段針對每一個輸入的文檔向量〈i,di〉,輸出〈key,value〉的集合〈t,〈i,di[t]〉,其中：i是文檔標識;di是權(quán)重向量;t是單詞;di[t]是t在文檔i中的權(quán)重。在Reduce端,同一個單詞t對應的value被組合在一起,按照〈t,[〈i,di[t]〉,〈j,dj[t]〉,…]〉的形式輸出。在Job 2中,Map階段針對每一個〈t,[〈i,di[t]〉,〈j,dj[t]〉,…]〉進行處理,輸出〈〈i,j〉,w=di[t]·dj[t]〉的集合,其中：〈i,j〉是兩個文檔的ID對；w是t在兩個文檔中的權(quán)重的乘積。在Reduce端,與同一個〈i,j〉對對應的w被組合在一起,對這些權(quán)重求和,得到的最終結(jié)果就是文檔對〈i,j〉的相似度。

文獻[12]的基本思路與文獻[7]類似,提出了V-SMART-Join方案。不同之處在于文獻[12]中對處理方案進行了一般化,處理的數(shù)據(jù)對象類型進行了擴充,可以處理集合、多重集合以及向量,相似性度量可以采用內(nèi)積、余弦相似度以及杰卡德相似度等。此外,文獻[12]中還提出了一些解決方案,用來高效處理傾斜數(shù)據(jù)，并在大規(guī)模真實數(shù)據(jù)集上進行了充分的實驗,實驗結(jié)果表明,文獻[12]方案的性能比文獻[8]方案的性能要高30倍以上。

Word-Count-Like方案的優(yōu)點是避免了重復比較,任何一對文檔只需要比較一次。另外,文檔本身沒有被重復復制,傳輸?shù)膬H僅是各個單詞對應的權(quán)重,所以大大降低了網(wǎng)絡傳輸?shù)拇鷥r。但是該類方案也存在一些局限性,任何兩個文檔只要包含一個公共元素,都需要比較一次,沒有利用到相似度閾值和前綴的過濾功能,因此會產(chǎn)生很多不必要的候選對。

4)混合方案。前綴過濾方案和Word-Count-Like方案各有優(yōu)缺點,文獻[13]中結(jié)合上述兩種方案的優(yōu)點,提出了一種混合方案Self-Join,從而進一步提高了集合相似性連接的效率。文獻[13]對文獻[11]進行了擴充,在建立倒排索引時候,利用前綴過濾技術來縮短索引列表的長度,從而可以大幅減少中間結(jié)果的數(shù)量。由于采用了前綴進行過濾,對于任意一個候選對中的文檔來說,可能只包含一部分權(quán)重信息,因此還需要兩次遠程操作來獲取其相應的權(quán)重信息,從而計算出最終的相似度。由于遠程操作的代價一般比較大,為了解決這一問題,文獻[13]又提出了一種優(yōu)化方案——SSJ-2R (Double-Pass MapReduce Prefix-Filtering with Remainder File)。

該方案的優(yōu)點是將前綴過濾技術與Word-Count-Like方案進行了結(jié)合,從而減少了候選對的數(shù)量;沒有重復計算,每一對只計算一次。不足之處在于,因候選對中沒有集合的全部信息,所以需要在候選對的基礎上,進行進一步的處理,進行數(shù)據(jù)的傳輸?shù)?候選對的數(shù)量與ALL Pairs方法中候選對的數(shù)量是一樣的,即只要兩個集合的前綴中至少含有一個公共項,就成為一個候選對。

5)基于劃分的方法。文獻[14]中提出了一種基于垂直劃分的相似性連接查詢算法FS-Join,可以有效避免重復計算,并可以實現(xiàn)Map端和Reduce端的負載均衡。但是,樞軸(Pivot)的選擇以及樞軸個數(shù)的確定對該算法的性能影響較大,需要花費較大的代價確定樞軸及其個數(shù)。為了減少重復計算的代價,Greedy+[15]設計了一種新的劃分機制,將集合劃分成若干子集,并確保：如果兩個集合相似,那么它們一定有相同的子集。

6)基于位置敏感哈希的方法。個性化位置敏感哈希(Personalized Locality Sensitive Hashing, PLSH)方法[16]在傳統(tǒng)位置敏感哈希技術的基礎上,提出了一種新的采用靈活閾值的分塊技術(banding technique),從而可以大幅減少偽正例的個數(shù),提高計算效率,并能夠?qū)崿F(xiàn)偽正例和偽反例之間的平衡。

2 向量相似性連接查詢

向量數(shù)據(jù)相似性連接查詢針對的數(shù)據(jù)類型是向量,包括低維向量和高維向量,如圖形、圖像、Web文檔、基因表達數(shù)據(jù)等多種數(shù)據(jù)經(jīng)過處理后,都可以用向量來表示。向量的相似性度量也有很多種,包括余弦相似度、杰卡德相似度、歐氏距離和閔可夫斯基距離等,本文將主要研究基于歐氏距離的解決方案。根據(jù)返回結(jié)果的不同,向量相似性連接查詢可以分為基于閾值的連接查詢、Top-k連接查詢和KNN連接查詢,具體信息如表3所示。

閾值相似性連接查詢:文獻[17]中提出了一種稱為DAA(Dimension Aggregation Approximation)技術的降維方法,并在此基礎上提出了基于MapReduce框架的并行相似性連接查詢算法。DAA是受分段累積近似法(Piecewise Aggregate Approximation, PAA)技術的啟發(fā),PAA是時間序列中一種比較有效的數(shù)據(jù)降維方法,其核心思想是:將一個長度為n的時間序列,劃分成m段,形成一個長度為m的新序列,用每一段內(nèi)的所有元素的均值作為新序列的元素值,基于新序列,可以構(gòu)建一個新的距離函數(shù),該距離是原始序列距離的下界,因此可以基于降維后的序列來對原始向量進行過濾。

在DAA技術的基礎上,結(jié)合MapReduce框架,作者以嵌套循環(huán)連接算法為基礎,提出了兩種新的并行化算法:一階段過濾驗證算法OSFR(One-Stage Filtering-and-Refinement)和兩階段過濾驗證算法TSFR(Two-Stage Filtering-and-Refinement)。在進行數(shù)據(jù)傳輸?shù)倪^程中,OSFR除了傳輸降維后的向量之外,原始向量也要一起傳輸,在得到候選對以后,在驗證階段就可以直接利用原始向量的信息計算原始距離。但是當向量維度特別高時,這種方案的網(wǎng)絡傳輸代價比較大。TSFR算法分為兩個階段來完成,在第一個階段僅僅使用降維后的低維向量進行計算,得到候選對以后,再利用第二個階段去獲取原始向量信息,進行最后的驗證。該方案可以減少網(wǎng)絡傳輸?shù)拇鷥r,但是在第二個階段需要遠程獲取原始向量的信息,也需要一定的額外開銷。最后,作者提出了一個代價模型,用來進行算法選擇,通過分析和實驗驗證表明,OSFR算法比較適合于較低維向量,TSFR算法比較適合于超高維向量。文獻[17]方案可以以較低的代價進行過濾,從而減少不必要的比較。但是,該方案的時間復雜度仍然是O(n2),即任意兩個向量在低維空間上都需要比較一次。

表3 向量相似性連接查詢技術

文獻[18]中提出了一種基于網(wǎng)格劃分方法的大規(guī)模向量相似性自連接處理方案,該方案的核心思想是利用網(wǎng)格對數(shù)據(jù)對象進行劃分,并按照相應的過濾技術,減少計算比較的次數(shù),降低網(wǎng)絡傳輸?shù)拇鷥r。以二維向量為例來進行介紹:假設距離閾值為ε,首先將空間進行網(wǎng)格劃分,格子的寬度為ε,對于每一個單元格內(nèi)的對象,只可能與自身以及周圍的八個單元格內(nèi)的對象相似,這樣就不需要與其他單元格內(nèi)的對象進行比較,可以減少大量的計算量。為了保證計算的完整性,每一個單元格內(nèi)的數(shù)據(jù)都需要復制3d次(d是向量的維數(shù)),在不同的Reduce上進行計算。實際上有些計算和復制是重復的,可以采取一定的措施來減少數(shù)據(jù)復制的比率,即每一個單元格內(nèi)的對象只與其自身和左下方的單元格內(nèi)的對象比較即可,這樣也可以保證計算的完整性,基于這種方法,數(shù)據(jù)復制的比率可以降為2d。另外,作者還提出了一些優(yōu)化方法,在Reduce端進一步減少計算的次數(shù)。該方法具有很好的并行特性,很容易在MapReduce框架下實現(xiàn)。其不足之處是該方法只適合于維度較低的情況,一旦維度比較高時,其性能急劇下降。

為了解決這一問題,文獻[19]對文獻[18]方案進行了擴充,提出了一種新的基于MapReduce的連接方案——PHiDJ(Parallel High-Dimensional Join),PHiDJ方案主要通過對維度分組和變長的網(wǎng)格劃分來提高連接速度。具體思路為:首先把d個維度(高維)劃分成若干個互不相交的組(低維),每一個組包含若干個維;然后針對每一個組,再采用文獻[18]方法處理,最后進行驗證、過濾。另外,文獻[18]采用的是均勻網(wǎng)格劃分法(等寬),文獻[19]則采用了變長的網(wǎng)格劃分方案,具有更好的適應性和過濾效果。作者通過大量的實驗結(jié)果表明,文獻[19]算法比文獻[18]算法具有更好的性能,并且能夠處理更高維的向量。

文獻[20-21]中提出了一種基于MapReduce框架的相似性連接查詢算法MRSimJoin(MapReduce Similarity Join),該算法的核心思想是從數(shù)據(jù)集中隨機選取k個向量作為中樞,然后將每一個向量分配到距離最近的中樞所在的分區(qū),這樣可以形成k個基本分區(qū)。由于基本分區(qū)之間的向量仍有可能相似,因此,兩個不同基本分區(qū)邊界中的向量組成窗體對分區(qū)。如果某個分區(qū)的大小小于單個節(jié)點所能處理的最大向量數(shù),那么該分區(qū)就不需要再進一步劃分,可以直接這對該分區(qū)執(zhí)行相似性連接查詢操作;反之,則需要對該分區(qū)作進一步劃分。每一輪劃分都由一個MapRedcue Job來負責實現(xiàn)。

文獻[22]對MRSimJoin算法[20]進行了改進,提出了一種MapReduce框架下增量式數(shù)據(jù)相似性(MapReduce-based Similarity Join for Incremental Data Set,MRSJ_IDS)連接算法,該算法能夠支持增量式數(shù)據(jù)集的相似性連接查詢。MRSJ_IDS算法的基本思想是:首先通過抽樣的方式獲得一個樣本集合,然后對樣本集合進行聚類,將各個類的中心作為中樞,按照MRSimJoin算法中的方法對全部數(shù)據(jù)進行劃分,從而得到基本分區(qū)和窗體對分區(qū)。針對每一個分區(qū)創(chuàng)建一個KD-樹索引,并計算出相似對。對于新增數(shù)據(jù),首先根據(jù)事先確定的劃分原則找到相應的分區(qū),再根據(jù)該分區(qū)的KD-樹索引進行查詢、插入操作,從而獲得新增數(shù)據(jù)對應的相似對,并對原有的KD-樹索引進行更新。

FACET(FAst and sCalable maprEduce similariTy join)[23]以余弦相似度來衡量向量之間的相似度。由于文獻[8-10]中提出的前綴過濾方法只適用于集合數(shù)據(jù),作者針對向量數(shù)據(jù)和余弦相似度提出了新的前綴過濾機制和長度過濾機制,并結(jié)合MapReduce框架設計了并行實現(xiàn)算法FACET[23],可以快速、精確計算出所有的相似對。

SAX-Based HDSJ(Symbolic Aggregate approXimation based High-Dimensional Similarity Join)[24]采用PAA對高維向量進行降維,并在此基礎上,利用符號累積近似法(Symbolic Aggregate Approximation, SAX)轉(zhuǎn)換成SAX字符串,基于SAX可以對原始高維向量進行分組,由于SAX字符串之間的距離是向量之間原始距離的下界,因此,可以利用SAX進行有效過濾。SAX的過濾效果直接影響到相似性連接查詢的效率。為了進一步提高過濾效果和減小過濾代價,文獻[25]在SAX-Based HDSJ[24]的基礎上提出了基于多PAA的相似性連接查詢方案MP-V-SJQ。

為了減少不必要的比較,并實現(xiàn)各個計算節(jié)點的負載均衡,文獻[26]中提出了基于動態(tài)網(wǎng)格劃分的相似性連接查詢方案Grid-Based SJ(Grid-Based Similarity Join):首先通過采樣的方法進行動態(tài)網(wǎng)格劃分,并根據(jù)劃分結(jié)果構(gòu)造網(wǎng)格索引;然后依據(jù)網(wǎng)格索引對所有數(shù)據(jù)進行分配和計算,盡量確保各計算節(jié)點負載均衡。

SJT(Similarity Join Tree)[27]通過計算所有點與某個選定點之間的距離,將原始數(shù)據(jù)映射到一維空間內(nèi),并在一維空間內(nèi)使用距離閾值進行等寬劃分。如果某塊內(nèi)的數(shù)據(jù)個數(shù)超過一定閾值,可以對該塊進行進一步劃分。為了能夠較好地描述上述數(shù)據(jù)劃分思路,作者在SJT[27]中設計了相似性連接樹。既可以減少不必要的比較計算,也可以實現(xiàn)各個計算節(jié)點的負載均衡。

K最近鄰(K-Nearest Neighbor, KNN)相似性連接查詢:文獻[28]最早對基于MapReduce框架的KNN連接查詢問題進行了研究,為了減少比較次數(shù),降低網(wǎng)絡傳輸代價,文獻[28]中提出了一種基于空間填充曲線技術的近似KNN連接查詢方案zKNNJ(z-order basedK-Nearest Neighbor Join)。

zKNNJ的基本思路是:首先采用z-order方法將d維空間的點轉(zhuǎn)換成一維數(shù)據(jù),并按照z-order值進行排序;在此基礎上,d維空間的KNN連接查詢可以轉(zhuǎn)換成一維上的范圍查詢;為了提高查詢結(jié)果的準確度,可以將原始向量轉(zhuǎn)換成多個一維序列。基于上述思想,作者提出了基于MapReduce的并行計算方案H-zKNNJ。H-zKNNJ基本思路是:首先將集合R和S按照上述的轉(zhuǎn)換方法,轉(zhuǎn)換成兩個一維的序列;接著將兩個一維序列分別劃分成n個組,劃分的時候要求R和S具有相同的劃分邊界,并且要確保劃分的均衡性,作者提出了一種基于采樣技術的劃分方案;將向量進行劃分以后,對于R中的每一組Ri,從S中找出可能滿足KNN查詢要求的集合Si′(可能包含S中多個組的數(shù)據(jù)),最后將Ri和Si′中的向量進行比較即可得到KNN的查詢結(jié)果。但是H-zKNNJ也存在一些不足之處,如只能返回近似的結(jié)果、不能有效地處理較高維度的向量等。

與文獻[28]返回近似的KNN連接查詢結(jié)果不同,文獻[29]中提出了一種精確的KNN連接查詢方案,該方案主要基于維諾圖(Voronoi Diagram)對數(shù)據(jù)進行劃分。基本思路是:對于給定的兩個向量集合R和S,首先采用維諾圖把集合R劃分成k個互不相交的子集R1,R2,…,Rk;然后針對R中的每一個子集Ri,按照一定的方法,從集合S中找到一個對應的子集Si,Si需要滿足如下要求:?r∈Ri,KNN(r,S)?Si,S的各個子集之間可能會有重疊。按照上述劃分方案,集合R中的每一個子集Ri只需要與對應的子集Si進行比較,這樣就可以大大降低網(wǎng)絡傳輸?shù)拇鷥r,同時也減少很多不必要的計算。上述方案的難點有兩個:一是如何對集合R進行劃分;二是如何為R的每一個子集Ri尋找相應的Si。在利用維諾圖對集合R進行劃分時,核心是中樞(pivot)的選擇,作者分別提出了隨機選擇(random selection)、最遠選擇(farthest selection)和k-means選擇(k-means selection)三種不同的選擇方案,并分別進行了實驗驗證。實驗結(jié)果表明,該方案在處理中低維度向量時效果較好,但是無法有效處理超高維度向量。

文獻[30]在嵌套循環(huán)連接框架的基礎上,分別提出了精確KNN(Distributed Sketched Grid based KNN Join using MapReduce,DSGMP-J)連接算法和近似KNN(Voronoi Diagram based KNN Join using MapReduce,VDMP-J)連接算法。在DSGMP-J算法中,首先采用DSG(Distributed Sketched Grid)對空間進行劃分,然后針對每一個單元格內(nèi)的數(shù)據(jù)建立一個本地索引,這樣就可以利用本地的DSG索引來求出局部KNN結(jié)果。DSGMP-J方案雖然實現(xiàn)起來比較簡單,但是在進行數(shù)據(jù)劃分時,沒有考慮數(shù)據(jù)的真實分布情況,只是采用了簡單的均勻劃分方案。為了解決這一問題,作者采用維諾圖對數(shù)據(jù)進行劃分,在此基礎上,提出了一種近似的KNN查詢方案VDMP-J。

Top-k相似性連接查詢:文獻[31]中提出了基于MapReduce框架的Top-k相似性連接查詢方案。作者首先提出了兩種串行化算法,分別是divide-and-conquer算法和branch-and-bound算法;然后又提出了兩種基于MapReduce框架的并行化算法,分別是完全對劃分算法(All pair Partitioning Algorithm, TopK-P-MR)和關鍵對劃分算法(Essential Pair Partitioning Algorithm, TopK-F-MR)。TopK-P-MR算法實際上是一個嵌套循環(huán)連接算法,需要分兩個階段來實現(xiàn),首先找出局部的Top-k結(jié)果,然后再找出全局的Top-k結(jié)果。在計算局部Top-k時,可以利用到前面提出的串行化算法。但是該方案的時間復雜度是O(n2),即任意兩個向量之間都需要計算一次,計算代價過大。為了解決這一問題,作者又提出了TopK-F-MR算法,該算法首先通過采樣的方法,找出第k個最小的距離,并以該距離作為Top-k結(jié)果的距離上界,然后根據(jù)該上界對數(shù)據(jù)進行過濾和劃分,這樣就可以減少很多不必要的比較和計算,大大提高計算的效率。

針對大規(guī)模高維向量,文獻[32]中提出了一種基于MapReduce框架的并行Top-k連接查詢算法SAX-Top-k。SAX-Top-k算法首先提出了一個基于采樣技術的Top-k閾值估計方法,并結(jié)合符號累積近似法(SAX)設計了高效的過濾方案,最后結(jié)合MapReduce框架提出了基于SAX的并行Top-k連接查詢算法。

文獻[33]中針對高維數(shù)據(jù)提出了基于局部敏感哈希(Locality-Sensitive Hashing, LSH)的距離,并將基于LSH的距離轉(zhuǎn)換成高維數(shù)據(jù)簽名的海明距離,在此基礎上,設計了基于Spark的Top-k相似性連接查詢方案。與基于Hadoop的方案相比,文獻[33]方案的計算速度更快,具有更好的擴展性。

3 空間數(shù)據(jù)相似性連接查詢

空間數(shù)據(jù)相似性連接是指給定兩個空間數(shù)據(jù)集合R和S,找出所有滿足空間關系要求的空間數(shù)據(jù)對。其中,空間數(shù)據(jù)可以是點(興趣點，如一棟房子、一個商鋪、一個郵筒、一個公交站等)、線(街道)、多邊形(住宅小區(qū)、醫(yī)學圖片中的細胞等)等,空間關系可以是歐氏距離、相交(重疊)等。根據(jù)返回結(jié)果的不同,又可以分為相交連接、Top-k連接、KNN連接和空間聚集連接等。

文獻[34]中提出了一種基于MapReduce框架的空間數(shù)據(jù)連接算法SJMR(Spatial Join with MapReduce)。該算法通過一個MapReduce Job來完成,在Map階段,作者提出了一個空間劃分函數(shù),將空間對象劃分到不同的子區(qū)域中,每一子區(qū)域中的數(shù)據(jù)由一個Reduce任務負責處理。為了確保劃分的均勻性,作者提出了基于空間填充曲線的劃分方法。在Reduce階段,采用過濾-驗證框架進行處理,在過濾階段,為了提高過濾效果,作者提出了Plane Sweeping技術,從而可以減少候選對的數(shù)量。由于一個空間對象可能會被劃分到不同的子區(qū)域中,所以在Reduce端可能會出現(xiàn)很多重復的比較,作者提出了一種基于參考點的方法,從而確保一對空間數(shù)據(jù)最多只被比較一次。

文獻[35]中針對海量空間數(shù)據(jù),提出了一種基于MapReduce框架的Top-k空間連接查詢算法(Top-kSpatial Join Algorithm using MapReduce,TKSJMR),該算法要求找出k個與其他空間數(shù)據(jù)具有最大交疊數(shù)的對象。主要通過三個階段來完成,每一個階段由一個MapReduce Job來實現(xiàn)。第一個階段為空間連接階段,主要負責找出所有相交的空間數(shù)據(jù)對;第二個階段為連接結(jié)果統(tǒng)計階段,負責統(tǒng)計出每個對象與其他對象相交的總數(shù)目;第三個階段為Top-k結(jié)果獲取階段,主要是從上一階段的統(tǒng)計結(jié)果中找出相交數(shù)最大的k個對象。為了進一步提高效率,作者進行了一些優(yōu)化,如為了減少必要的比較，在空間連接階段,作者采用了基于網(wǎng)格的劃分方法;為了避免重復比較,又提出了基于參考點的方法。同時為了減少MapReduce Job的數(shù)量,作者把后面兩個階段進行了合并。

文獻[36]中提出了一種基于MapReduce框架的快速空間聚集連接查詢算法MRFM(Map-Reduce-Filter-Merge)。文獻[37]首先提出了基于MapReduce框架的并行R-tree索引構(gòu)建方法,并在R-tree索引的基礎上提出了基于MapReduce的KNN連接查詢算法。文獻[38]中針對空間連接問題,提出了一種新的“可控-復制”框架,基于該框架可以減少集群節(jié)點之間的網(wǎng)絡傳輸代價,能夠有效處理基于“重疊”和“包含”兩種謂詞的空間連接查詢問題。

文獻[39]中針對MapReduce框架下的空間關鍵字連接查詢問題進行了研究,提出了基于前綴過濾和網(wǎng)格化分技術相結(jié)合的空間文本對象過濾算法,并在此基礎上又提出了兩種優(yōu)化方法,從而進一步提升了空間關鍵字連接查詢的性能。

4 概率數(shù)據(jù)相似性連接查詢

MELODY-JOIN[41]在MapReduce框架下,針對直方圖概率數(shù)據(jù)提出了一種基于EMD距離的閾值相似性連接方案。其核心思想是:首先將原始的直方圖概率數(shù)據(jù)轉(zhuǎn)換到EMD距離的標準下界空間,然后采用特定的網(wǎng)格劃分方法對標準下界空間進行劃分;接下來計算每一個記錄與每一個單元格的EMD距離的下界,如果該下界值大于給定的閾值,則該記錄就不需要與該單元格內(nèi)的所有記錄進行比較；否則需要進一步比較。同時,為了解決負載均衡的問題,作者提出了基于Quantile Grid的劃分方法,從而使得每一個單元格包含的記錄數(shù)量近似相等。但是,MELODY-JOIN[41]需要三個MapReduce Job來實現(xiàn),需要消耗三次Job啟動時間;另外,MELODY-JOIN[41]的負載均衡策略僅僅依賴于連接負載(join workload),無法有效處理轉(zhuǎn)換空間內(nèi)的數(shù)據(jù)傾斜問題。Heads-Join[42]通過引入EMD下界和上界對MELODY-JOIN[41]進行了進一步擴展,既可以處理范圍連接(range join),又可以處理Top-k連接，并將Heads-Join框架在MapReudce、BSP和Spark模式下分別進行了實現(xiàn)。

為了解決MELODY-JOIN[41]存在的問題,文獻[43]中提出了基于映射的數(shù)據(jù)劃分框架EMD-MPJ(Mapping-based Partition Join),它只需要兩個MapReduce Job即可完成,其數(shù)據(jù)劃分方案主要是基于線性規(guī)劃的對偶理論進行設計。為了實現(xiàn)負載均衡,EMD-MPJ設計了針對Reduce端的連接代價模型,并據(jù)此進行連接負載的分配。

文獻[44]中針對大規(guī)模概率集合數(shù)據(jù)提出了兩種基于MapReduce的并行化方法:基于Map端過濾的連接和基于Reduce端過濾的連接?；贛ap端過濾的連接算法主要根據(jù)集合的存在概率,在Map端將那些沒有可能與其他任何概率集合相似的集合直接過濾掉;基于Reduce端過濾的連接算法主要采用基于概率總和以及概率上界的過濾方法來減少候選相似對的數(shù)量,從而降低計算代價。

5 字符串相似性連接查詢

林學民、李國良、王煒等學者對集中式環(huán)境下的字符串相似性連接查詢問題進行了細致深入的研究,并提出了大量創(chuàng)新性的成果[45-50]。文獻[51-53]主要探討了基于MapReduce框架的海量字符串數(shù)據(jù)可擴展相似性連接查詢問題。文獻[51]以編輯距離作為字符串間的相似性度量,以trie樹結(jié)構(gòu)為基礎,提出了一種新的索引結(jié)構(gòu)PeARL。PeARL索引由一系列trie樹構(gòu)成,每一棵trie樹用來索引以某個前綴(prefix)開頭的字符串。在進行連接查詢時,master節(jié)點首先從根節(jié)點開始逐步掃描trie樹,針對trie樹的每一對內(nèi)部節(jié)點,計算其對應前綴的編輯距離,如果大于給定的閾值,則該對節(jié)點就可以過濾掉；否則繼續(xù)往下掃描,直到遇到葉子點對(字符串節(jié)點對)時,為其生成一個map task。以此類推,為每一個可能相似的字符串節(jié)點對生成一個map task,最后以并行的方式來計算字符串之間的實際編輯距離。

文獻[52]主要對基于劃分的簽名機制進行了擴展,從而可以支持基于集合相似度(杰卡德相似度)的字符串連接。為了解決文獻[8]中存在的過濾效果不理想、數(shù)據(jù)傾斜等問題,文獻[52]中提出了一種基于劃分的簽名機制,將每個字符串按照某種規(guī)則劃分成若干個分段,如果兩個字符串相似,它們至少包含有一個相同的分段。基于該特性,就可以為每一個分段生成一個〈key,value〉對,這樣就可以取得較好的過濾效果。為了進一步減少〈key,value〉對的數(shù)量,作者又提出了一種基于合并的算法,從而可以減少網(wǎng)絡傳輸?shù)拇鷥r。文獻[53]對PassJoin(Partition-based Method for Similarity Joins)算法[54]進行了擴展,提出了一種更快的算法PassJoinK,并結(jié)合MapReduce框架,對PassJoinK算法進行并行化,提出了可擴展的字符串相似性連接查詢算法PassJoinKMRS。

6 圖數(shù)據(jù)相似性連接查詢

文獻[55]中針對海量圖數(shù)據(jù)的相似性連接查詢問題,提出了可擴展的前綴過濾方案,從而減少比較次數(shù);設計了一種有效的候選項約減方法來降低數(shù)據(jù)傳輸代價;并基于MapReduce框架設計了可擴展的圖數(shù)據(jù)相似性連接查詢算法。文獻[56]主要研究了基于編輯距離的圖相似性連接查詢問題,作者主要提出了一種基于“過濾-驗證”機制的算法MGSJoin(Graph Similarity Joins in MapReduce),采用布隆過濾器技術來減少冗余計算和網(wǎng)絡傳輸代價,并集成多路連接策略來增強驗證階段的效率。文獻[57]主要解決了海量RDF數(shù)據(jù)的連接查詢問題。針對RDF數(shù)據(jù)的SPARQL查詢往往包含很多連接操作,查詢代價比較高,當數(shù)據(jù)規(guī)模比較大時,傳統(tǒng)的單機算法無法滿足性能要求,于是文獻[57]中提出了基于MapReduce框架的高效RDF數(shù)據(jù)連接方案。首先將原始的RDF數(shù)據(jù)按照謂詞(predicate)進行分解重組,每一個謂詞對應一個謂詞文件;然后在這些謂詞文件的基礎上,把SPARQL查詢轉(zhuǎn)換成一系列的MapReduce Job,其中可能包含很多連接操作;作者提出了一種新穎的樹形結(jié)構(gòu)索引(all possible join tree)來索引所有可能的執(zhí)行計劃;最后依據(jù)代價模型來選擇最優(yōu)的查詢計劃,從而獲得最快的響應時間。

7 研究工作展望

目前,在云計算環(huán)境下針對多種不同數(shù)據(jù)類型(集合數(shù)據(jù)、空間數(shù)據(jù)、概率數(shù)據(jù)等)的大數(shù)據(jù)相似性連接查詢算法的研究已經(jīng)取得了一些成果,但是仍然存在諸多挑戰(zhàn)性問題值得進一步深入研究:

1)大規(guī)模超高維數(shù)據(jù)相似性連接查詢技術。

該研究中，對照組用遵醫(yī)護理，全面化針對性護理干預組用全面化針對性護理干預。結(jié)果顯示，全面化針對性護理干預組滿意程度、血糖空腹指標、餐后2 h指標的監(jiān)測結(jié)果、微量泵注入胰島素治療的依從性、復常血糖的時間、住院治療時間、低血糖、酮癥酸中毒等不良事件的發(fā)生率方面相比對照組更有優(yōu)勢（P＜0.05）。

“高維”是大數(shù)據(jù)的一個重要特征,基因序列、軌跡數(shù)據(jù)、視頻、音頻、圖片等非結(jié)構(gòu)化數(shù)據(jù)都具有高維特性,高維大數(shù)據(jù)的有效分析和管理是大數(shù)據(jù)面臨的一個重大挑戰(zhàn)。高維向量相似性連接查詢主要面臨兩大挑戰(zhàn):一是如何設計高效的過濾方案。當向量維度較高時,現(xiàn)有的以樹形索引為基礎的過濾方案會面臨“維度災難”問題。當向量維度逐漸增大時,索引的過濾效果逐漸降低,當維度超過一定閾值時,索引的性能甚至不如順序掃描。二是如何設計高效的可擴展算法。隨著向量維度的不斷增高,兩個向量之間相似度的計算代價會比較大;隨著參與連接的向量集合規(guī)模的不斷擴大,相似性連接的時間復雜度呈指數(shù)級增長。傳統(tǒng)的集中式處理算法已經(jīng)無法有效處理大規(guī)模超高維向量的相似性連接查詢問題。

2)復雜數(shù)據(jù)類型的大數(shù)據(jù)相似性連接查詢技術。

已有的相似性連接查詢研究工作主要集中在常見的集合數(shù)據(jù)、字符串數(shù)據(jù)和向量數(shù)據(jù)。然而,除了這三種數(shù)據(jù)類型之外,還有很多結(jié)構(gòu)更為復雜的數(shù)據(jù)類型,如軌跡數(shù)據(jù)、時間序列、基因數(shù)據(jù)、流數(shù)據(jù)、圖和XML文檔等。這些數(shù)據(jù)的結(jié)構(gòu)往往更為復雜,相似度的計算代價更高,并且,由于類型不同,已有的相似性連接查詢技術并不能有效處理這些更為復雜的數(shù)據(jù)類型。因此,需要針對這些復雜數(shù)據(jù)類型的結(jié)構(gòu)和特點,研究新的相似度計算方法、過濾技術和并行化方案。

3)增量式大數(shù)據(jù)相似性連接查詢技術。

目前的大數(shù)據(jù)相似性連接查詢技術大都是基于MapRedcue框架,然而,MapRecduce是一種批處理模型,無法有效處理實時查詢和增量式查詢?；赟park等新的計算框架的增量式大數(shù)據(jù)相似性連接查詢技術,有待進一步深入研究。

4)基于哈希學習的近似KNN連接查詢技術。

局部敏感哈希技術是解決海量高維向量KNN連接查詢的一種有效方案。常用的局部敏感哈希函數(shù)雖然具有位置敏感性,但并不能有效保證哈希映射前后數(shù)據(jù)之間的相對位置關系,影響KNN連接查詢結(jié)果的質(zhì)量。將哈希學習思想與局部敏感哈希技術相結(jié)合,通過學習的方法來對局部敏感哈希函數(shù)進行學習,使得學習到的LSH函數(shù)能夠最大限度地保持哈希映射前后數(shù)據(jù)之間的相對位置關系。在此基礎上,結(jié)合MapReduce框架,研究高維向量并行近似KNN連接查詢算法,有效應對擴展性問題。

隱私保護是大數(shù)據(jù)時代的一個重要研究課題。軌跡數(shù)據(jù)、基因數(shù)據(jù)、社交網(wǎng)絡數(shù)據(jù)等都包含了大量的個人敏感信息,如何在確保相似度計算準確性和效率的同時,又能最大限度地保護隱私數(shù)據(jù),成為一個亟待解決的研究課題。目前,面向隱私保護的大數(shù)據(jù)相似性連接查詢技術研究工作還處于起步階段,需要進一步深入研究,例如,可以嘗試將差分隱私等最新的隱私保護技術應用到大數(shù)據(jù)相似性連接查中。

8 結(jié)語

相似性連接查詢是一種十分重要的操作,在很多數(shù)據(jù)挖據(jù)和數(shù)據(jù)分析任務中都有應用。隨著數(shù)據(jù)規(guī)模的不斷增長,針對大數(shù)據(jù)的相似性連接查詢問題出現(xiàn)了新的挑戰(zhàn)。本文針對集合、向量、空間數(shù)據(jù)、概率數(shù)據(jù)等不同類型大數(shù)據(jù)的相似性連接查詢技術相關工作進行了深入研究,對其優(yōu)缺點進行了歸納總結(jié)，最后指出了大數(shù)據(jù)相似性連接查詢面臨的若干挑戰(zhàn)性問題。

參考文獻(References)

[1] 龐俊,谷峪, 許嘉, 等. 相似性連接查詢技術研究進展[J]. 計算機科學與探索, 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 & Technology, 2013, 7(1): 1-13.)

[2] 林學民, 王煒. 集合和字符串的相似度查詢[J]. 計算機學報, 2011, 34(10): 1853-1862.(LIN X M, WANG W. Set and string similarity queries: a survey[J]. Chinese Journal of Computers, 2011, 34(10): 1853-1862.)

[3] YU M H, LI G L, DENG D, et al. String similarity search and join: a survey[J]. Frontiers of Computer Science, 2016, 10(3): 399-417.

[4] 龐俊, 于戈, 許嘉, 等.基于MapReduce框架的海量數(shù)據(jù)相似性連接研究進展[J]. 計算機科學, 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.)

[5] SILVA Y, REED J, BROWN K, et al. An experimental survey of MapReduce-based similarity joins[C]// Proceedings of the 9th International Conference on Similarity Search and Applications. Berlin: Springer, 2016: 181-195.

[6] KIMMETT B, SRINIVASAN V, THOMO A. Fuzzy joins in MapReduce: an experimental study[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1514-1517.

[7] LIN J. Brute force and indexed approaches to pairwise document similarity comparisons with MapReduce[C]// Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2009: 155-162.

[8] 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. New York: ACM, 2010: 495-506.

[9] 李瑞, 王朝坤, 鄭偉, 等.基于MapReduce框架的近似復制文本檢測[J]. 計算機研究與發(fā)展, 2010, 47(增刊1): 400-406.(LI R, WANG C K, ZHENG W, et al. Near duplicate text detection based on MapReduce[J]. Journal of Computer Research and Development, 2010, 47(S1): 400-406.)

[10] RONG C T, 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.

[11] ELSAYED T, LIN J, OARD D. Pairwise document similarity in large collections with MapReduce[C]// HLT-Short 2008: Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies. Stroudsburg, PA, USA: ACL, 2008: 265-268.

[12] METWALLY A, FALOUTSOS C. V-SMART-Join: a scalable MapReduce framework for all-pair similarity joins of multisets and vectors[J]. Proceedings of the VLDB Endowment, 2012, 5(8): 704-715.

[13] BARAGLIA R, MORALES G, LUCCHESE C. Document similarity self-join with MapReduce[C]// Proceedings of the 10th IEEE International Conference on Data Mining. Piscataway, NJ: IEEE, 2010: 731-736.

[14] RONG C T, LIN C B, SILVA Y, et al. Fast and scalable distributed set similarity joins for big data analytics[C]// Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Piscataway, NJ: IEEE, 2017: 1-12.

[15] DENG D, LI G L, WEN H, et al. An efficient partition based method for exact set similarity joins[J]. Proceedings of the VLDB Endowment, 2015, 9(4): 360-371.

[16] WANG J J, LIN C. MapReduce based personalized locality sensitive hashing for similarity joins on large scale data[J]. Computational Intelligence and Neuroscience, 2015, 2015: Article No. 37.

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

[18] SEIDL T, FRIES S, BODEN B. MR-DSJ: distance-based self-join for large-scale 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.

[19] FRIES S, BODEN B, STEPIEN G, et al. PHiDJ: parallel similarity self-join for high-dimensional vector data with MapReduce[C]// Proceedings of the 30th IEEE International Conference on Data Engineering. Piscataway, NJ: IEEE, 2014: 796-807.

[20] SILVA Y N, REED J M, TSOSIE L M. MapReduce-based similarity join for metric spaces[C]// Proceedings of the 1st International Workshop on Cloud Intelligence. New York: ACM, 2012: Article No. 3.

[21] SILVA Y N, REED J M. Exploiting MapReduce-based similarity joins[C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 693-696.

[22] 徐媛媛, 陳華輝. 基于MapReduce增量式數(shù)據(jù)集的相似性連接[J]. 計算機應用研究, 2014, 31(11): 3369-3384.(XU Y Y, CHEN H H. MapReduce-based similarity join for incremental data set[J]. Application Research of Computers, 2014, 31(11): 3369-3384.)

[23] YANG B, KIM H, SHIM J, et al. Fast and scalable vector similarity joins with MapReduce[J]. Journal of Intelligent Information Systems, 2016, 46(3): 473-497.

[24] MA Y Z, MENG X F, WANG S Y. Parallel similarity joins on massive high-dimensional data using MapReduce[J]. Concurrency and Computation: Practice and Experience, 2016, 28(1): 166-183.

[25] MA Y Z, JIA S J, ZHANG Y X. A novel approach for high-dimensional vector similarity join query[J]. Concurrency and Computation: Practice and Experience, 2017, 29(5): 1-12.

[26] JANG M Y, SONG Y, CHANG J. A density-aware similarity join query processing algorithm on MapReduce[M]// PARK J J, JIN H, KHAN M K, et al. Advanced Multimedia and Ubiquitous Engineering. Berlin: Springer, 2016: 469-475.

[27] LIU W, SHEN Y M, WANG P. An efficient MapReduce algorithm for similarity join in metric spaces[J]. The Journal of Supercomputing, 2016, 72(3): 1179-1200.

[28] 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.

[29] 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.

[30] 戴健, 丁治明. 基于MapReduce快速kNN Join方法[J]. 計算機學報, 2015, 38(1): 99-108.(DAI J, DING Z M. MapReduce based fast kNN join[J]. Chinese Journal of Computers, 2015, 38(1): 99-108.)

[31] KIM Y, SHIM K. Parallel Top-Ksimilarity join algorithms using MapReduce[C]// Proceedings of the 2012 IEEE 28th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2012, 510-521.

[32] 馬友忠, 慈祥. 海量高維向量的并行Top-k連接查詢[J]. 計算機學報, 2015, 38(1): 86-98.(MA Y Z, CI X. Parallel Top-kjoin on massive high-dimensional vectors[J]. Chinese Journal of Computers, 2015, 38(1): 86-98.)

[33] CHEN D H, SHEN C G, FENG J Y, et al. An efficient parallel Top-ksimilarity join for massive multidimensional data using spark[J]. International Journal of Database Theory and Application, 2015, 8(3): 57-68.

[34] ZHANG S B, HAN J Z, LIU Z Y, et al. SJMR: parallelizing spatial join with MapReduce on clusters[C]// Proceedings of 2009 IEEE International Conference on Cluster Computing and Workshops. Piscataway, NJ: IEEE, 2009: 1-8.

[35] 劉義, 陳犖, 景寧, 等. 海量空間數(shù)據(jù)的并行Top-k連接查詢[J]. 計算機研究與發(fā)展, 2011, 48(增刊3): 163-172.(LIU Y, CHEN L, JING N, et al. Parallel Top-kspatial join query processing on massive spatial data[J]. Journal of Computer Research and Development, 2011, 48(S3): 163-172.)

[36] LIU Y, CHEN L, JING N, et al. MRFM: an efficient approach to spatial join aggregate[C]// Proceedings of the WAIM 2012 International Workshops: GDMM, IWSN, MDSP, USDM, and XMLDM. Berlin: Springer, 2012, 140-150.

[37] 劉義, 景寧, 陳犖, 等. MapReduce框架下基于R-樹的k-近鄰連接算法[J]. 軟件學報, 2013, 24(8): 1836-1851.(LIU Y, JING N, CHEN L, et al. Algorithm for processingk-nearest join based on R-tree in MapReduce[J]. Journal of Software, 2013, 24(8): 1836-1851.)

[38] GUPTA H, CHAWDA B, NEGI S, et al. Processing multi-way spatial joins on Map-Reduce[C]// Proceedings of the 16th International Conference on Extending Database Technology. New York: ACM, 2013, 113-124.

[39] ZHANG Y, MA Y, MENG X. Efficient spatio-textual similarity join using MapReduce [C]// Proceedings of the 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies. Piscataway, NJ: IEEE, 2014: 52-59.

[40] 雷斌, 許嘉, 谷峪, 等. 概率數(shù)據(jù)上基于EMD距離的并行Top-k相似性連接算法[J]. 軟件學報, 2013, 24(增刊2): 188-199.(LEI B, XU J, GU Y, et al. Parallel Top-ksimilarity join algorithm on large probabilistic data based on earth mover’s distance[J]. Journal of Software, 2013, 24(S2): 188-199.)

[41] HUANG J, ZHANG R, BUYYA R, et al. MELODY-JOIN: efficient earth mover’s distance similarity joins using MapReduce[C]// Proceedings of the 30th IEEE International Conference on Data Engineering. Piscataway, NJ: IEEE, 2014: 808-819.

[42] HUANG J, ZHANG R, BUYYA R, et al. Heads-Join: efficient earth mover’s distance similarity joins on Hadoop[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(6): 1660-1673.

[43] XU J, LEI B, GU Y, et al. Efficient similarity join based on earth mover’s distance using MapReduce[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8): 2148-2162.

[44] MA Y Z, MENG X F. Set similarity join on massive probabilistic data using MapReduce[J]. Distributed and Parallel Databases, 2014, 32(3): 447-464.

[45] WANG J N, LI G L, FENG J H. Extending string similarity join to tolerant fuzzy token matching[J]. ACM Transactions on Database Systems, 2014, 39(1) : Article No. 7.

[46] LI G L, DENG D, FENG J H. Pass-Join+: a partition-based method for string similarity joins with edit-distance constraints[J]. ACM Transactions on Database Systems, 2013, 38(2) : Article No. 9.

[47] JIANG Y, LI G, FENG J H, et al. String similarity joins: an experimental evaluation[J]. Proceedings of the VLDB Endowment, 2014, 7(8): 625-636.

[48] WANG W, QIN J B, XIAO C, et al. VChunkJoin: an efficient algorithm for edit similarity joins[J]. IEEE Transactions on Knowledge & Data Engineering, 2013, 25(8): 1916-1929.

[49] LU J H, LIN C B, WANG W, et al. String similarity measures and joins with synonyms[C]// SIGMOD 2013: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 373-384.

[50] XIAO C, WANG W, LIN X M, et al. Efficient similarity joins for near duplicate detection[J]. ACM Transaction of Database Systems, 2011, 36(3): Article No. 15.

[52] DENG D, LI G L, HAO S, et al. MassJoin: a MapReduce-based algorithm for string similarity joins[C]// Proceedings of IEEE 30th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2014: 340-351.

[53] LIN C, YU H Y, WENG W, et al. Large scale similarity join with edit-distance constraints[C]// Proceedings of 19th International Conference on Database Systems for Advanced Applications. Berlin: Springer, 2014: 328-342.

[54] LI G L, DENG D, WANG J N, et al. Pass-join: a partition-based method for similarity joins[J]. Proceedings of the VLDB Endowment. Berlin: Springer, 2011, 5(3): 253-264.

[55] PANG J, GU Y, XU J, et al. Efficient graph similarity join with scalable prefix-filtering using MapReduce[C]// Proceedings of 15th International Conference on Web-Age Information Management. Berlin: Springer, 2014: 415-418.

[56] CHEN Y F, ZHAO X, GE B, et al. Practising scalable graph similarity joins in MapReduce[C]// Proceedings of the 2014 IEEE International Congress on Big Data. Washington, DC: IEEE Computer Society, 2014: 112-119.

[57] ZHANG X F, CHEN L, WANG M. Towards efficient join processing over large RDF graph using MapReduce[C]// Proceedings of the 24th International Conference on Scientific and Statistical Database Management. Berlin: Springer, 2012: 250-259.

This work is partially supported by the National Natural Science Foundation of China (61602231), the National Key R&D Plan Project (2016YFE0104600), the Science and Technology Open Cooperation Project of Henan Province (172106000077, 152106000048), the Key Scientific Research Project of Higher Education of Henan Province (16A520022).