XSA-tree：圖象檢索系統(tǒng)中的一種高維索引結(jié)構(gòu).pdf

1、隨著計(jì)算機(jī)技術(shù)、數(shù)字圖像技術(shù)以及互聯(lián)網(wǎng)技術(shù)的發(fā)展，使人們?cè)絹?lái)越多的接觸到大量的圖像信息。傳統(tǒng)的圖像檢索技術(shù)面臨很大的挑戰(zhàn)。為了有效地發(fā)現(xiàn)、檢索和存取這些圖像信息，人們開(kāi)始提出基于內(nèi)容的圖像檢索系統(tǒng)。基于內(nèi)容的圖像檢索是利用圖像的視覺(jué)特征來(lái)表征圖像，檢索則根據(jù)這些特征的相似性來(lái)進(jìn)行。實(shí)現(xiàn)基于內(nèi)容的圖像檢索要對(duì)檢索的圖像進(jìn)行特征提取，得到的是維數(shù)很高的特征向量。我們對(duì)這些向量建立高維數(shù)據(jù)索引，通過(guò)這個(gè)索引以實(shí)現(xiàn)對(duì)圖像信息的相似性查詢(xún)。高維索

2、引技術(shù)是基于內(nèi)容的圖像檢索系統(tǒng)中用到的關(guān)鍵技術(shù)，它直接影響到系統(tǒng)的性能。 SA-tree是一種比較成功的高維數(shù)據(jù)空間索引結(jié)構(gòu)。它在查詢(xún)過(guò)程中是采用空間逼近方法，而不是傳統(tǒng)索引結(jié)構(gòu)分而治之的方法，當(dāng)查詢(xún)的選擇度比較低的情況下，這種索引結(jié)構(gòu)表現(xiàn)出非常好的性能。但SA-tree的根節(jié)點(diǎn)選取是隨機(jī)的，可能造成數(shù)據(jù)傾斜。另一方面SA-tree是一種空間逼近方法，每一次只能從當(dāng)前數(shù)據(jù)點(diǎn)移向它的近鄰數(shù)據(jù)點(diǎn)，而SA-tree中一個(gè)數(shù)據(jù)點(diǎn)到它近鄰

3、數(shù)據(jù)的距離比較小，逼近速度較慢，影響查詢(xún)性能。 我們?cè)O(shè)計(jì)了一種新的索引結(jié)構(gòu)——XSA-tree。索引樹(shù)XSA-tree擴(kuò)展了現(xiàn)有的索引結(jié)構(gòu)SA-tree，提出了衛(wèi)星數(shù)據(jù)域的思想，以改善相似性索引的性能。XSA-tree這種索引結(jié)構(gòu)在對(duì)根節(jié)點(diǎn)中代表數(shù)據(jù)點(diǎn)選取上進(jìn)行優(yōu)化，能夠得到相對(duì)平衡的索引樹(shù)，可以有效地避免數(shù)據(jù)傾斜現(xiàn)象。由于衛(wèi)星數(shù)據(jù)域的存在，當(dāng)前數(shù)據(jù)點(diǎn)到它近鄰數(shù)據(jù)點(diǎn)的距離變大，使得空間逼近的速度變快，索引的查詢(xún)性能也隨之提高。