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

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

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

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

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