技術領域

本發明屬于數據檢索技術領域，尤其涉及一種基于幾何空間劃分的向量模糊搜索方法及系統。

背景技術

目前基于視頻、圖片的智能分析及處理已經越來越廣泛地應用于各個領域當中。在這些應用中，一個典型的問題是：如何在大規模的集當中，通過搜索的方法得到某個特定的對象是否在這個數據集中、及有多少符合條件的對象在這個數據集中。

在這類應用中，通常在搜索前已經對待檢索的對象（如人臉圖片）進行了一些預處理，把這個對象用一個數值向量（整形或浮點向量）來進行描述，這個數值向量通常稱為這個原始對像的特征值，這個預處理的過程稱之為結構化過程；這個過程中的得到的特征值通常都具備可比較性，即兩個向量之間通過一個數值運算過程得到的結果，可以表征原始的兩個對象的相似度。在搜索過程中，先按一定的方法構造對象的特征值搜索庫，在具體的搜索過程中，通過不斷的計算搜索對象的特征值與搜索庫中特征值之間的相似度，在設定相似度門限情況，即可得到符合門限要求的對象的特征值的集合。

由上所述，視頻搜索/圖像搜索通過提取結構化特征值的過程轉換為數值向量搜索問題，而數值向量搜索包含兩個關鍵步驟：一個是數值向量庫的創建，即以什么樣的形式來存儲海量數據規模的向量集合；二是如果執行搜索過程，即在向量集合的存儲結構已經確定的情況下，以什么的流程/步驟/方法從向量集合中找到符合條件的目標向量。

在實際的應用中，現有的技術方案雖然從兩個方向出發都做出了很多有益的優化，如在第一步中通過向量hash將特征值進行聚類后存儲，降低第二步進行搜索時的進行向量相似度計算的規模，又如一些方案借用文本搜索中的倒排索引概念，將特征值匹配搜索運算轉換為矩陣的分解等等。這些方法都存在以下一項或多項問題：

1.雖然對運算進行了轉換，但數學含義不再等效，降低了搜索的精度。

2.雖然通過對索引結構的優化，降低了搜索過程中相似度匹配次數，但因為匹配需求并沒有消失，所以還是存在計算量隨規模的增長而增加的問題。

3.丟失了對模糊匹配的支持或模糊匹配的精度降低。

發明內容

本發明的目的在于提供一種基于幾何空間劃分的向量模糊搜索方法及系統，旨在解決上述的技術問題。

本發明是這樣實現的，一種基于幾何空間劃分的向量模糊搜索方法，包括向量的索引存儲方法及向量的搜索匹配方法，所述索引存儲方法包括以下步驟：

A、將數值特征向量之間相似度轉換為幾何空間兩個向量之間的距離進行度量f(d(x,y))；

B、選取一個模糊搜索的搜索精度，并將這個精度轉換為對應的向量空間距離設置為Dm；

C、以Dm為單位長度，對整個向量進行空間劃分并對得到所有的空間塊進行編號得到編號集合ID（x）;

D、對于一個待存儲的向量a，通過ID映射關系得到這個向量（a）所屬于存儲塊的編號設為ID（a）；

E、以ID（x）為鍵值創建一個Hash Map，在存儲時判斷映射得到的ID（a）鏈表是否在Hash Map中有對應項；如果有，則直接將這個向量插入到對應的鏈表，如果沒有，則創建這個Hash Map鏈表項，并將當前向量插入到這個鏈表中；

F、對上述步驟A-E進行循環完成所有向量的存儲。

本發明的進一步技術方案是：所述搜索匹配方法包括以下步驟：

a、將帶搜索的特征值向量x進行ID號映射并找到對應的空間塊ID（x）；

b、按照模糊度匹配的閾值（threshold）設定換算得到幾何空間的距離；

c、根據幾何空間的距離得到待搜索特征值向量的所在空間為中心的空間區域Space(ID(x),threshold)；

d、取得Space(ID(x),threshold)內所有空間塊的IDs(Space(ID, threshold))集合；

e、對IDs(Space(ID(x), threshold))進行遍歷獲取本次搜索結果。

本發明的進一步技術方案是：所述步驟C中空間塊內的任意兩個向量的距離小于區分粒度（Dm）。

本發明的進一步技術方案是：所述步驟D中的Hash Map里的元素為向量的鏈表。

本發明的進一步技術方案是：所述步驟e中還包括以下步驟：

e1、將每次從IDs ( Space( ID(x), threshold))得到的元素設為ID(iterator)；