[發明專利]一種基于幾何空間劃分的向量模糊搜索方法及系統有效
| 申請號: | 201610880618.0 | 申請日: | 2016-10-09 |
| 公開(公告)號: | CN106528629B | 公開(公告)日: | 2018-04-03 |
| 發明(設計)人: | 鐘斌;田第鴻 | 申請(專利權)人: | 深圳云天勵飛技術有限公司 |
| 主分類號: | G06F17/30 | 分類號: | G06F17/30 |
| 代理公司: | 深圳市科吉華烽知識產權事務所(普通合伙)44248 | 代理人: | 于標 |
| 地址: | 518000 廣東省深圳市龍崗區橫崗*** | 國省代碼: | 廣東;44 |
| 權利要求書: | 查看更多 | 說明書: | 查看更多 |
| 摘要: | |||
| 搜索關鍵詞: | 一種 基于 幾何 空間 劃分 向量 模糊 搜索 方法 系統 | ||
1.一種基于幾何空間劃分的向量模糊搜索方法,包括向量的索引存儲方法及向量的搜索匹配方法,其特征在于,所述索引存儲方法包括以下步驟:
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進行循環完成所有向量的存儲。
2.根據權利要求1所述的向量模糊搜索方法,其特征在于,所述搜索匹配方法包括以下步驟:
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))進行遍歷獲取本次搜索結果。
3.根據權利要求2所述的向量模糊搜索方法,其特征在于,所述步驟C中空間塊內的任意兩個向量的距離小于區分粒度(Dm)。
4.根據權利要求3所述的向量模糊搜索方法,其特征在于,所述步驟E中的Hash Map里的元素為向量的鏈表。
5.根據權利要求2-4任一項所述的向量模糊搜索方法,其特征在于,所述步驟e中還包括以下步驟:
e1、將每次從IDs ( Space( ID(x), threshold))得到的元素設為ID(iterator);
e2、判斷ID(iterator)是否在Hash Map中;如果是,則取出對應列表中的所有向量加入到結果集的ResultSet中,如果否,則跳過此元素進行下一個ID處理;
e3、循環e1-e2步驟將所有ID(iterator)處理完成輸出ResultSet為本次搜索的結果。
6.一種基于幾何空間劃分的向量模糊搜索系統,包括向量的索引存儲系統及向量的搜索匹配系統,其特征在于,所述索引存儲系統包括:
度量模塊,用于將數值特征向量之間相似度轉換為幾何空間兩個向量之間的距離進行度量f(d(x,y));
區分粒度模塊,用于選取一個模糊搜索的搜索精度,并將這個精度轉換為對應的向量空間距離設置為Dm;
空間劃分模塊,用于以Dm為單位長度,對整個向量進行空間劃分并對得到所有的空間塊進行編號得到編號集合ID(x);
映射創建模塊,用于對于一個待存儲的向量a,通過ID映射關系得到這個向量(a)所屬于存儲塊的編號設為ID(a);
鏈表判斷模塊,用于以ID(x)為鍵值創建一個Hash Map,在存儲時判斷映射得到的ID(a)鏈表是否在Hash Map中有對應項;如果有,則直接將這個向量插入到對應的鏈表,如果沒有,則創建這個Hash Map鏈表項,并將當前向量插入到這個鏈表中;
循環模塊,用于對上述度量模塊、區分粒度模塊、空間劃分模塊、映射創建模塊、鏈表判斷模塊執行過程進行循環完成所有向量的存儲。
該專利技術資料僅供研究查看技術是否侵權等信息,商用須獲得專利權人授權。該專利全部權利屬于深圳云天勵飛技術有限公司,未經深圳云天勵飛技術有限公司許可,擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作,請聯系【客服】
本文鏈接:http://www.17sss.com.cn/pat/books/201610880618.0/1.html,轉載請聲明來源鉆瓜專利網。





