[發明專利]一種基于街區距離的高維向量快速檢索算法

有效

• 申請號: 201110291515.8
• 申請日: 2011-09-30
• 公開（公告）號: CN102306202A
• 公開（公告）日: 2012-01-04
• 發明（設計）人: 黃祥林;楊麗芳;呂銳;呂慧
• 申請（專利權）人: 中國傳媒大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于多媒體信息檢索、智能信息處理、數據挖掘等數據處理領域，具體涉及的是一種基于街區距離的高維向量快速檢索算法。

背景技術

隨著計算機和信息技術的發展，產生了海量的多媒體數據，如何在海量的多媒體數據庫中快速找到所需的信息是當前多媒體數據庫領域研究的一個重點問題。傳統的方法是由人工對多媒體數據進行標注，然后通過文本檢索來實現多媒體信息檢索。然而人工標注存在工作量大和主觀性強的缺陷，對于爆炸式增長的多媒體數據來說，完全人工標注是不可實現的，因此需要研究基于內容的多媒體信息檢索技術。

實現基于內容的多媒體信息檢索的技術路線是：通過特征變換，將多媒體數據映射到高維空間中的點——特征向量，用該特征向量來描述多媒體對象，得到特征庫；然后用同樣的特征變換方法來提取查詢對象的特征向量，最后通過特征向量間的相似度匹配來實現多媒體信息的相似檢索。因此多媒體信息的相似檢索轉變為在高維特征空間中尋找與給定查詢點最近的點集的過程。

要在高維空間中尋找與給定查詢點最相近的點集，最簡單直觀的方法就是順序掃描，即依次將特征庫中的每個特征(高維向量)與查詢點進行相似度匹配，返回最匹配的那些特征點集，得到檢索結果。順序掃描隨著特征庫中特征數目和特征維度的增加，計算消耗時間線性增大，當特征庫中的特征數目很大時，順序掃描將不能滿足實時性需求。為了加快檢索速度，最常用的方法就是借助于高維索引技術。

為了實現對海量高維向量的管理，研究者們提出了大量的索引結構，其中最為經典的是以R-tree為代表的R-tree家族系列索引結構。R-tree是20世紀80年代由Guttman提出的，用于管理多維矩形塊數據而設計的一種索引結構，它是一種利用樹結構管理數據的高度平衡樹，每個節點用該節點中所有數據的最小外接矩形(MBR：Minimal?Bounding?Rectangle)來表示，實際數據僅出現在葉子節點中。該索引結構通過擴展也可用于高維空間中點數據的管理。在查詢過程中，從根節點層到葉子節點層進行向下搜索，通過計算查詢向量和各節點MBR之間的最小距離來判斷查詢范圍是否與某節點相交來實現剪枝過濾，僅搜索可能包含結果的子樹，從而加快檢索速度。該索引結構允許節點之間的空間重疊，影響了其查詢效率。為了提高R-tree的性能，研究者們相續提出了R⁺-tree、R^*-tree、SS-tree、SR-tree、X-tree、A-tree等索引結構。但這些樹型索引結構隨著特征維度的增加，查詢效率急劇下降，甚至不如順序掃描，這就是所謂的“維數災難”。

除了樹型結構之外，還存在高維到一維轉換的索引結構，例如：金字塔技術、NB-tree、iDistance、iMinMax等等。高維到一維轉換的索引結構通過某種規則，將高維向量映射為一維數據(稱為key值)，然后采用一維的B⁺-tree來管理這些key值，key值在B⁺-tree的葉子節點層有序排列。進行查詢時，首先通過相同的高維到一維轉換規則計算查詢向量的查詢key值，最后根據查詢范圍，確定搜索的key值起始位置和結束位置，并依次掃描這些key值對應的高維向量，計算查詢向量與這些高維向量間的相似性，返回那些最相似的高維向量集，得到檢索結果。由查詢過程可知，高維到一維轉換的索引結構在任何情況下性能均優于或等效于順序掃描，且基于前人的大量實驗表明，這類索引結構隨維數和數據量的增加，性能降低緩慢。

街區距離是高維向量相似度匹配算法中最常用的度量方式之一，其運算簡單，且具有較高的檢索效率，但先前提出的高維到一維轉換的索引結構大都是基于歐式距離匹配度量提出的，沒有哪一種能直接支持街區距離這一度量方式的。

發明內容

本發明的目的在于提出了一種基于街區距離的高維到一維轉換的索引結構BlockB-tree，通過高維到一維轉換后key值的過濾，能夠加快高維向量的相似檢索速度。該索引結構既能有效支持基于街區距離的查詢度量方式，同時也能支持歐式距離的查詢度量方式。