APMI：一種同時優化I/O與計算開銷的高維索引技術

李煥軍

摘 要 本文提出了一種新的同時優化I/O與計算的高維索引技術APMI。該索引技術在判斷是否遍歷當前區域之前，先判斷該查詢范圍所擴展而成的超立方體是否與當前區域相交，以便減少無效的I/O開銷；此外，在遍歷每個索引節點數據點之前，通過三角剪枝方法篩除一部分數據點，以很小的計算開銷進一步減少了數據訪問量，進一步提升了總體效率。在大規模的真實數據集上的性能試驗表明，APMI較現有代表性技術有較大性能提升。

【關鍵詞】高維索引 性能優化 kNN檢索

1 引言

隨著多媒體數字娛樂設備和多媒體傳感器設備的普及，圖像、音頻、視頻等多媒體數據己成為人們日常生活中信息的重要來源，著名的IT咨詢公司IDG的研究報告表明，視頻，音頻，圖像等多媒體數據已經占到了當前信息數據總量的70%以上。如何對大規模多媒體數據進行有效的組織、分類和檢索，從而幫助人們快速的查找到自己感興趣的信息，已成為研究者們亟需解決的關鍵問題。其中，高維索引技術作為對大規模多媒體數據的內容進行檢索的關鍵技術和重要手段，其重要性也變得越來越突出，其廣闊的應用前景已為人們所公認，因而也成為學術界和產業界的研究熱點。

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

在某些情況下，可能不能直接獲取多媒體數據對象的特征向量，但是多媒體對象之間的距離關系仍然可以被獲取到。基于距離度量（metric）的索引技術就是針對這種情況而提出的一類高維索引技術。其基本原理是：基于某些選擇出來的參考點，根據數據對象到參考點之間的距離，將數據區域劃分為若干個區域。然后，kNN檢索的結果就可以根據給定的查詢對象到數據對象以及參考點之間的距離來獲得。代表性的索引技術包括M-Tree，MVP-Tree，iDistance等。

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

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

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

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

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

針對上述問題，本文提出了一種新的同時優化I/O與計算的高維索引技術APMI，以便提升高維數據檢索效率。本文的主要技術工作如下：

（1）優化度量空間的索引結構，為每個葉子結點增加了一個屬性，該屬性記錄該點到數據空間中心的距離；

（2）優化I/O開銷：在判斷是否遍歷當前區域之前，先判斷該查詢范圍所擴展而成的超立方體是否與當前區域相交，以便減少無效的I/O開銷；

（3）優化計算開銷：在遍歷每個索引節點數據點之前，通過三角剪枝方法篩除一部分數據點，以很小的計算開銷進一步減少了數據訪問量，進一步提升了總體效率。

2 APMI索引的數據存儲結構

APMI索引是一種基于度量，同時結合降維技術與聚類技術的高維索引技術，其在數據存儲的組織結構上與iDistance等度量空間索引比較相似，在此不再贅述。其核心思想包括三點：

（1）數據空間內每個點的表征可以通過參考點來表示；

（2）根據數據空間內點離參考點的距離組織索引；

（3）索引基于B+-Tree，鍵值是與空間距離有關的一維數據。基于以上思想，該索引可以通過距離間的度量進行剪枝。

APMI索引在存儲結構上相對于傳統的度量空間索引技術的優化之處在于：為索引的每個葉子結點增加了一個屬性，該屬性記錄該點到數據空間中心的距離。在進行數據檢索時，剪枝算法通過該點到與中心點的距離、該點到參考點的距離、查詢半徑作為參數，以三角剪枝的達到降低計算開銷的目的，進而提高查詢效率。

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

3 基于空間劃分策略的I/O開銷優化

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

圖2是一個采用I/O優化的剪枝策略的實例。其中左圖中給定了查詢點q，查詢半徑r，且q包含于P3。同時，q與P2滿足條件dist（O2，q）-r ≤ dist_max2。其中不過，q與r所形成的超球，與P2中O2所形成的超半球，其相交的這個分區頁，只包含O2所在金字塔頂端的幾個數據點。超過金字塔范圍所形成的超半球，即使與q的查詢范圍相交，但由于這個區域本身不存在屬于P2的任何數據點，所以查詢相交的這個頁面，對于整個查詢過程來說，是無效的I/O開銷。

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

4 計算開銷優化策略

對于基于度量空間的高維索引，存在一個普遍的問題，即所形成的超球體積會很大。如圖3的左圖所示：對于當前查詢q與查詢半徑r所形成的查詢區域，對于P2而言，可雙向遍歷到達；對于與P3而言，可向內遍歷到達。不難發現，因超球的體積很大，其包含的數據點分布也非常散亂。其需要遍歷的三個頁面中的很多數據點，浪費了大部分的計算開銷。

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

具體的，將為全部數據點增加一個屬性字段（包括查詢點q），記錄該點到數據空間中心center的距離。假定采用歐氏距離作為度量標準，p為數據空間內某個與查詢區域相交的索引節點頁面中的數據點，則存在以下三角不等式規則，可作為剪枝依據：

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

當規定查詢點q的查詢半徑r時，對于q查詢半徑內的所有候選點p，必須滿足：

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

否則，page內的點將被篩除，從而在僅進行三角剪枝這一計算開銷極小的處理的前提下，進一步減少了數據訪問量，提升了總體效率。

5 實驗結果與分析

5.1 實驗環境和設置

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

在實驗中，APMI和iDistance的參考點（reference point）的數量均設置為100；在128維和256維度數據的實驗中，索引節點的頁面大小分別設置為32 KB和64KB。

5.2 實驗分析

在實驗中，將比較分析數據量對基于APMI和iDistance索引的kNN檢索的平均響應時間的影響。數據量的大小范圍設置為20萬-100萬，k設置為100，實驗結果如圖4和圖5所示。

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

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

6 結語

傳統的高維索引技術通常只針對I/O開銷進行優化，而沒有重復考慮到數據維度較高時，計算開銷也會成為總體開銷的重要組成部分這一情況。針對此問題，本文提出了高維索引技術APMI，通過優化度量空間的索引結構、設計面向I/O優化的剪枝策略、引入具有極低計算開銷的三角剪枝方法等技術，從同時優化I/O與計算開銷的角度減少數據訪問量，提升總體效率。并在大規模真實數據集的基礎上，驗證了APMI技術的高效性。

參考文獻

[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].計算機科學與探索，2013（09）.

作者單位

貴州航天電器股份有限公司 貴州省貴陽市 550009