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

【文章來(lái)源】：中山大學(xué)廣東省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級(jí)別】：碩士

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



本文編號(hào)：3422751