對(duì)偶連接問題的哈希算法研究.pdf

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

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

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

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

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

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

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

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

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

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

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

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