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

有效

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

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值+查詢半徑)。