[發(fā)明專利]一種基于IDistance的細(xì)粒度位碼過濾的相似性檢索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610124087.2
• 申請(qǐng)日: 2016-03-04
• 公開（公告）號(hào): CN105574214B
• 公開（公告）日: 2019-04-09
• 發(fā)明（設(shè)計(jì)）人: 袁鑫攀;汪燦飛;何岸;向一平;朱艷輝;滿君豐;李長(zhǎng)云
• 申請(qǐng)（專利權(quán)）人: 湖南工業(yè)大學(xué)
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 任重;馮振寧

1.一種基于IDistance的細(xì)粒度位碼過濾的相似性檢索方法，其特征在于，包括以下步驟：

S1、建立FGBC-IDistance的索引結(jié)構(gòu)圖；

S11、在錨點(diǎn)P_i(P_i1,P_i2,…,P_ij,…,P_id)的每一維的兩邊再尋找2個(gè)錨點(diǎn)作為次錨點(diǎn)，次錨點(diǎn)用((L₁,R₁),(L₂,R₂),…,(L_j,R_j)…,(L_d,R_d))表示，R_j>L_j，1≤j≤d，P_ij表示錨點(diǎn)P_i在第j維上的值，R_j和L_j表示錨點(diǎn)P_i的第j維上的兩個(gè)次錨點(diǎn)；

S12、細(xì)粒度位碼FGBC，設(shè)向量S(S₁,S₂,…,S_d)所屬的聚類子空間的錨點(diǎn)為P_i(P_i1,P_i2,…,P_ij,…,P_id)，向量S的FGBC碼表示為B_S(b_S11b_S12,b_S21b_S22,…,b_Sj1b_Sj2,…,b_Sd1b_Sd2)，其中b_Sj1b_Sj2滿足公式(1)：

其中，b_Sj1b_Sj2是向量S在錨點(diǎn)P_i的第j維上的位碼，S_j是向量S在第j維上的值；

S13、建立索引結(jié)構(gòu)圖；

S2、基于FGBC-IDistance的索引結(jié)構(gòu)圖進(jìn)行檢索，檢索過程為：

S21、通過IDistance檢索獲得候選集

通過和各個(gè)錨點(diǎn)P_i的距離來測(cè)算：查詢點(diǎn)q的搜索圓是否與該錨點(diǎn)P_i的向量子集相交；

相交的判斷公式為：dist(q,P_i)<C_i+r

不相交的判斷公式為：dist(q,P_i)>C_i+r

其中，函數(shù)dist(q，P_i)表示查詢點(diǎn)q到錨點(diǎn)P_i的距離，C_i為錨點(diǎn)P_i的向量子集中離錨點(diǎn)P_i最遠(yuǎn)的向量的距離，r為查詢點(diǎn)q的搜索圓的半徑；

若不相交則該錨點(diǎn)的向量子集中無檢索目標(biāo)點(diǎn)；

若相交，則確定錨點(diǎn)P_i搜索的距離(dist)環(huán)體范圍：

{x∈P_i,max(dist(P_i,q)-r,0)＜dist(P_i,x)＜min(dist(P_i,q)+r,C_i)}

其中，x表示任意向量；

從而確定iDist的搜索范圍：

{x∈P_i,i*c+max(dist(P_i,q)-r,0)＜iDist(P_i,x)＜i*c+min(dist(P_i,q)+r,C_i)}檢索到的向量集則為候選集；

S22、對(duì)候選集中的每個(gè)向量進(jìn)行FGBC碼過濾；

判斷是否過濾的原則是：查詢點(diǎn)q的搜索圓和錨點(diǎn)P_i的FGBC碼所在區(qū)域是否相交，若相交則不過濾，若不相交則過濾；

FGBC碼所在區(qū)域是FGBC碼將錨點(diǎn)P_i聚類子空間的每一維分成4個(gè)區(qū)域，每一維度產(chǎn)生的位碼長(zhǎng)度為2，則d維的數(shù)據(jù)產(chǎn)生的位碼長(zhǎng)度為2d，位碼將整個(gè)聚類子空間劃分成了2^2d個(gè)小區(qū)域；

S23、對(duì)過濾后的候選集中的每個(gè)向量與查詢點(diǎn)q進(jìn)行距離計(jì)算，若距離小于r，則進(jìn)入最終的檢索結(jié)果集。