高維索引技術(shù)中向量近似方法研究.pdf

1、基于內(nèi)容的圖像檢索已經(jīng)成為圖像數(shù)據(jù)庫的一項(xiàng)重要應(yīng)用。高維數(shù)據(jù)索引是加速圖像相似性檢索的關(guān)鍵技術(shù)之一，也是多媒體和數(shù)據(jù)庫領(lǐng)域的研究熱點(diǎn)和難點(diǎn)。傳統(tǒng)的多維索引技術(shù)在高維情況下會(huì)受到“維數(shù)災(zāi)難”現(xiàn)象的影響，在維數(shù)足夠高的情況下(超過幾十維)，其檢索性能會(huì)退化到最原始的順序查找方法，研究有效的高維索引機(jī)制是使面向大規(guī)模數(shù)據(jù)庫的檢索達(dá)到實(shí)時(shí)性要求的關(guān)鍵。除了多媒體對象的相似性檢索外，高維索引技術(shù)也可應(yīng)用于其他相關(guān)領(lǐng)域，如數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)

2、習(xí)、數(shù)據(jù)統(tǒng)計(jì)和分析等。 本文在介紹維數(shù)災(zāi)難現(xiàn)象的基礎(chǔ)上，系統(tǒng)地綜述了高維索引技術(shù)的研究現(xiàn)狀和發(fā)展趨勢。向量近似方法是一種有效的高維索引技術(shù)，在高維情況下，其檢索性能仍優(yōu)于順序查找方法，目前對高維索引技術(shù)的研究大部分都是在該方法的基礎(chǔ)上進(jìn)行。本文主要面向大規(guī)模圖像數(shù)據(jù)庫上k近鄰搜索應(yīng)用，在向量近似方法的基礎(chǔ)上，開展對高維索引技術(shù)的研究。本論文的主要?jiǎng)?chuàng)新性成果如下所述： 1.向量近似方法是一種基于壓縮技術(shù)的索引方法，該方法需

3、要順序訪問所有的近似向量才能完成搜索過程。提出了一種基于主分量排序的新型索引方法，只要順序訪問部分近似向量即可完成搜索過程。首先在正交變換域上建立近似向量，選擇變換域能量最大的分量作為主分量，根據(jù)主分量值對近似向量進(jìn)行順序排列，并且用B+樹存儲(chǔ)每個(gè)數(shù)據(jù)頁面中的主分量值的范圍。在k近鄰搜索過程中，采用變換域部分失真搜索算法，從初始訪問數(shù)據(jù)頁面開始在升序和降序兩個(gè)方向上順序訪問近似向量。除了歐氏距離外，本文還將新的索引方法擴(kuò)展到了二次式距離

4、和絕對值距離。對于二次式距離，使用奇異值分解技術(shù)對向量進(jìn)行變換。對于絕對值距離，提出了一種相鄰元素相加的多分辨率數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，該索引方法能夠在保持順序訪問方式的基礎(chǔ)上，減少近似向量訪問數(shù)量，提高檢索性能。 2.提出了一種用R樹組織近似向量的新型索引結(jié)構(gòu)—PCR樹。在正交變換域上建立近似向量，選擇變換域能量最大的多維分量作為主分量，采用R樹來組織主分量上的近似向量。在k近鄰搜索過程中，采用了新的低維過濾算法來剪枝PCR樹

5、中的目錄節(jié)點(diǎn)。主分量維數(shù)的選取對PCR樹的索引能力影響很大，選取的主分量維數(shù)越少，能量損失越大，過濾效率越低，I/O開銷會(huì)增大；選取的主分量維數(shù)越多，過濾效率越高，但是索引結(jié)構(gòu)又會(huì)受到維數(shù)災(zāi)難現(xiàn)象的影響。實(shí)驗(yàn)結(jié)果表明，在PCR樹中，訪問很少的近似向量即可完成搜索過程，從而大幅度降低了搜索過程中的CPU運(yùn)算開銷。 3.提出一種基于矢量量化技術(shù)的索引方法。從量化技術(shù)角度來看，近似向量的生成實(shí)際上采用了標(biāo)量量化方法，與標(biāo)量量化相比，矢

6、量量化能夠提供更高的壓縮率，采用矢量量化技術(shù)生成近似向量，可以進(jìn)一步降低近似向量的長度，從而降低近似文件的存儲(chǔ)容量。對特征向量進(jìn)行矢量量化后，量化碼字就是其近似向量。采用超球來組織矢量量化后胞腔中的數(shù)據(jù)，根據(jù)近似向量可以計(jì)算特征向量與查詢向量之間的距離上、下界。為解決矢量量化過程中碼字?jǐn)?shù)目過大以及復(fù)雜度過高的問題，采用乘積矢量量化器來生成碼書。實(shí)驗(yàn)結(jié)果表明，該方法能夠在保證過濾效率的基礎(chǔ)上，降低近似向量文件的長度，降低搜索過程中的I/O

7、代價(jià)，從而提高搜索性能。 4.探討了向量近似方法在相關(guān)反饋技術(shù)中的應(yīng)用，相關(guān)反饋技術(shù)中一個(gè)很重要的特性就是在反饋過程中特征向量的表示和相似性度量方式都會(huì)發(fā)生變化。介紹了二次式距離和核函數(shù)距離上的向量近似方法，并且提出了改進(jìn)的近鄰搜索算法。反饋過程中相鄰兩次查詢結(jié)果具有一定的相關(guān)性，改進(jìn)算法在查詢過程中利用了反饋信息和上輪次的查詢結(jié)果，可以提高向量近似方法的過濾性能，從而提高搜索速度。 5.在基于低層特征的圖像檢索應(yīng)用中，

8、精確檢索得到的結(jié)果并不具有精確含義，最近幾年人們提出了近似檢索的概念。從索引技術(shù)角度來看，近似檢索技術(shù)是克服維數(shù)災(zāi)難現(xiàn)象的一種有效手段。針對本文提出的多種精確索引結(jié)構(gòu)，分別提出相應(yīng)的近似近鄰搜索算法。(1)對于順序訪問方式的向量近似方法，采用訪問部分?jǐn)?shù)據(jù)集的近似查詢方法。(2)對于基于矢量量化的近似索引方法，提出了用倒排文件組織近似向量的索引結(jié)構(gòu)和搜索算法，新算法能夠大幅度降低CPU運(yùn)算開銷，并且只用一次I/O即可完成最近鄰查詢過程，但