基于圖的大規(guī)模特征庫(kù)高維索引技術(shù)研究.pdf

1、高維索引是基于內(nèi)容的多媒體檢索及地理、生物數(shù)據(jù)庫(kù)等需要運(yùn)用到高維數(shù)據(jù)庫(kù)的系統(tǒng)中一個(gè)至關(guān)重要的部分，其性能直接影響整個(gè)查詢系統(tǒng)的查詢速度和準(zhǔn)確率，但高維情況下的“維度災(zāi)難”問(wèn)題始終困擾著高維特征向量查詢的性能提升，使得高維索引常常成為相關(guān)系統(tǒng)的性能瓶頸之一。自上世紀(jì)六七十年代起，研究人員提出了許多種類的高維索引解決方案，但迄今仍然沒(méi)有出現(xiàn)一種各方面性能都能令人滿意的索引技術(shù)，使得當(dāng)前高維索引技術(shù)的發(fā)展仍然紛亂而迫切。
　　 本文參

2、考目前熱門(mén)的圖上的隨機(jī)游走算法，設(shè)計(jì)了一種融入了圖上游走思想的新型高維索引技術(shù)，稱為逼近索引，并給出了相應(yīng)的逼近游走相似性查詢算法。同時(shí)，通過(guò)分析逼近游走算法和一般高維索引算法的優(yōu)缺點(diǎn)，本文進(jìn)一步提出了一套基于逼近游走的分層組合索引思想，并按照此思想給出了一種新的相似逼近索引算法。具體而言，本文的詳細(xì)工作包括:
　　 第一，本文分析總結(jié)了向量空間和度量空間中的各種常見(jiàn)索引結(jié)構(gòu)的基本思想和優(yōu)缺點(diǎn)，闡述了高維索引算法的發(fā)展趨勢(shì)。然后

3、融合向量空間和度量空間索引特點(diǎn)，設(shè)計(jì)了一種不與特征向量維度直接相關(guān)，能有效減少高維向量查詢中對(duì)特征向量庫(kù)訪問(wèn)比例的逼近索引及相關(guān)相似性查詢算法。該索引將高維特征向量庫(kù)表示成圖的形式，引入逼近游走來(lái)進(jìn)行近似近鄰查詢和范圍查詢。
　　 第二，本文進(jìn)一步分析了目前逼近索引算法的優(yōu)點(diǎn)和不足之處，聯(lián)合多種現(xiàn)有的高維索引和逼近索引，提出了一種基于逼近索引的多層組合索引算法的思路。其中，完整地給出了近似逼近索引的生成維護(hù)及查詢算法，并對(duì)該索引

4、的綜合性能進(jìn)行了詳細(xì)的評(píng)測(cè)。此外，對(duì)于超高維數(shù)據(jù)，本文提出了包含向量降維和一維轉(zhuǎn)換算法的組合索引設(shè)想。
　　 第三，在向量降維部分，本文引入了近年來(lái)熱門(mén)的壓縮感知理論，設(shè)計(jì)了一種利用壓縮采樣的思想進(jìn)行高維向量降維的線性降維算法。該算法具有需要信息少，計(jì)算時(shí)間和空間復(fù)雜度低以及能處理特別高維度向量的特點(diǎn)。
　　 實(shí)驗(yàn)數(shù)據(jù)表明，本文算法適合應(yīng)用于大型特征庫(kù)的相似性查詢，具有訪問(wèn)特征庫(kù)中記錄條數(shù)少，查詢準(zhǔn)確性高的特點(diǎn)，綜合性能