APMI：一種同時(shí)優(yōu)化I/O與計(jì)算開(kāi)銷的高維索引技術(shù)

李煥軍

摘 要 本文提出了一種新的同時(shí)優(yōu)化I/O與計(jì)算的高維索引技術(shù)APMI。該索引技術(shù)在判斷是否遍歷當(dāng)前區(qū)域之前，先判斷該查詢范圍所擴(kuò)展而成的超立方體是否與當(dāng)前區(qū)域相交，以便減少無(wú)效的I/O開(kāi)銷；此外，在遍歷每個(gè)索引節(jié)點(diǎn)數(shù)據(jù)點(diǎn)之前，通過(guò)三角剪枝方法篩除一部分?jǐn)?shù)據(jù)點(diǎn)，以很小的計(jì)算開(kāi)銷進(jìn)一步減少了數(shù)據(jù)訪問(wèn)量，進(jìn)一步提升了總體效率。在大規(guī)模的真實(shí)數(shù)據(jù)集上的性能試驗(yàn)表明，APMI較現(xiàn)有代表性技術(shù)有較大性能提升。

【關(guān)鍵詞】高維索引 性能優(yōu)化 kNN檢索

1 引言

隨著多媒體數(shù)字娛樂(lè)設(shè)備和多媒體傳感器設(shè)備的普及，圖像、音頻、視頻等多媒體數(shù)據(jù)己成為人們?nèi)粘Ｉ钪行畔⒌闹匾獊?lái)源，著名的IT咨詢公司IDG的研究報(bào)告表明，視頻，音頻，圖像等多媒體數(shù)據(jù)已經(jīng)占到了當(dāng)前信息數(shù)據(jù)總量的70%以上。如何對(duì)大規(guī)模多媒體數(shù)據(jù)進(jìn)行有效的組織、分類和檢索，從而幫助人們快速的查找到自己感興趣的信息，已成為研究者們亟需解決的關(guān)鍵問(wèn)題。其中，高維索引技術(shù)作為對(duì)大規(guī)模多媒體數(shù)據(jù)的內(nèi)容進(jìn)行檢索的關(guān)鍵技術(shù)和重要手段，其重要性也變得越來(lái)越突出，其廣闊的應(yīng)用前景已為人們所公認(rèn)，因而也成為學(xué)術(shù)界和產(chǎn)業(yè)界的研究熱點(diǎn)。

根據(jù)索引結(jié)構(gòu)，高維索引技術(shù)通?？梢詣澐譃槿箢悾夯趧澐值母呔S索引，基于度量（metric）的高維索引和基于近似方法的高維索引。其中，基于劃分的高維索引技術(shù)可以進(jìn)一步細(xì)分為基于數(shù)據(jù)劃分和基于空間劃分的高維索引技術(shù)。

在某些情況下，可能不能直接獲取多媒體數(shù)據(jù)對(duì)象的特征向量，但是多媒體對(duì)象之間的距離關(guān)系仍然可以被獲取到?；诰嚯x度量（metric）的索引技術(shù)就是針對(duì)這種情況而提出的一類高維索引技術(shù)。其基本原理是：基于某些選擇出來(lái)的參考點(diǎn)，根據(jù)數(shù)據(jù)對(duì)象到參考點(diǎn)之間的距離，將數(shù)據(jù)區(qū)域劃分為若干個(gè)區(qū)域。然后，kNN檢索的結(jié)果就可以根據(jù)給定的查詢對(duì)象到數(shù)據(jù)對(duì)象以及參考點(diǎn)之間的距離來(lái)獲得。代表性的索引技術(shù)包括M-Tree，MVP-Tree，iDistance等。

第三類常見(jiàn)的高維索引技術(shù)就是基于近似技術(shù)的索引方法。具體可以分為3類，包括：

（1）基于近似表示的特征向量的高維索引技術(shù)，如A-Tree技術(shù)；

（2）基于降維和維度轉(zhuǎn)換方法的高維索引技術(shù)，如MMDR和DCR等。其中，后三者都是在進(jìn)行維度轉(zhuǎn)換后將新得到的維度用B+-Tree進(jìn)行索引，然后在此基礎(chǔ)上進(jìn)行各種檢索；

（3）基于Hash的方法，如TreeHB等。

傳統(tǒng)的高維索引研究認(rèn)為，當(dāng)數(shù)據(jù)規(guī)模較大且維度較高時(shí)，I/O開(kāi)銷是最主要的性能瓶頸，因此，高維索引技術(shù)的研究者們都著重研發(fā)各種減少I(mǎi)/O開(kāi)銷的索引技術(shù)和檢索方法。然而，已有工作證明[Hike]，對(duì)于海量多媒體數(shù)據(jù)，當(dāng)多媒體特征向量的維度較高時(shí)，計(jì)算開(kāi)銷，尤其是各種距離計(jì)算開(kāi)銷也是不能忽略的，這些計(jì)算開(kāi)銷甚至可能成為高維數(shù)據(jù)查詢處理過(guò)程中的重要瓶頸。

針對(duì)上述問(wèn)題，本文提出了一種新的同時(shí)優(yōu)化I/O與計(jì)算的高維索引技術(shù)APMI，以便提升高維數(shù)據(jù)檢索效率。本文的主要技術(shù)工作如下：

（1）優(yōu)化度量空間的索引結(jié)構(gòu)，為每個(gè)葉子結(jié)點(diǎn)增加了一個(gè)屬性，該屬性記錄該點(diǎn)到數(shù)據(jù)空間中心的距離；

（2）優(yōu)化I/O開(kāi)銷：在判斷是否遍歷當(dāng)前區(qū)域之前，先判斷該查詢范圍所擴(kuò)展而成的超立方體是否與當(dāng)前區(qū)域相交，以便減少無(wú)效的I/O開(kāi)銷；

（3）優(yōu)化計(jì)算開(kāi)銷：在遍歷每個(gè)索引節(jié)點(diǎn)數(shù)據(jù)點(diǎn)之前，通過(guò)三角剪枝方法篩除一部分?jǐn)?shù)據(jù)點(diǎn)，以很小的計(jì)算開(kāi)銷進(jìn)一步減少了數(shù)據(jù)訪問(wèn)量，進(jìn)一步提升了總體效率。

2 APMI索引的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

APMI索引是一種基于度量，同時(shí)結(jié)合降維技術(shù)與聚類技術(shù)的高維索引技術(shù)，其在數(shù)據(jù)存儲(chǔ)的組織結(jié)構(gòu)上與iDistance等度量空間索引比較相似，在此不再贅述。其核心思想包括三點(diǎn)：

（1）數(shù)據(jù)空間內(nèi)每個(gè)點(diǎn)的表征可以通過(guò)參考點(diǎn)來(lái)表示；

（2）根據(jù)數(shù)據(jù)空間內(nèi)點(diǎn)離參考點(diǎn)的距離組織索引；

（3）索引基于B+-Tree，鍵值是與空間距離有關(guān)的一維數(shù)據(jù)?；谝陨纤枷耄撍饕梢酝ㄟ^(guò)距離間的度量進(jìn)行剪枝。

APMI索引在存儲(chǔ)結(jié)構(gòu)上相對(duì)于傳統(tǒng)的度量空間索引技術(shù)的優(yōu)化之處在于：為索引的每個(gè)葉子結(jié)點(diǎn)增加了一個(gè)屬性，該屬性記錄該點(diǎn)到數(shù)據(jù)空間中心的距離。在進(jìn)行數(shù)據(jù)檢索時(shí)，剪枝算法通過(guò)該點(diǎn)到與中心點(diǎn)的距離、該點(diǎn)到參考點(diǎn)的距離、查詢半徑作為參數(shù)，以三角剪枝的達(dá)到降低計(jì)算開(kāi)銷的目的，進(jìn)而提高查詢效率。

APMI索引結(jié)構(gòu)的一個(gè)簡(jiǎn)單的例子如圖1所示。給定三個(gè)基于聚類的劃分P1、P2、P3，其中心分別為O1、O2和O3，對(duì)于查詢點(diǎn)q，P1、P2需要遍歷，P3不需要。高維查詢空間，通過(guò)APMI索引轉(zhuǎn)換為一維鍵值的查詢，其陰影部分即為查詢空間。

3 基于空間劃分策略的I/O開(kāi)銷優(yōu)化

APMI索引的基于空間劃分策略的I/O優(yōu)化方案的主要技術(shù)特性是：在判斷是否遍歷當(dāng)前區(qū)域之前，先判斷該查詢范圍所擴(kuò)展而成的超立方體是否與當(dāng)前區(qū)域相交。具體的，在判斷查詢q與當(dāng)前分區(qū)滿足哪類候選剪枝情形之前，先判斷q與查詢半徑r所形成的查詢區(qū)域與分區(qū)是否存在無(wú)效I/O開(kāi)銷的可能。其剪枝算法如下：

圖2是一個(gè)采用I/O優(yōu)化的剪枝策略的實(shí)例。其中左圖中給定了查詢點(diǎn)q，查詢半徑r，且q包含于P3。同時(shí)，q與P2滿足條件dist（O2，q）-r ≤ dist_max2。其中不過(guò)，q與r所形成的超球，與P2中O2所形成的超半球，其相交的這個(gè)分區(qū)頁(yè)，只包含O2所在金字塔頂端的幾個(gè)數(shù)據(jù)點(diǎn)。超過(guò)金字塔范圍所形成的超半球，即使與q的查詢范圍相交，但由于這個(gè)區(qū)域本身不存在屬于P2的任何數(shù)據(jù)點(diǎn)，所以查詢相交的這個(gè)頁(yè)面，對(duì)于整個(gè)查詢過(guò)程來(lái)說(shuō)，是無(wú)效的I/O開(kāi)銷。

圖2的右圖是采用了本文提出的面向I/O優(yōu)化的剪枝策略的檢索實(shí)例。其將圖2左圖中q與r所形成的圓擴(kuò)展成正方形。不難看出正方形與P2不存在交叉，即滿足PP算法中的剪枝情況，不必對(duì)原本需要查詢的page進(jìn)行查詢，減少了一部分I/O的開(kāi)銷。

4 計(jì)算開(kāi)銷優(yōu)化策略

對(duì)于基于度量空間的高維索引，存在一個(gè)普遍的問(wèn)題，即所形成的超球體積會(huì)很大。如圖3的左圖所示：對(duì)于當(dāng)前查詢q與查詢半徑r所形成的查詢區(qū)域，對(duì)于P2而言，可雙向遍歷到達(dá)；對(duì)于與P3而言，可向內(nèi)遍歷到達(dá)。不難發(fā)現(xiàn)，因超球的體積很大，其包含的數(shù)據(jù)點(diǎn)分布也非常散亂。其需要遍歷的三個(gè)頁(yè)面中的很多數(shù)據(jù)點(diǎn)，浪費(fèi)了大部分的計(jì)算開(kāi)銷。

為解決此問(wèn)題，本文提出一種基于三角不等式剪枝的算法：在遍歷每個(gè)page中數(shù)據(jù)點(diǎn)之前，通過(guò)三角剪枝的方法篩除一部分?jǐn)?shù)據(jù)點(diǎn)。該方案為每個(gè)葉子結(jié)點(diǎn)增加了一個(gè)屬性，該屬性記錄該點(diǎn)到數(shù)據(jù)空間中心的距離。剪枝算法通過(guò)該點(diǎn)到與中心點(diǎn)的距離、該點(diǎn)到參考點(diǎn)的距離、查詢半徑作為參數(shù)，以三角剪枝的達(dá)到降低計(jì)算開(kāi)銷的目的，進(jìn)而提高查詢效率（如圖2的右圖所示）。

具體的，將為全部數(shù)據(jù)點(diǎn)增加一個(gè)屬性字段（包括查詢點(diǎn)q），記錄該點(diǎn)到數(shù)據(jù)空間中心center的距離。假定采用歐氏距離作為度量標(biāo)準(zhǔn)，p為數(shù)據(jù)空間內(nèi)某個(gè)與查詢區(qū)域相交的索引節(jié)點(diǎn)頁(yè)面中的數(shù)據(jù)點(diǎn)，則存在以下三角不等式規(guī)則，可作為剪枝依據(jù)：

dist（p，q）-dist（q，center） ≤ dist（p，center） ≤ dist（q，center） + dist（q，center）

當(dāng)規(guī)定查詢點(diǎn)q的查詢半徑r時(shí)，對(duì)于q查詢半徑內(nèi)的所有候選點(diǎn)p，必須滿足：

dist（p，center） ≤ r + dist（q，center）

否則，page內(nèi)的點(diǎn)將被篩除，從而在僅進(jìn)行三角剪枝這一計(jì)算開(kāi)銷極小的處理的前提下，進(jìn)一步減少了數(shù)據(jù)訪問(wèn)量，提升了總體效率。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境和設(shè)置

在本文的實(shí)驗(yàn)中，采用64位操作系統(tǒng)CentOS-6.4，內(nèi)核版本為3.10.0。內(nèi)存為16 Gb，處理器為2.4GHz的Intel Xeon E5645，磁盤(pán)為300Gb。實(shí)驗(yàn)中，將基于MSRA-MM 2.0數(shù)據(jù)集，將APMI與iDistance這種代表性的高維索引技術(shù)進(jìn)行比較。實(shí)驗(yàn)中所用的高維特征向量數(shù)據(jù)包括128維小波紋理特征和256維RGB特征兩種，它們均來(lái)自于根據(jù)Bing Images圖片搜索引擎所收錄的實(shí)際圖片數(shù)據(jù)，數(shù)據(jù)總量為100萬(wàn)。其中的100張圖片所對(duì)應(yīng)的特征向量被選出來(lái)作為查詢集。

在實(shí)驗(yàn)中，APMI和iDistance的參考點(diǎn)（reference point）的數(shù)量均設(shè)置為100；在128維和256維度數(shù)據(jù)的實(shí)驗(yàn)中，索引節(jié)點(diǎn)的頁(yè)面大小分別設(shè)置為32 KB和64KB。

5.2 實(shí)驗(yàn)分析

在實(shí)驗(yàn)中，將比較分析數(shù)據(jù)量對(duì)基于APMI和iDistance索引的kNN檢索的平均響應(yīng)時(shí)間的影響。數(shù)據(jù)量的大小范圍設(shè)置為20萬(wàn)-100萬(wàn)，k設(shè)置為100，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

實(shí)驗(yàn)結(jié)果表明，在查詢的平均響應(yīng)時(shí)間上，本文提出的基于APMI的kNN檢索在計(jì)劃所有的實(shí)驗(yàn)場(chǎng)景下都取得了最好的效果.唯一的例外是：當(dāng)維度是256維且數(shù)據(jù)量小于400K時(shí)，基于APMI的kNN查詢處理的響應(yīng)時(shí)間略高于iDistance。在絕大部分時(shí)候，APMI的效率都要比iDistance好，這主要是由于iDistance將數(shù)據(jù)空間中的聚簇的中心選為“reference point”，而除此之外，APMI還將索引節(jié)點(diǎn)的中心作為某種意義上的“reference point”。因此，APMI在“reference point”的數(shù)量上通常會(huì)大于iDistance。此外，作為“reference point”的APIM的索引節(jié)點(diǎn)的中心通常只是用于代表較小范圍內(nèi)的數(shù)據(jù)對(duì)象，因此，它會(huì)使得kNN剪枝過(guò)程更為有效和準(zhǔn)確。這是APMI在實(shí)驗(yàn)中通常更容易比iDistance中取得更好的I/O優(yōu)化效率，能夠節(jié)省更多的I/O開(kāi)銷的直接愿意之一。

此外，APMI索引沒(méi)有使用傳統(tǒng)的計(jì)算開(kāi)銷較大的剪枝技術(shù)，而是采用了本文提出的計(jì)算開(kāi)銷很小的基于三角不等式進(jìn)行剪枝的策略，在kNN剪枝前就減少了很多不必要的I/O和相應(yīng)的計(jì)算，從而進(jìn)一步的提升了總體效率，最終獲得了更短的查詢響應(yīng)時(shí)間。

6 結(jié)語(yǔ)

傳統(tǒng)的高維索引技術(shù)通常只針對(duì)I/O開(kāi)銷進(jìn)行優(yōu)化，而沒(méi)有重復(fù)考慮到數(shù)據(jù)維度較高時(shí)，計(jì)算開(kāi)銷也會(huì)成為總體開(kāi)銷的重要組成部分這一情況。針對(duì)此問(wèn)題，本文提出了高維索引技術(shù)APMI，通過(guò)優(yōu)化度量空間的索引結(jié)構(gòu)、設(shè)計(jì)面向I/O優(yōu)化的剪枝策略、引入具有極低計(jì)算開(kāi)銷的三角剪枝方法等技術(shù)，從同時(shí)優(yōu)化I/O與計(jì)算開(kāi)銷的角度減少數(shù)據(jù)訪問(wèn)量，提升總體效率。并在大規(guī)模真實(shí)數(shù)據(jù)集的基礎(chǔ)上，驗(yàn)證了APMI技術(shù)的高效性。

參考文獻(xiàn)

[1]P.Ciaccia，M.Patella，and P.Zezula. M-tree：An efficient access method for similarity search in metric spaces[C].Proc.VLDB，1997.

[2] T.Bozkaya，Z.?zsoyoglu.Indexing Large Metric Spaces for Similarity Search Queries [J].ACM Trans.Database Syst.1999，24（03）.

[3] H.V.Jagadish，B.Chin Ooi，K.L.Tan，C.Yu，R.Zhang.iDistance：An adaptive B -tree based indexing method for nearest neighbor search[J].ACM Trans.Database Syst.2005，30（02）.

[4] Y.Sakurai，M.Yoshikawa，S.Uemura， H.Kojima.The A-tree：An Index Structure for High-Dimensional Spaces Using Relative Approximation[C]. Proc.VLDB，2000.

[5] H.Shen，X.Zhou，A.Zhou.An adaptive and dynamic dimensionality reduction method for high-dimensional indexing[J].VLDB Journal.2007，16（02）.

[6] Z.Huang，H.Shen，J.Liu，X.Zhou. Effective data co-reduction for multimedia similarity search[C].Proc.SIGMOD，2011.

[7] 林朝暉，于俊清，何云峰，管濤，艾列富.高維分布式局部敏感哈希索引方法[J].計(jì)算機(jī)科學(xué)與探索，2013（09）.

作者單位

貴州航天電器股份有限公司 貴州省貴陽(yáng)市 550009