大數(shù)據(jù)相似性連接查詢技術(shù)研究進(jìn)展

馬友忠,張智輝,林春杰

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

0 引言

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

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

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

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

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

1 集合相似性連接查詢

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

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

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

1)窮舉方案。

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

2)前綴過濾。

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

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

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

3)Word-Count-Like方案。

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

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

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

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

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

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

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

2 向量相似性連接查詢

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

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

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

表3 向量相似性連接查詢技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 字符串相似性連接查詢

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

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

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

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

7 研究工作展望

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

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

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

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

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

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

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

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

4)基于哈希學(xué)習(xí)的近似KNN連接查詢技術(shù)。

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

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

8 結(jié)語

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

參考文獻(xiàn)(References)

[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 & Technology, 2013, 7(1): 1-13.)

[2] 林學(xué)民, 王煒. 集合和字符串的相似度查詢[J]. 計(jì)算機(jī)學(xué)報(bào), 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ì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.)

[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框架的近似復(fù)制文本檢測(cè)[J]. 計(jì)算機(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]. 計(jì)算機(jī)應(yīng)用研究, 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]. 計(jì)算機(jī)學(xué)報(bào), 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]. 計(jì)算機(jī)學(xué)報(bào), 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]. 計(jì)算機(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]. 軟件學(xué)報(bào), 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]. 軟件學(xué)報(bào), 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).