最大內積檢索是一個相對比較新的問題,但在許多應用中都發(fā)揮著重要作用,如基于矩陣分解的協(xié)同過濾、文檔檢索、最大核搜索等。其正式的定義如下：給定一個有n個數(shù)據(jù)點的集合D（?）sRd,一個查詢q∈sRd,最大內積檢索問題要求我們快速地找到一個向量v*∈D,使得,其中<*,*)表示兩個向量間的內積。由于問題的重要性,目前已經(jīng)有很多文獻針對最大內積檢索提出（精確或近似的）解決方案。ball-樹是目前最大內積檢索中常用的數(shù)據(jù)結構。其具有高效、簡單以及易于實現(xiàn)等優(yōu)點。我們對ball-樹的性能分析結果指出,ball-樹在搜索的過程中超過90%的時間都是花費在內積計算上。因此,內積計算是提升算法性能的一個瓶頸。搜索過程中有兩個地方需要進行內積計算：（1）每次上界計算都需要一次內積計算。我們用瓜表示搜索過程中上界計算的次數(shù)；（2）搜索訪問到的葉子中的每個數(shù)據(jù)點都需要與查詢計算一遍內積。我們用Xv表示需要與查詢計算內積的數(shù)據(jù)點的個數(shù)。很明顯,如果我們能將XN和Xv降下來,我們將能夠更快地進行最大內積檢索。本文通過挖掘內積計算的性質,提出了兩個簡單且高效的優(yōu)化,分別降低了XN和Xv,從而提高了ball-... 

【文章來源】：中山大學廣東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：65 頁

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 引言
    1.1 最大內積檢索問題
    1.2 最大內積檢索問題的應用
    1.3 最大內積檢索的難點
    1.4 論文的貢獻
    1.5 論文的安排
第二章 相關工作
    2.1 精確算法
    2.2 近似算法
第三章 我們的優(yōu)化
    3.1 ball-樹的代價模型
    3.2 點級別的剪枝
    3.3 協(xié)同上界計算
    3.4 算法
第四章 實驗與分析
    4.1 實驗介紹
    4.2 實驗結果
第五章 總結與展望
    5.1 研究總結
    5.2 未來工作
參考文獻
致謝



本文編號：3422751