一種基於街區距離的高維向量快速檢索算法的製作方法
2023-05-11 09:09:11
專利名稱：一種基於街區距離的高維向量快速檢索算法的製作方法
技術領域：
本發明屬於多媒體信息檢索、智能信息處理、數據挖掘等數據處理領域，具體涉及的是一種基於街區距離的高維向量快速檢索算法。
背景技術：
隨著計算機和信息技術的發展，產生了海量的多媒體數據，如何在海量的多媒體資料庫中快速找到所需的信息是當前多媒體資料庫領域研究的一個重點問題。傳統的方法是由人工對多媒體數據進行標註，然後通過文本檢索來實現多媒體信息檢索。然而人工標註存在工作量大和主觀性強的缺陷，對於爆炸式增長的多媒體數據來說，完全人工標註是不可實現的，因此需要研究基於內容的多媒體信息檢索技術。實現基於內容的多媒體信息檢索的技術路線是通過特徵變換，將多媒體數據映射到高維空間中的點——特徵向量，用該特徵向量來描述多媒體對象，得到特徵庫；然後用同樣的特徵變換方法來提取查詢對象的特徵向量，最後通過特徵向量間的相似度匹配來實現多媒體信息的相似檢索。因此多媒體信息的相似檢索轉變為在高維特徵空間中尋找與給定查詢點最近的點集的過程。要在高維空間中尋找與給定查詢點最相近的點集，最簡單直觀的方法就是順序掃描，即依次將特徵庫中的每個特徵(高維向量)與查詢點進行相似度匹配，返回最匹配的那些特徵點集，得到檢索結果。順序掃描隨著特徵庫中特徵數目和特徵維度的增加，計算消耗時間線性增大，當特徵庫中的特徵數目很大時，順序掃描將不能滿足實時性需求。為了加快檢索速度，最常用的方法就是藉助於高維索引技術。為了實現對海量高維向量的管理，研究者們提出了大量的索引結構，其中最為經典的是以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、!Distance, iMinMax等等。高維到一維轉換的索引結構通過某種規則，將高維向量映射為一維數據(稱為key值)，然後採用一維的B+-tree來管理這些key值，key值在 B+-tree的葉子節點層有序排列。進行查詢時，首先通過相同的高維到一維轉換規則計算查詢向量的查詢key值，最後根據查詢範圍，確定搜索的key值起始位置和結束位置，並依次掃描這些key值對應的高維向量，計算查詢向量與這些高維向量間的相似性，返回那些最相似的高維向量集，得到檢索結果。由查詢過程可知，高維到一維轉換的索引結構在任何情況下性能均優於或等效於順序掃描，且基於前人的大量實驗表明，這類索引結構隨維數和數據量的增加，性能降低緩慢。街區距離是高維向量相似度匹配算法中最常用的度量方式之一，其運算簡單，且具有較高的檢索效率，但先前提出的高維到一維轉換的索引結構大都是基於歐式距離匹配度量提出的，沒有哪一種能直接支持街區距離這一度量方式的。
發明內容
本發明的目的在於提出了一種基於街區距離的高維到一維轉換的索引結構 BlockB-tree，通過高維到一維轉換後key值的過濾，能夠加快高維向量的相似檢索速度。 該索引結構既能有效支持基於街區距離的查詢度量方式，同時也能支持歐式距離的查詢度量方式。本發明的總體思想如下選取高維空間中的某個點作為參考點，將高維向量集 (特徵庫)中的所有高維向量採用這些向量對所選參考點間的街區距離映射為一維的key 值，然後用B+-tree來管理這些key值，得到BlockB-tree。進行查詢時，計算查詢向量和參考點間的街區距離，得到查詢key值，然後根據查詢範圍，確定搜索的key值起始位置和結束位置，並掃描這些key值對應的特徵向量，計算查詢向量與這些特徵向量間的相似性，返回那些最相似的向量集，得到檢索結果。具體創新點採用高維向量與選定參考點間的街區距離作為高維到一維轉換的規則，使得本發明提出的高維到一維轉換的索引結構BlockB-tree能夠直接支持基於街區距離的度量方式進行檢索，且也能支持基於歐式距離的度量方式進行檢索。本發明的具體方法步驟為(1)在高維空間中選取一個參考點，將所有的高維向量採用這些高維向量對所選參考點間的街區距離映射為一維的key值；(2)然後逐一將這些高維向量和對應的key值插入到BlockB-tree中；( 進行檢索時，首先計算查詢向量與所選參考點間的街區距離得到一維的查詢key值；(4)根據查詢範圍和查詢key值，得到需要進行搜索的key值的起始位置和結束位置，掃描計算這些key值對應的高維向量與查詢向量間的距離，得到檢索結果。更進一步，步驟1中所述的參考點的選取，既可選取原點或數據分布的質心為參考點，也可選取高維空間中的任意一個高維向量為參考點。更進一步，步驟2中所述的BlockB-tree採用B+-tree索引結構來管理上層的key 值，同時葉子節點層的每個key值都綁定一個指向對應高維向量的指針，當插入一個高維向量和對應的key值時，根據該key值的大小定位其應插入到的葉子節點，如果該葉子節點未滿，則直接將key值插入到該葉子節點中，並產生指向對應高維向量的指針，更新其父節點對應的key值；如果該葉子節點已滿，處理的方法包括以下兩種1)結合待插入的高維向量和key值，直接對該葉子節點進行分裂，並將分裂後新產生的葉子節點插入到其父節點中，同時更新其父節點對應的key值，如果父節點也已滿， 分裂過程繼續向上傳遞，並更新對應的key值；2)如果該葉子的左右兄弟節點存在未滿的情況，則結合其左右兄弟節點，進行待插入高維向量和key值的插入，並更新其父節點對應的key值，如果其左右兄弟節點均滿， 再採用方法1的處理方式進行處理。更進一步，步驟3中所述的檢索方式，既包括範圍查詢也包括k近鄰查詢。更進一步，步驟4中所述的查詢範圍，對於範圍查詢來說，是由查詢半徑來確定的，對於k近鄰查詢來說是由按某一步長遞增的查詢半徑來確定的，直到第k個近鄰到查詢向量的距離值小於查詢半徑為止。再進一步，如上所述的查詢半徑確定查詢範圍的方法，對於採用街區距離作為查詢度量的方式，查詢範圍為(查詢key值-查詢半徑)到(查詢key值+查詢半徑)。再進一步，如上所述的查詢半徑確定查詢範圍的方法，對於採用歐式距離作為查詢度量的方式，查詢範圍是由高維空間中點到超平面的距離公式來確定搜索的key值起始位置和結束位置的，設高維向量的維度為d，選取的參考點為0(Ol，o2, ... , od)，查詢向量為 q(qi，Q2,... , qd)，對應的查詢key值為key,，q以r為半徑的查詢範圍對應的key值起始位置為keyi，結束位置為key2:1)首先key,的計算可以表示為fk "0J = keyq，根據查詢向量q與參考點0之間
/=1
的位置關係，可將該式表示為A (q-o) = key,，得到係數矩陣A ；2)對於1 ^2所對應的各超平面；￡|\-0,| = 6炒2位於與查詢向量相對於參考點同一象限的超平面可表示為A(X-O) = key23)高維空間中點α到Ax = β所確定的超平面的距離公式d =
I At (AAt) ―1 (Α α - β ) I I，則根據點q到A (χ-O) = key2所確定的超平面的距離r，代入到該距離公式中，可以求出key2，根據查詢範圍上下界key值的對稱性，可以求出Icey1 r = \AT{AAry'[A{q-O)-key2]\\ = \AT{AAryx[keyq -L·y2]\=> Jcey2 = Keyq +r /| 丫⑷7.)-丨 |由對稱性得keyi= keyq-r/ | | At (AAt) 11再進一步，步驟4中所述的掃描計算起始位置和結束位置區間所有key值對應的高維向量與查詢向量間的距離，其掃描方法可以是從起始位置開始到結束位置的順序掃描，也可以是通過查詢key值定位到葉子節點應該進行插入的位置，從此位置開始，分別向前掃描到起始位置再向後掃描到結束位置或先向後掃描到結束位置再向前掃描到起始位置。
圖1 (a)本發明所述方法的流程 1 (b) BlockB-tree 的示例2在BlockB-tree上進行範圍查詢的框3在BlockB-tree上進行k近鄰查詢的框圖
具體實施方式
下面結合附圖對本發明的具體實施方式
做進一步說明本實施例的技術方案如圖1 (a)所示首先，從高維向量集中選取一個參考點；然後逐一計算高維向量集中每個高維向量與參考點間的街區距離，得到每個高維向量對應的key值；再將各高維向量及其對應的 key值進行插入，得到BlockB-tree (如圖1 (b)所示，上層為B+-tree，葉子節點層的每個key 值都綁定一個指向對應高維向量的指針)。在進行檢索時，計算查詢向量與參考點間的街區距離，得到查詢key值，並定位查詢key值在BlockB-tree葉子節點層應該進行插入的位置，通過查詢範圍和查詢key值，得到需要進行搜索的key值起始位置和結束位置，然後掃描計算這些key值對應的高維向量與查詢向量間的距離，得到檢索結果。本發明範圍查詢的流程圖如圖2所示，k近鄰查詢的流程圖如圖3所示。由圖3可知，k近鄰查詢是通過範圍查詢來實現，因此下面我們只對範圍查詢作進一步的分析。由於本發明所提出的索引結構BlockB-tree既能支持基於街區距離的查詢度量方式，又能支持基於歐式距離的查詢度量方式，由此，我們根據兩種查詢度量方式分別做詳細說明。已知高維向量的維度d及參考點為0(Ol，o2，…，od)，給定查詢向量q和查詢半徑r :1)街區距離的查詢度量方式首先計算查詢向量的key值keyj如公式1)，並定位 key,在葉子節點層所在的位置。然後由查詢半徑為r，可知對應的搜索key值的起始位置為 keyq-r,結束位置為keyjr。最後由key,所在的位置向前掃描到key^-r止(包含key^-r)， 逐一計算每個key值對應的高維向量\ (j的取值範圍由key^-r到key,間的key值數目確定)與查詢向量q間的街區距離(如公式2)，將所有街區距離小於等於r的高維向量插入到檢索結果向量集中；再由key^f在的位置向後掃描到keyjr止(包含keyjr)，逐一計算每個key值對應的高維向量Vk(k的取值範圍由key,到keyjr間的key值數目確定)與查詢向量q間的街區距離，將所有街區距離小於等於r的高維向量插入到檢索結果向量集中， 得到檢索結果。
權利要求
1.一種基於街區距離的高維向量快速檢索算法，其特徵在於具體步驟如下1)在高維空間中選取一個參考點，將所有的高維向量採用該高維向量對所選參考點間的街區距離映射為一維的key值；2)然後逐一將這些高維向量和對應的key值插入到BlockB-tree中；3)進行檢索時，首先計算查詢向量與所選參考點間的街區距離得到一維的查詢key值；4)根據查詢範圍和查詢key值，得到需要進行搜索的key值的起始位置和結束位置，掃描計算這些key值對應的高維向量與查詢向量間的距離，得到檢索結果。
2.如權利要求1所述的一種基於街區距離的高維向量快速檢索算法，其特徵在於步驟1中所述的參考點的選取，包括可選取原點或數據分布的質心為參考點，也包括可選取高維空間中的任意一個高維向量為參考點。
3.如權利要求1所述的一種基於街區距離的高維向量快速檢索算法，其特徵在於步驟2中所述的BlockB-tree採用B+-tree索引結構來管理上層的key值，同時葉子節點層的每個key值都綁定一個指向對應高維向量的指針，當插入一個高維向量和對應的key值時，根據該key值的大小定位其應插入到BlockB-tree中的某一葉子節點，如果該葉子節點未滿，則直接將key值插入到該葉子節點中，並產生指向對應高維向量的指針，更新其父節點對應的key值；如果該葉子節點已滿，處理的方式有兩種1)結合待插入的高維向量和key值，直接對該葉子節點進行分裂，並將分裂後新產生的葉子節點插入到其父節點中，同時更新其父節點對應的key值，如果父節點也已滿，分裂過程繼續向上傳遞，並更新對應的key值；2)如果該葉子節點的左右兄弟節點存在未滿的情況，則結合其左右兄弟節點，進行待插入高維向量和key值的插入，並更新其父節點對應的key值，如果其左右兄弟節點均滿， 再採用方法1的處理方式進行處理。
4.如權利要求1所述的一種基於街區距離的高維向量快速檢索算法，其特徵在於步驟3中所述的檢索方式，既包括範圍查詢也包括k近鄰查詢。
5.如權利要求1所述的一種基於街區距離的高維向量快速檢索算法，其特徵在於步驟4中所述的查詢範圍，對於範圍查詢來說，是由查詢半徑來確定的，對於k近鄰查詢來說是由按某一步長遞增的查詢半徑來確定的，直到第k個近鄰到查詢向量的距離值小於查詢半徑為止。
6.如權利要求5所述的查詢半徑確定查詢範圍的方法，其特徵在於對於採用街區距離作為查詢度量的方式，查詢範圍為(查詢key值-查詢半徑)到(查詢key值+查詢半徑)。
7.如權利要求5所述的查詢半徑確定查詢範圍的方法，其特徵在於對於採用歐式距離作為查詢度量的方式，查詢範圍是由高維空間中點到超平面的距離公式來確定搜索的 key值起始位置和結束位置的，設高維向量的維度為d，選取的參考點為0(Ol，o2,…，od)， 查詢向量為9( ，q2，…，qd)，對應的查詢key值為key,，q以r為半徑的查詢範圍對應的 key值起始位置為key」結束位置為key2 1)首先key,的計算可以表示為
8.如權利要求1所述的一種基於街區距離的高維向量快速檢索算法，其特徵在於步驟4中所述的掃描計算起始位置和結束位置區間所有key值對應的高維向量與查詢向量間的距離，其掃描方法可以是從起始位置開始到結束位置的順序掃描，也可以是通過查詢key 值定位到葉子節點應該進行插入的位置，從此位置開始，分別向前掃描到起始位置再向後掃描到結束位置或先向後掃描到結束位置再向前掃描到起始位置。
全文摘要
本發明是一種基於街區距離的高維向量快速檢索算法，屬於多媒體信息檢索、智能信息處理、數據挖掘等數據處理領域。在本發明中，提出了一種基於街區距離的高維到一維轉換的索引結構BlockB-tree，它採用高維向量對參考點間的街區距離將該高維向量映射為一維key值，用B+-tree索引結構來管理這些key值，同時葉子節點層的每個key值都綁定一個指向對應高維向量的指針。進行檢索時，使用相同的映射方法將查詢向量映射為一維的查詢key值，然後只需對key值與查詢key值相近的那些高維特徵進行相似度計算，減少計算量，大大加快檢索速度。在高維向量的相似度匹配算法中，街區距離是最常用的度量方式之一，其運算簡單，且具有較高的檢索效率，但當前大多數索引結構都是基於歐式距離匹配度量提出的。本發明提出的索引結構不但支持基於歐式距離度量方式的檢索，而且直接支持基於街區距離度量方式的檢索。
文檔編號G06F17/30GK102306202SQ20111029151
公開日2012年1月4日 申請日期2011年9月30日 優先權日2011年9月30日
發明者呂慧, 呂銳, 楊麗芳, 黃祥林 申請人:中國傳媒大學