圖像檢索系統(tǒng)中高維數(shù)據(jù)索引技術(shù)研究.pdf

1、隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展，圖像等多媒體信息的應(yīng)用越來(lái)越普遍，它們廣泛應(yīng)用于社會(huì)的各個(gè)領(lǐng)域，而且信息量也越來(lái)越大。如何對(duì)這些圖像信息進(jìn)行高效存儲(chǔ)和快速的基于內(nèi)容相似性檢索，越來(lái)越受到學(xué)術(shù)界人士的普遍關(guān)注。由于圖像信息的高維性，它需要不同于普通數(shù)據(jù)信息的處理技術(shù)，而高維索引技術(shù)正是加速圖像信息檢索的有效手段。因此，設(shè)計(jì)更加有效的高維索引結(jié)構(gòu)，以支持高效的基于內(nèi)容的相似性檢索成為迫切需要解決的關(guān)鍵問(wèn)題。在這種研究背景下，我們深入研究了與

2、高維信息相關(guān)的一些問(wèn)題，以及已經(jīng)存在的一些高維索引技術(shù)，提出了三種新的索引技術(shù)，并通過(guò)廣泛的實(shí)驗(yàn)，驗(yàn)證了我們提出的索引技術(shù)的高效性。下面對(duì)本文的主要工作和貢獻(xiàn)總結(jié)如下： (1)提出了關(guān)鍵維和孿生兄弟節(jié)點(diǎn)的概念，以及關(guān)鍵維轉(zhuǎn)移的思想，并在此基礎(chǔ)上提出了高維數(shù)據(jù)空間中基于距離和關(guān)鍵維的兩步分割策略和索引技術(shù)M+-tree。在索引結(jié)構(gòu)上，M+-tree的每個(gè)入口項(xiàng)包含兩個(gè)指針，分別指向一對(duì)孿生兄弟節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)。在查詢中，M+-

3、tree采用兩遍過(guò)濾方法，即普通兄弟節(jié)點(diǎn)間基于距離的過(guò)濾和孿生兄弟節(jié)點(diǎn)間基于關(guān)鍵維的過(guò)濾，其中基于關(guān)鍵維的過(guò)濾不需要高維距離計(jì)算，只需要進(jìn)行關(guān)鍵維的比較，代價(jià)非常低。孿生兄弟節(jié)點(diǎn)間的分割屬于無(wú)重疊分割，因此，在一定的查詢范圍內(nèi)，關(guān)鍵維的過(guò)濾能力非常強(qiáng)。針對(duì)M+-tree的近鄰查詢，M+-tree首次提出了基于度量的索引中優(yōu)先隊(duì)列訪問(wèn)對(duì)查詢性能的極大影響，并提出將孿生兄弟節(jié)點(diǎn)作為整體進(jìn)行隊(duì)列訪問(wèn)，極大地降低了對(duì)優(yōu)先隊(duì)列的訪問(wèn)。基于這些思想

4、，本文給出了M+-tree的構(gòu)建、分裂、范圍查詢以及近鄰查詢的算法。 (2)提出了兩種批量構(gòu)建M+-tree的方法：基于單步聚類(lèi)的批量構(gòu)建技術(shù)和基于多步聚類(lèi)的批量構(gòu)建技術(shù)。其中基于單步聚類(lèi)的批量構(gòu)建技術(shù)能夠?qū)崿F(xiàn)索引的快速構(gòu)建，而基于多步聚類(lèi)的批量構(gòu)建技術(shù)不僅考慮快速構(gòu)建索引結(jié)構(gòu)，而且把快速的相似性查詢作為其另一個(gè)重要目標(biāo)，在充分利用索引空間并快速構(gòu)建索引結(jié)構(gòu)的前提下，保證了索引空間良好的聚類(lèi)特性，以及索引相似性查詢的有效性。由于

5、我們的批量構(gòu)建技術(shù)是建立在靜態(tài)構(gòu)建索引結(jié)構(gòu)基礎(chǔ)上的，索引的空間利用率可以達(dá)100％。同普通的索引構(gòu)建方法相比，我們提出的批量構(gòu)建技術(shù)不僅極大地加快了索引的構(gòu)建速度，而且保證了索引的高效查詢性能。 (3)提出了高維數(shù)據(jù)空間中基于距離和可旋轉(zhuǎn)二元超平面的兩步分割策略和索引技術(shù)BM+-tree。BM+-tree是在M+-tree的基礎(chǔ)上提出的一種改進(jìn)索引技術(shù)。它的提出一方面改進(jìn)了孿生兄弟節(jié)點(diǎn)間的數(shù)據(jù)分布，使得孿生兄弟節(jié)點(diǎn)中包含的數(shù)據(jù)信

6、息具有更好的聚類(lèi)特性，另一方面，可旋轉(zhuǎn)的二元超平面使得我們的考察對(duì)象能夠保留更多的信息，因此，可旋轉(zhuǎn)的二元超平面比關(guān)鍵維具有更強(qiáng)的過(guò)濾能力，而且，在某種程度上，避免了關(guān)鍵維過(guò)濾中當(dāng)查詢半徑增大，過(guò)濾能力迅速下降的不足。從而達(dá)到進(jìn)一步提高高維數(shù)據(jù)查詢效率的目的。本文給出了可旋轉(zhuǎn)二元超平面的構(gòu)建算法以及BM+-tree的構(gòu)建和查詢算法。 (4)提出了假活動(dòng)子空間的概念，并分析了傳統(tǒng)索引技術(shù)在進(jìn)行相似性查詢時(shí)對(duì)假活動(dòng)子空間訪問(wèn)的極大代

7、價(jià)，以及在低維空間中精煉查詢空間的可行性。提出了通過(guò)空間投影，在低維空間中精煉過(guò)濾查詢空間的思想。提出了基于最大間隔的空間投影策略，該投影策略能夠保證精煉過(guò)程的高效性。最后，基于這種思想構(gòu)建了索引結(jié)構(gòu)MS-tree，以驗(yàn)證這種精煉過(guò)濾策略的高效性。我們通過(guò)對(duì)范圍查詢的實(shí)驗(yàn)，證明了這種精煉過(guò)濾策略的高效性。 (5)最后，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于內(nèi)容的圖像檢索系統(tǒng)IBASE。IBASE提供信息的特征提取、索引創(chuàng)建、數(shù)據(jù)存儲(chǔ)以及相似性