多媒體數(shù)據(jù)庫(kù)高維數(shù)據(jù)索引研究及應(yīng)用.pdf

1、隨著互聯(lián)網(wǎng)和多媒體技術(shù)的迅速發(fā)展，人們可以訪(fǎng)問(wèn)到的視頻數(shù)據(jù)急劇增長(zhǎng)，如何從這些海量的數(shù)據(jù)中尋找感興趣的內(nèi)容成為一個(gè)非常重要的研究課題。通常，人們利用特征提取算法從多媒體數(shù)據(jù)對(duì)象中提取出特征矢量，然后利用特征矢量之間的距離表示多媒體對(duì)象之間相似度，從而利用相似性檢索，通過(guò)計(jì)算查詢(xún)矢量與數(shù)據(jù)庫(kù)中矢量之間的距離找出滿(mǎn)足條件的對(duì)象。由于這些特征矢量通常維數(shù)較高，且當(dāng)數(shù)據(jù)庫(kù)中矢量很多時(shí)，簡(jiǎn)單的順序掃描搜索將導(dǎo)致極大的查詢(xún)代價(jià)，無(wú)法滿(mǎn)足用戶(hù)需求。為

2、了提高查詢(xún)效率，就必須借助于高效的、適合高維數(shù)據(jù)的索引結(jié)構(gòu)。
　　 近幾十年中，人們提出了很多高維數(shù)據(jù)索引結(jié)構(gòu)，如R-Tree、M-Tree及其變種等。這些索引結(jié)構(gòu)在維數(shù)升高時(shí)性能會(huì)急劇下降，即產(chǎn)生所謂的“維災(zāi)”。另外，目前的很多索引結(jié)構(gòu)都是適用于維數(shù)一定的數(shù)據(jù)，當(dāng)多媒體系統(tǒng)中同時(shí)存在不同維度的特征矢量時(shí)，其查詢(xún)性能也受到影響。
　　 本文對(duì)現(xiàn)有的索引結(jié)構(gòu)進(jìn)行了研究。已有的NB-Tree(Norm B+-Tree)方法通

3、過(guò)計(jì)算特征矢量與參考點(diǎn)的距離將高維特征矢量映射到一維距離空間，采用大型數(shù)據(jù)庫(kù)系統(tǒng)所支持的B+-tree進(jìn)行索引，通用性強(qiáng)且易于維護(hù)。但NB-Tree未考慮數(shù)據(jù)分布情況，使得相似查詢(xún)的候選結(jié)果集中存在很多臟數(shù)據(jù)，增加了不必要的距離計(jì)算次數(shù)。結(jié)合已有的NB-Tree改進(jìn)方法，本文從數(shù)據(jù)分布的角度出發(fā)，改進(jìn)出INNB-Tree(Improved New NB-tree)。INNB-Tree采用主成分析原理選擇landmark點(diǎn)的方法來(lái)選擇參考