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

1、高維索引作為模式識別、內容檢索等領域的關鍵技術，其目的在于建立特征庫的索引結構提高特征向量查詢效率，但其在高維情況下存在的“維度災難”問題一直困擾著高維特征向量查詢的性能提升。自上世紀六七十年代起，研究人員提出了許多種類的高維索引解決方案，但迄今仍然沒有出現(xiàn)一種在各方面性能都能令人滿意的索引技術，相關領域對良好的高維索引技術的需求仍然迫切。
　　本文受復雜網絡中“六度分隔”現(xiàn)象的啟發(fā)，設計了一種基于小世界模型的新型高維索引技術，并

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

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

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