近似最近鄰搜索問題是數(shù)據(jù)庫、數(shù)據(jù)挖掘、人工智能等領(lǐng)域中的一個基本問題。一個具有實(shí)際應(yīng)用價(jià)值的近似最近鄰搜索算法必須同時(shí)具有極高的搜索速度以及合理的內(nèi)存用量。相比于傳統(tǒng)的基于樹結(jié)構(gòu)、基于哈希和基于量化的搜索算法,基于圖索引的近似最近鄰搜索算法因其搜索高且速度快的特點(diǎn),吸引了來自學(xué)術(shù)界和工業(yè)界的大量關(guān)注。雖然許多早期的基于圖結(jié)構(gòu)的近似最近鄰搜索算法算法在理論上具有十分低的搜索時(shí)間復(fù)雜度,但這些圖結(jié)構(gòu)索引的索引構(gòu)建算法往往具有極高的時(shí)間復(fù)雜度,從而使其在目前的大數(shù)據(jù)時(shí)代場景中無法有效應(yīng)用。因此近年來學(xué)界提出了諸多新的圖結(jié)構(gòu)索引,以期能夠降低索引構(gòu)建的時(shí)間復(fù)雜度。雖然這些方法取得了許多革命性的進(jìn)步,但其仍舊不夠高效從而限制了其在更大規(guī)模數(shù)據(jù)集上的應(yīng)用。本文結(jié)合近年來的最新研究成果,對圖結(jié)構(gòu)索引進(jìn)行了更深入的探究,以希望能夠更有效地解決上述困難。具體來講,本文從以下四個方面出發(fā)對用于近似最近鄰搜索的圖結(jié)構(gòu)進(jìn)行了探究:（1）保證圖的連通性;（2）降低圖中節(jié)點(diǎn)的平均出度已獲得更快的遍歷速度;（3）降低查詢在圖上的搜索路徑長度;（4）減小基于圖結(jié)構(gòu)的索引的大小�；谝陨纤狞c(diǎn),本文在理論上提出了一種全新... 

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 本文研究內(nèi)容與貢獻(xiàn)
    1.4 本文章節(jié)安排
第2章 相關(guān)工作概述
    2.1 問題定義
    2.2 研究前提
    2.3 基于非圖結(jié)構(gòu)的近似最近鄰搜索算法
        2.3.1 基于樹結(jié)構(gòu)的算法
        2.3.2 基于哈希的算法
        2.3.3 基于空間量化的算法
        2.3.4 總結(jié)與討論
    2.4 基于圖結(jié)構(gòu)的近似最近鄰搜索算法
        2.4.1 德勞內(nèi)圖
        2.4.2 相對近鄰圖RNG
        2.4.3 可通航小世界網(wǎng)絡(luò)NSWN
        2.4.4 隨機(jī)化近鄰圖RANG
        2.4.5 單調(diào)搜索網(wǎng)絡(luò)MSNET
    2.5 本章小結(jié)
第3章 MRNG算法介紹與分析
    3.1 引言
    3.2 單調(diào)路徑與單調(diào)搜索網(wǎng)絡(luò)MSNET
    3.3 單調(diào)相對近鄰圖MRNG
    3.4 MRNG的構(gòu)建算法
    3.5 本章小結(jié)
第4章 NSG算法介紹與分析
    4.1 設(shè)計(jì)思想與構(gòu)建算法
        4.1.1 設(shè)計(jì)思想
        4.1.2 算法實(shí)現(xiàn)
    4.2 時(shí)間復(fù)雜度分析
        4.2.1 構(gòu)建時(shí)間復(fù)雜度
        4.2.2 搜索時(shí)間復(fù)雜度
    4.3 分布式搜索系統(tǒng)設(shè)計(jì)方案
    4.4 本章小結(jié)
第5章 實(shí)驗(yàn)與分析
    5.1 數(shù)據(jù)集
    5.2 對比算法
    5.3 實(shí)驗(yàn)環(huán)境
    5.4 百萬級數(shù)據(jù)實(shí)驗(yàn)結(jié)果與分析
        5.4.1 圖結(jié)構(gòu)算法優(yōu)勢分析
        5.4.2 NSG算法對比驗(yàn)證與分析
        5.4.3 其他結(jié)論與分析
    5.5 NSG算法時(shí)間復(fù)雜度驗(yàn)證
        5.5.1 索引構(gòu)建時(shí)間復(fù)雜度
        5.5.2 搜索時(shí)間復(fù)雜度
    5.6 億級數(shù)據(jù)實(shí)驗(yàn)結(jié)果與分析
        5.6.1 NSG性能對比測試
        5.6.2 分布式搜索系統(tǒng)可行性驗(yàn)證
        5.6.3 分析與結(jié)論
    5.7 本章小結(jié)
第6章 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
參考文獻(xiàn)
攻讀碩士學(xué)位期間的主要研究成果
致謝



本文編號：3702419