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

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

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

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

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