基于小世界模型的高維向量查詢技術(shù)研究.pdf

1、高維索引作為模式識(shí)別、內(nèi)容檢索等領(lǐng)域的關(guān)鍵技術(shù)，其目的在于建立特征庫(kù)的索引結(jié)構(gòu)提高特征向量查詢效率，但其在高維情況下存在的“維度災(zāi)難”問(wèn)題一直困擾著高維特征向量查詢的性能提升。自上世紀(jì)六七十年代起，研究人員提出了許多種類的高維索引解決方案，但迄今仍然沒(méi)有出現(xiàn)一種在各方面性能都能令人滿意的索引技術(shù)，相關(guān)領(lǐng)域?qū)α己玫母呔S索引技術(shù)的需求仍然迫切。
　　本文受復(fù)雜網(wǎng)絡(luò)中“六度分隔”現(xiàn)象的啟發(fā)，設(shè)計(jì)了一種基于小世界模型的新型高維索引技術(shù)，并

2、給出了相應(yīng)的范圍查詢，近似k近鄰查詢和索引維護(hù)算法。該索引維護(hù)一定的鄰居節(jié)點(diǎn)分布，包括近鄰連接和遠(yuǎn)程連接，并將高維索引中向量查詢的過(guò)程類比于圖上鄰居節(jié)點(diǎn)間的跳躍，通過(guò)逐跳地往目標(biāo)方向逼近最終找到目標(biāo)節(jié)點(diǎn)，因此該索引被命名為逐跳逼近索引。同時(shí)，通過(guò)對(duì)相關(guān)理論研究證明的總結(jié)，本文對(duì)該索引模型作了展開(kāi)分析，說(shuō)明了在簡(jiǎn)化模型上其查詢平均路徑長(zhǎng)度的理論上界。最后，本文進(jìn)一步提出了若干基于小世界模型的組合索引方案，并結(jié)合數(shù)據(jù)庫(kù)系統(tǒng)將上述高維索引推向

3、實(shí)際應(yīng)用。具體而言，本文的詳細(xì)工作包括:
　　第一，本文參照小世界網(wǎng)絡(luò)的理論研究成果，對(duì)項(xiàng)目組的逼近索引結(jié)構(gòu)進(jìn)行了多項(xiàng)改進(jìn):額外添加了一定比例的隨機(jī)遠(yuǎn)程連接，以提供遠(yuǎn)程跳躍的捷徑，進(jìn)一步提高了索引查詢性能;取消范圍限制穩(wěn)定各節(jié)點(diǎn)的度，以保證圖在各種實(shí)際情況中的連通性，從而使得索引能夠較好地處理數(shù)據(jù)分布不均和小庫(kù)容量等實(shí)際應(yīng)用中常見(jiàn)的查詢場(chǎng)景。
　　第二，本文進(jìn)一步完善了逐跳逼近索引的范圍查詢和近似kNN查詢算法以及索引維護(hù)算

4、法，并將該索引應(yīng)用于隨機(jī)生成庫(kù)及實(shí)際圖像特征庫(kù)。結(jié)合理論分析和實(shí)驗(yàn)數(shù)據(jù)，探討了逐跳逼近索引的關(guān)鍵參數(shù)性質(zhì)特點(diǎn)，以及應(yīng)用到不同場(chǎng)景時(shí)的預(yù)期效果和注意事項(xiàng)。
　　第三，最后，本文分析了逐跳逼近索引的優(yōu)點(diǎn)和不足，結(jié)合目前已有的高維索引技術(shù)，給出了若干分層組合索引的算法。此外，為推動(dòng)該索引更快的應(yīng)用于實(shí)際系統(tǒng)，提出了結(jié)合數(shù)據(jù)庫(kù)系統(tǒng)的逐跳逼近索引應(yīng)用，借助成熟的數(shù)據(jù)庫(kù)系統(tǒng)解決了算法分布式拓展和內(nèi)存緩存管理等多個(gè)實(shí)際運(yùn)用問(wèn)題。
　　相關(guān)