高維多媒體數(shù)據(jù)索引算法研究.pdf

1、隨著數(shù)據(jù)采集制作設(shè)備的日益普及，人們越來越方便地生產(chǎn)圖像、圖形、音頻、視頻、動畫和三維模型等多媒體數(shù)據(jù)，這些多媒體數(shù)據(jù)具有異構(gòu)、非結(jié)構(gòu)化、高維和動態(tài)變化等特征，給后續(xù)處理例如分類、聚類、挖掘、理解和查詢檢索帶來巨大困難。基于內(nèi)容檢索方法的出現(xiàn)為多媒體數(shù)據(jù)查找開辟了一條新的途徑，而高維數(shù)據(jù)索引是加速相似性檢索的關(guān)鍵技術(shù)之一，也是多媒體和數(shù)據(jù)庫領(lǐng)域的研究熱點和難點。本文就是對高維索引進(jìn)行深入研究，并取得了一定成果。主要包括以下兩個方面：

2、r>　　 1.對基于高維索引結(jié)構(gòu)M-tree的KNN查詢算法和范圍查詢算法的近似化，分別提出基于M-tree結(jié)構(gòu)的AKNNQ算法和ARQ算法。M-tree結(jié)構(gòu)雖然使用過濾機(jī)制過濾不必要的分支，大大減少了計算量，但當(dāng)維數(shù)較高時，性能還是急速下降。而近似檢索則被認(rèn)為是適合高維的算法，所以對基于M-tree的查詢算法的近似化能更好的適用高維數(shù)據(jù)，以精度換取效率。ARQ算法擴(kuò)展了查詢的過濾的條件，更大程度上的過濾分支，減少不必要的計算。AKN

3、NQ算法也改進(jìn)的過濾條件，還對最小優(yōu)先子樹按某種規(guī)則排序，更快的收斂動態(tài)的查詢半徑，最后通過分析實驗數(shù)據(jù)，證明了近似檢索算法的有效性。
　　 2.對PI近似高維結(jié)構(gòu)中心點選取方法的優(yōu)化和選取數(shù)量的確定，提出維數(shù)區(qū)分方法以高效的查詢。PI高維索引結(jié)構(gòu)預(yù)計算數(shù)據(jù)集對于錨對象(permutant)集距離順序，對數(shù)據(jù)庫進(jìn)行預(yù)測規(guī)整，只需精確計算少量數(shù)據(jù)就到得到大部分的正確結(jié)果。其中permutant的選取很大程度上影響了索引結(jié)構(gòu)的性能，

4、而PI結(jié)構(gòu)中的隨機(jī)選取方法并不能保證效率的可靠性，而permutant選取的數(shù)量也是影響效率和準(zhǔn)確率的一個很大因素，permutant選取越多準(zhǔn)確率越高，但同時其效率大大下降，而選取的越少效率提高了，但其準(zhǔn)確率又得不到保證。本文就針對這兩個問題作了研究，基于最佳的permutant兩兩之間的距離盡可能遠(yuǎn)的假設(shè)提出了permutant的幾種選取方法，并在實驗中驗證了不同選取方法的可行性和有效性。最后提出了維數(shù)區(qū)分方法，得到最優(yōu)的permu