對偶連接問題的哈希算法研究.pdf

1、在信息檢索和數(shù)據(jù)庫應(yīng)用中，一種常見的查詢方式是從一組數(shù)據(jù)對象(如文檔，圖像)中返回符合條件的成對對象，例如，在數(shù)據(jù)庫應(yīng)用中經(jīng)常需要根據(jù)相似度將兩個相似的文檔或者網(wǎng)頁作為結(jié)果返回給用戶，這樣的操作在最近的研究工作中定義為相似性連接。在本文中，我們將這一類典型的查詢形式進一步擴展為對偶連接問題。對應(yīng)的問題描述為，給定一組數(shù)據(jù)對象和操作在對象上的關(guān)系度量(如相似度或相關(guān)性系數(shù))找到所有符合關(guān)系度量閾值條件的對象對。由于問題定義的簡單性和其中所

2、定義的關(guān)系度量的多樣性，對偶連接問題在各種不同領(lǐng)域的問題中扮演核心的角色，例如，副本檢測，關(guān)聯(lián)規(guī)則挖掘，統(tǒng)計相關(guān)性分析，協(xié)同過濾等。同時，在技術(shù)上的挑戰(zhàn)性也使這一問題在以往的研究工作中得到廣泛的關(guān)注?；诒苊鈱λ袑ο蟮膬蓛杀容^的動機，一系列適用于不同數(shù)據(jù)類型和關(guān)系度量的啟發(fā)式剪枝算法被開發(fā)出來，其中有代表性的如倒排表索引，前綴/后綴過濾，準(zhǔn)單調(diào)性剪枝等等。
　　然而，這一類基于啟發(fā)式的方法在解決問題時，其執(zhí)行性能仍然收到一些內(nèi)在

3、缺陷的負面影響，例如剪枝的效果得不到保證，無法針對不同特征的數(shù)據(jù)集優(yōu)化算法性能，以及缺乏一種通用的算法模型等。進一步的優(yōu)化在確定性的算法框架下難以達到。近來，很多研究發(fā)現(xiàn)僅僅得到近似的結(jié)果在現(xiàn)實中很多查詢應(yīng)用中可以被接受，并且這種做法可以大幅度降低查詢的時間。這樣的原則也同樣適用于對偶連接問題，因此，本文重點關(guān)注利用一組隨機算法高效的處理“近似版本”的對偶連接問題。在這樣的情況下，一組值得關(guān)注的問題是：(1)在面對大規(guī)模數(shù)據(jù)時，是否可以

4、將原始數(shù)據(jù)通過隨機模式轉(zhuǎn)化為規(guī)模小到可以裝入內(nèi)存的“概要”，并且通過處理概要來執(zhí)行關(guān)系度量下的查詢；(2)能否以較小的代價(如通過概要)足夠精確地估計對象之間的關(guān)系度量的值；(3)怎樣在解決問題時盡可能避免對象之間的兩兩比較，或者說是否可以采用一種剪枝方法將不符合條件的結(jié)果盡可能地去除。
　　本文中發(fā)現(xiàn)在空間最近鄰中廣泛使用的Locality-sensitiveHashing(LSH)思想為對偶連接問題的解決提供了一個很好的借鑒。

5、類似的哈希映射模式在對偶連接問題中成為從原始數(shù)據(jù)生成概要的理想選擇。在此基礎(chǔ)上，本文為了高效執(zhí)行對偶連接查找提出了一組基于隨機模式的解決方案，其中所有的算法模型均基于哈希模式生成的概要進行操作，因此稱之為哈希算法?？偨Y(jié)起來，本文工作在理論模型方面主要的貢獻包括：
　　(1)研究了所定義的哈希模式的存在性與關(guān)系度量之間的關(guān)系，給出了哈希模式對于度量存在的一組必要條件。這一部分的結(jié)論實際上也給出了哈希算法的適用范圍。具體地說，我們首先

6、從以往研究中的抽樣技術(shù)和擾動算法中抽象出一組針對常用關(guān)系度量的哈希模式，并根據(jù)這些典型的實例歸納和證明出一組哈希模式對于度量存在性的必要條件。
　　(2)提出了一個對關(guān)系度量的區(qū)間估計模型。區(qū)間估計模型與早期工作中的期望估計模式相比，具有在分析上可證和執(zhí)行上可控的估計精度，并且可以通過調(diào)整參數(shù)優(yōu)化整體剪枝算法的效率。在分析方面，我們證明區(qū)間估計模型在解決對偶連接問題所需哈希演算的次數(shù)(代表主要的時空代價)為O(ε-2logn)(n

7、代表對象總數(shù))；在執(zhí)行方面，我們討論了估計模型所需的數(shù)據(jù)結(jié)構(gòu)并對算法整體的時間和空間復(fù)雜度進行了分析，并且通過在真實數(shù)據(jù)集上的執(zhí)行結(jié)果揭示了區(qū)間估計模型與之前工作中的期望估計模型比較在性能上的優(yōu)勢。
　　(3)設(shè)計一個高效的隨機過濾器模型。這類模型相比估計模型在執(zhí)行上具有更小的時間/存儲需求。這里首先歸納和分析了移植自最近鄰問題中LSH技術(shù)的原始過濾器模型(稱為BasicLSH，簡稱B-LSH)，指出了其在處理對偶連接問題時的不足

8、。隨后，我們提出了具有更高效率的近似隨機過濾器模型(ApproximationLSH，簡稱A-LSH)，使得所需的哈希演算次數(shù)從B-LSH模式的O(n1/1+ε)級降低至O(ε-2logn)級。并且，我們證明A-LSH過濾器模型所具有的性質(zhì)使其克服了原始B-LSH模式的性能瓶頸。
　　在應(yīng)用方面，我們將提出的通用估計模型和通用過濾器模型分別置于一組實際應(yīng)用問題中，針對每一個具體問題對隨機模型進行擴展和調(diào)整，使之適用于具體的問題環(huán)境

9、，并藉此揭示不同隨機模型在執(zhí)行時的內(nèi)部行為和性能特性。這部分工作所涉及的主要內(nèi)容包括：
　　(1)置信度估計和快速挖掘置信度關(guān)聯(lián)規(guī)則。從不頻繁的項中挖掘具有高置信度的關(guān)聯(lián)在很多實際應(yīng)用中扮演重要的角色。通過對估計模型進行擴展和變型可以設(shè)計一個適用與置信度的區(qū)間估計模式并由此得到一個高效的剪枝算法進行快速的置信度關(guān)了規(guī)則挖掘。通過在真實和人工數(shù)據(jù)上執(zhí)行的實驗表明，由此得到的剪枝算法在執(zhí)行時間，可擴展性等各項性能指標(biāo)上明顯優(yōu)于基于樹計

10、數(shù)結(jié)構(gòu)的確定性算法。對這一應(yīng)用問題的解決體現(xiàn)了通用估計模型的理論適用范圍可通過在原有基礎(chǔ)上設(shè)計新模式得到有效的擴展。
　　(2)在Pearson統(tǒng)計相關(guān)系數(shù)下識別高度相關(guān)項。在統(tǒng)計相關(guān)性度量下發(fā)現(xiàn)具有高度相關(guān)性的項在機器學(xué)習(xí)、數(shù)據(jù)庫等領(lǐng)域具有重要的現(xiàn)實意義。通常使用的基于上界準(zhǔn)單調(diào)性的啟發(fā)式剪枝方法的執(zhí)行效果不盡理想。我們發(fā)現(xiàn)Pearson系數(shù)可被隨機過濾器模型處理，特別地，根據(jù)問題本身的特點使用A-LSH模式構(gòu)造的算法在執(zhí)行時間

11、以及數(shù)據(jù)規(guī)模的適應(yīng)性上均明顯優(yōu)于啟發(fā)式方法和B-LSH過濾器算法，特別是在B-LSH方法出現(xiàn)瓶頸的低閾值條件下，效率提升更為明顯。對此問題的解決過程體現(xiàn)了對隨機過濾器模型適用條件的進一步擴展，并從執(zhí)行上體現(xiàn)了A-LSH模式帶來的顯著的性能提升。
　　(3)加權(quán)集合相似度下的相似性連接。在描述查找對象時附加權(quán)重信息通常會顯著增加查詢的精度，但同時也加大了技術(shù)上的挑戰(zhàn)性。針對加權(quán)集合相似度，我們構(gòu)造對應(yīng)的哈希模式從而得到區(qū)間估計模型；

12、同時提出一個執(zhí)行更加簡單且具有更高時間空間效率的隨機算法，即通過基于Cauthy的分布LSH函數(shù)得到的過濾模式算法，實驗證明后者與基于估計模型的算法相比具有更高的執(zhí)行效率。對該應(yīng)用問題的處理體現(xiàn)了在可以同時適用估計模型和過濾器模型時使用不同哈希模式以及相應(yīng)的不同模型對于執(zhí)行效率的影響。
　　總而言之，本文重點關(guān)注在信息檢索、數(shù)據(jù)庫以及數(shù)據(jù)挖掘等領(lǐng)域中廣泛存在的一類查詢形式--對偶連接查詢以及對該問題的基于隨機模式的解法。為此，我們