[發明專利]一種基于IDistance的細粒度位碼過濾的相似性檢索方法有效
| 申請號: | 201610124087.2 | 申請日: | 2016-03-04 |
| 公開(公告)號: | CN105574214B | 公開(公告)日: | 2019-04-09 |
| 發明(設計)人: | 袁鑫攀;汪燦飛;何岸;向一平;朱艷輝;滿君豐;李長云 | 申請(專利權)人: | 湖南工業大學 |
| 主分類號: | G06F16/901 | 分類號: | G06F16/901 |
| 代理公司: | 廣州粵高專利商標代理有限公司 44102 | 代理人: | 任重;馮振寧 |
| 地址: | 412000 湖*** | 國省代碼: | 湖南;43 |
| 權利要求書: | 查看更多 | 說明書: | 查看更多 |
| 摘要: | |||
| 搜索關鍵詞: | 一種 基于 idistance 細粒度 過濾 相似性 檢索 方法 | ||
1.一種基于IDistance的細粒度位碼過濾的相似性檢索方法,其特征在于,包括以下步驟:
S1、建立FGBC-IDistance的索引結構圖;
S11、在錨點Pi(Pi1,Pi2,…,Pij,…,Pid)的每一維的兩邊再尋找2個錨點作為次錨點,次錨點用((L1,R1),(L2,R2),…,(Lj,Rj)…,(Ld,Rd))表示,Rj>Lj,1≤j≤d,Pij表示錨點Pi在第j維上的值,Rj和Lj表示錨點Pi的第j維上的兩個次錨點;
S12、細粒度位碼FGBC,設向量S(S1,S2,…,Sd)所屬的聚類子空間的錨點為Pi(Pi1,Pi2,…,Pij,…,Pid),向量S的FGBC碼表示為BS(bS11bS12,bS21bS22,…,bSj1bSj2,…,bSd1bSd2),其中bSj1bSj2滿足公式(1):
其中,bSj1bSj2是向量S在錨點Pi的第j維上的位碼,Sj是向量S在第j維上的值;
S13、建立索引結構圖;
S2、基于FGBC-IDistance的索引結構圖進行檢索,檢索過程為:
S21、通過IDistance檢索獲得候選集
通過和各個錨點Pi的距離來測算:查詢點q的搜索圓是否與該錨點Pi的向量子集相交;
相交的判斷公式為:dist(q,Pi)<Ci+r
不相交的判斷公式為:dist(q,Pi)>Ci+r
其中,函數dist(q,Pi)表示查詢點q到錨點Pi的距離,Ci為錨點Pi的向量子集中離錨點Pi最遠的向量的距離,r為查詢點q的搜索圓的半徑;
若不相交則該錨點的向量子集中無檢索目標點;
若相交,則確定錨點Pi搜索的距離(dist)環體范圍:
{x∈Pi,max(dist(Pi,q)-r,0)<dist(Pi,x)<min(dist(Pi,q)+r,Ci)}
其中,x表示任意向量;
從而確定iDist的搜索范圍:
{x∈Pi,i*c+max(dist(Pi,q)-r,0)<iDist(Pi,x)<i*c+min(dist(Pi,q)+r,Ci)}檢索到的向量集則為候選集;
S22、對候選集中的每個向量進行FGBC碼過濾;
判斷是否過濾的原則是:查詢點q的搜索圓和錨點Pi的FGBC碼所在區域是否相交,若相交則不過濾,若不相交則過濾;
FGBC碼所在區域是FGBC碼將錨點Pi聚類子空間的每一維分成4個區域,每一維度產生的位碼長度為2,則d維的數據產生的位碼長度為2d,位碼將整個聚類子空間劃分成了22d個小區域;
S23、對過濾后的候選集中的每個向量與查詢點q進行距離計算,若距離小于r,則進入最終的檢索結果集。
該專利技術資料僅供研究查看技術是否侵權等信息,商用須獲得專利權人授權。該專利全部權利屬于湖南工業大學,未經湖南工業大學許可,擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作,請聯系【客服】
本文鏈接:http://www.szxzyx.cn/pat/books/201610124087.2/1.html,轉載請聲明來源鉆瓜專利網。





