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

馬友忠 賈世杰 張永新

摘要：為了解決高維數據相似性連接查詢中存在的維度災難和計算代價高等問題，基于p穩態分布，將高維數據映射到低維空間。根據卡方分布的性質，證明了如果低維空間的距離大于kε，則原始空間距離大于ε的概率具有一定的下界，從而可以在低維空間以較低的計算代價進行有效過濾。在此基礎上，提出了基于卡方分布的高維數據相似性連接查詢算法。為了進一步提高查詢效率，提出了基于雙重過濾的高維數據相似性連接查詢算法。利用真實數據集進行了實驗，實驗結果表明所提方法具有較好的性能。基于卡方分布的相似性連接查詢算法召回率可以達到90%以上。基于雙重過濾的相似性連接查詢算法可以進一步提高性能，但是會損失一定的召回率。對時間性能要求比較高、對召回率要求不太嚴格的查詢任務可以采用基于雙重過濾的相似性連接查詢算法；反之，可以采用基于卡方分布的相似性連接查詢算法。

關鍵詞：

相似性連接查詢；高維數據；卡方分布；p穩態分布；召回率

中圖分類號： TP311.13 文獻標志碼：A

0引言

高維數據相似性連接查詢是一種十分重要且應用廣泛的操作，是許多數據挖掘、機器學習任務的基礎操作，如圖片聚類、視頻副本檢測、文檔去重等。由于維度災難的存在，高維數據的相似性連接查詢面臨巨大挑戰，傳統的以樹形索引結構為基礎的查詢算法已無法奏效。

經過深入分析和推理，作者發現基于穩態分布和卡方分布的特點，可以將數據從高維空間映射到低維空間，并且可以通過計算低維空間的距離來進行過濾，同時保證如果低維空間的距離大于kε，則原始空間距離大于ε的概率具有一定的下界。本文基于該重要觀察提出了一種基于卡方分布的高維數據相似性連接查詢算法，主要貢獻如下：

1）提出了基于穩態分布的降維方法，并證明了利用低維空間距離進行過濾的概率下界，具有較好的過濾效果；

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

3）針對真實數據集做了深入細致的實驗，對本文所提出的方案進行了認真分析。實驗結果表明，本文所提方案具有較好的性能。

1相關工作

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

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

文獻[4]提出了EGO（Epsilon Grid Order）方法，可以用來處理大規模高維數據的相似性連接查詢。該方法將整個數據空間劃分成等寬（ε）的若干個格子，并按照一定的機制將所有的格子進行編號排序，最后采取一定的算法對這些格子內的數據進行一一比較。由于該方法不需要額外的內存來存儲索引結構，因此具有較好的擴展性。

文獻[5]在EGO[4]的基礎上提出了一種改進算法——SuperEGO。該算法主要采用基于數據驅動的維度重排序機制，設計了一種新穎的EGO策略，能夠大大地減少不必要的計算；同時也開發了并行版本，具有較好的執行效率。

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

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

文獻[9]基于時間序列中的分段累積近似法（Piecewise Aggregate Approximation， PAA）提出了一種新的降維方法，可以將高維數據降到低維空間，并且低維空間的距離是原始距離的下界。基于該性質，可以以較低的代價進行有效過濾。同時，作者將該技術并行化，提出了兩種基于MapReduce框架的并行連接查詢算法，能夠有效地處理大規模高維數據。

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

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

2預備知識

2.1問題定義

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

2.2p穩態分布與卡方分布

定義2p穩態分布。對于一個分布D，如果存在p≥0，對任何d個實數v1，v2，…，vd和d個滿足D分布的獨立同分布的變量X1，X2，…，Xd，隨機變量∑iviXi與（∑di=1vpi）1/pX具有相同的分布，其中X是服從D分布的一個隨機變量，則稱D是一個p穩態分布。

當p∈（0，2]時都存在p穩態分布，當p=2時，高斯分布（即正態分布）就是2穩態分布。

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

定義3卡方分布。如果X1，X2，…，Xm是服從標準正態分布N（0，1）的獨立、同分布隨機變量，令S2=∑mi=1X2i，則S2服從自由度為m的卡方分布，記為：S2～χ2（m）。

2.3常用符號說明

常用符號說明如表1所示。

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

3.1相關定理

令g（v）=v·a，其中向量a的每一個元素都是服從標準正態分布N（0，1）的獨立、同分布隨機變量。可得如下引理。

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

定理2的含義是：如果向量v1，v2的m維映射的距離大于kε，則v1和v2的歐氏距離大于ε的概率大于1-P（χ2>k2）。基于該性質，可以將高維向量v1，v2映射到低維空間內，通過計算低維空間的距離來進行過濾，從而降低過濾的計算代價。

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

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

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

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

有序號的程序——————————Shift+Alt+Y

程序前

輸入：S，n，ε，m，此處有5個變量，但后面的說明中卻只有4個，是否說明有遺漏？請明確。回復：是新向量集合，在算法第1）行已有說明，為排版美觀，在這沒有再作說明。//數據集合、數據規模、距離閾值、映射空間維度

輸出：相似向量對和距離。

1）

=，Q=；//新向量集合和結果集合

2）

隨機選擇m個向量a1，a2，…，am，e∈ai～N（0，1）；

3）

對于S中的每一個向量v

4）

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

5）

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

6）

對于中的每一個向量對（1，2）

7）

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

8）

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

9）

計算原始距離dist（v1，v2）；

10）

如果 dist（v1，v2）≤ε

11）

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

12）

輸出結果集合Q；

程序后

3.3基于雙重過濾的相似性連接查詢

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

證明過程如定理2。

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

4實驗分析

本章將對提出的基于卡方分布的相似性連接查詢（chisquare distributionbased Similarity Join Query， χ2SJQ）算法和基于雙重過濾的相似性連接查詢（Similarity Join Query based on Double Filtering DFχ2SJQ）算法與嵌套循環連接（Nested Loop Join， NLJ）算法對比進行實驗驗證。驗證指標主要包括算法運行時間（run time）和召回率（recall）。由于最終的結果都經過驗證階段，所以準確率（precision）為100%。

4.1實驗環境設置

實驗環境實驗運行的計算機配置如下：CPU為Intel Core i54210H 2.90GHz，內存為8GB，磁盤為1TB，操作系統為64bit Windows 7。實驗中的相關參數如表2所示，加下劃線的數字表示默認值。

4.2距離閾值變化（ε）

圖2顯示了距離閾值的變化對運行時間和召回率的影響。從圖2中可以看出，在距離閾值小于0.3時，算法 χ2SJQ和算法DFχ2SJQ的性能差別不大；但是，隨著距離閾值的增大，結果數量也會急劇增加，此時，算法DFχ2SJQ的性能更好；但是，算法DFχ2SJQ的性能是以犧牲一定的召回率來換得的，因此，實際應用中需要在運行時間和召回率之間進行適當的權衡。

4.3維度變化（d）

圖3顯示了算法性能與向量維度之間的關系。直觀上分析，隨著維度的增加，運行時間應該增大；但是，從圖3中看出，部分節點出現異常。通過對結果進行深入分析發現，實驗中統計的運行時間包括計算時間和把運行結果寫入文件的時間。維度越大，計算時間肯定越大；但是數據寫入花費的時間卻不一定。從實驗結果看出，d=256時，結果數據量分別是425551814，421966225和393140173；而d=960時，最終的計算結果數量分別是4444884，4190456和2704272，因此，才會出現圖3中所示的情況。

4.4數據集大小變化（n）

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

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

圖5描述了映射空間維度對算法性能的影響。整體來看，映射空間維度越大，算法DFχ2SJQ的運行時間也會越長，而算法χ2SJQ的運行時間卻逐步下降，但仍大于前者。

4.6過濾效果概率下界對性能的影響

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

5結語

高維數據的相似性連接查詢是一種計算代價較高的操作。本文基于p穩態分布，將原始d維數據映射到m維（m

未來將對本文方案作進一步的優化：目前在m維空間進行距離計算的時候，采取的是窮舉法，即所有的m維向量兩兩進行比較，未來可以對m維空間（低維空間）的距離計算進行優化；另外，本文所處理的數據集規模比較有限，未來將結合目前流行的云計算平臺，重點研究并行化方案，用于處理大規模數據集的相似性連接查詢；同時，未來還將對其他類型的相似性連接查詢問題進行研究，如KNN連接查詢、Topk連接查詢等。

參考文獻：

[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 and Technology， 2013， 7（1）： 1-13.）

[2]

龐俊，于戈，許嘉，等.基于MapReduce框架的海量數據相似性連接研究進展[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.）

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

劉義，陳犖，景寧，等.海量空間數據的并行Topk連接查詢[J].計算機研究與發展，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]

雷斌，許嘉，谷峪，等.概率數據上基于EMD距離的并行Topk相似性連接算法[J].軟件學報，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.