Scalable Similarity Search for SimRank相似性評價(jià)度量

1、Scalable Similarity Search for SimRankScalable Similarity Search for SimRank論文方向：相似度評價(jià)算法論文級別：SIGMOD會議，CCF推薦A類基于SimRank模型的可擴(kuò)展相似性搜索目 錄論文背景簡介SimRank論文主要工作總結(jié)123SimRank什么是SimRank1SimRank 是一種基于圖的拓?fù)浣Y(jié)構(gòu)信息來衡量任意兩個(gè)對象間相似程度兩個(gè)對象間相似程度的模型，該模型由 MIT 實(shí)驗(yàn)室的 Glen Jeh 和 Jennifer Widom教授在2002年首先提出。SimRank相似度的核心思想為：如果兩個(gè)對象和被其

2、相似的對象所引用（即它們有相似的入鄰邊結(jié)構(gòu)），那么這兩個(gè)對象也相似。SimRank模型定義SimRank2SimRank 模型定義兩個(gè)頁面的相似度是基于如下遞歸的公式：網(wǎng)頁排名協(xié)同過濾近似查詢網(wǎng)絡(luò)圖聚類SimRankSimRank的應(yīng)用3論文主要工作論文摘要1由Jeh和Widom教授提出的SimRank模型提供了一個(gè)很好的相似性指數(shù)，并且已經(jīng)成功應(yīng)用于許多提到的應(yīng)用之中。迄今為止，盡管已經(jīng)提出了很多算法來計(jì)算SimRank，但是沒一個(gè)算法能夠擴(kuò)展到一個(gè)具有十億數(shù)量級的圖之中來。由此項(xiàng)事實(shí)激勵(lì)我們考慮以下的SimRank相似性搜索問題：給定一個(gè)查詢節(jié)點(diǎn)u，查找對于u來說擁有最高SimRank指數(shù)

3、的前k個(gè)節(jié)點(diǎn)v，該指數(shù)可表述為s(u,v)。我們提出了一個(gè)高效且可擴(kuò)展的計(jì)算SimRank搜索問題的算法。在十億級別邊的圖中，該算法可以在 幾秒之內(nèi)計(jì)算出給定節(jié)點(diǎn)u的的top-20相似性節(jié)點(diǎn)。論文主要工作四大要素2 線性遞歸表達(dá)式s(u, v) = euDev +c(Peu)DPev +c2(P2eu)DP2ev + 兩個(gè)上界值xy max xew xy |x| |y| SimRank指數(shù)的距離衰減特性 蒙特卡羅模擬論文主要工作SimRank線性遞歸公式變換3論文主要工作top-k相似性搜索算法4預(yù)處理構(gòu)建原圖的二分圖，由蒙特卡羅模擬確定二分圖的邊。第一次篩選出候選節(jié)點(diǎn)。計(jì)算兩個(gè)相似度界限。查

4、詢由兩個(gè)相似度界限剪除冗余節(jié)點(diǎn)。運(yùn)用適應(yīng)性選樣加速篩選節(jié)點(diǎn)，一次設(shè)置隨機(jī)游走的次數(shù)較少，第二次篩選出候選點(diǎn)后進(jìn)行二次精確計(jì)算SimRank值，選出前K個(gè)點(diǎn)。總結(jié)論文的創(chuàng)新點(diǎn) 提出SimRank的線性遞歸表達(dá)式，結(jié)合蒙特卡羅模擬方法、距離的衰減特性、適應(yīng)性選樣技術(shù)使得搜索的時(shí)間復(fù)雜度獨(dú)立于圖的規(guī)模，空間復(fù)雜度控制在可接受范圍。 根據(jù)實(shí)際需要，進(jìn)一步簡化算法為top-k相似性搜索，為實(shí)際運(yùn)用提供指導(dǎo)。 由于算法獨(dú)立于圖的規(guī)模的特性，方便進(jìn)行并行計(jì)算。使得計(jì)算超大規(guī)模的圖的SimRank值成為可能。首次擴(kuò)展到十億級別的超大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中來?？偨Y(jié)論文不足之處與其他可行工作 未能建立蒙特卡羅步數(shù)、衰減系數(shù)與精度的關(guān)系的數(shù)學(xué)分析模型 算法的預(yù)處理步驟是建立二分圖，能否找到空間復(fù)雜度更優(yōu)的替代數(shù)據(jù)結(jié)構(gòu)完成篩選點(diǎn)的步驟，這樣就可以擴(kuò)展到更大的圖 算法的核心是基于線性遞歸表達(dá)式的，而論文的實(shí)驗(yàn)數(shù)據(jù)都是大規(guī)模的稀疏圖，若是稠密圖，精度會有較大影響 節(jié)點(diǎn)間的相似度不僅與它們之間的鏈接有關(guān)還與其中的內(nèi)容有關(guān)，當(dāng)把節(jié)點(diǎn)間的內(nèi)容也放進(jìn)相似度評價(jià)后，如何把本文的線性遞歸表達(dá)式與內(nèi)容評價(jià)融合起來是一個(gè)值得研究的問題總結(jié)體會 SimR