[發(fā)明專利]一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法

有效

• 申請?zhí)枺?/td>: 201510927383.1
• 申請日: 2015-12-14
• 公開（公告）號: CN105578575B
• 公開（公告）日: 2019-02-26
• 發(fā)明（設(shè)計(jì)）人: 胡海峰;何杰芳;吳建盛
• 申請（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號: H04W52/02
• 分類號: H04W52/02;H04W84/18
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 田凌濤

1.一種應(yīng)用于無線傳感網(wǎng)絡(luò)的分布式相似性查詢方法，其特征在于：針對無線傳感網(wǎng)絡(luò)中各個(gè)數(shù)據(jù)項(xiàng)進(jìn)行L組K維局部敏感哈希映射，構(gòu)建各個(gè)數(shù)據(jù)項(xiàng)分別所映射的L組K維局部敏感哈希指紋值，即一個(gè)數(shù)據(jù)項(xiàng)對應(yīng)L組局部敏感哈希指紋值集合，各組局部敏感哈希指紋值集合分別包括K維局部敏感哈希指紋值，L和K為預(yù)設(shè)整數(shù)值；所述分布式相似性查詢方法包括如下步驟：

步驟001.針對查詢數(shù)據(jù)項(xiàng)V_查詢，獲得其進(jìn)行L組K維局部敏感哈希映射時(shí)，各組各維按預(yù)設(shè)切割寬度W進(jìn)行分割取整前的映射值進(jìn)入步驟002；其中，l＝1、…、L，k＝1、…、K，A_l,k和B_l,k為無線傳感網(wǎng)絡(luò)中各數(shù)據(jù)項(xiàng)進(jìn)行L組K維局部敏感哈希映射時(shí)，各組各維所對應(yīng)的隨機(jī)參數(shù)，且無線傳感網(wǎng)絡(luò)中各個(gè)數(shù)據(jù)項(xiàng)之間所對應(yīng)各組各維的A_l,k和B_l,k彼此對應(yīng)相同，A_l,k為查詢數(shù)據(jù)項(xiàng)V_查詢對應(yīng)第l組第k維局部敏感哈希映射時(shí)，與查詢數(shù)據(jù)項(xiàng)V_查詢維數(shù)相同，且每一維服從P穩(wěn)態(tài)分布的隨機(jī)高維向量；B_l,k為查詢數(shù)據(jù)項(xiàng)V_查詢對應(yīng)第l組第k維局部敏感哈希映射時(shí)，屬于[0,W]之間的隨機(jī)數(shù)；

步驟002.根據(jù)查詢數(shù)據(jù)項(xiàng)V_查詢進(jìn)行L組K維局部敏感哈希映射時(shí)，各組各維按預(yù)設(shè)切割寬度W進(jìn)行分割取整前的映射值獲得查詢數(shù)據(jù)項(xiàng)V_查詢進(jìn)行L組K維局部敏感哈希映射后，各組局部敏感哈希指紋值集合中各維局部敏感哈希指紋值進(jìn)入步驟003；

步驟003.將無線傳感網(wǎng)絡(luò)中的所有數(shù)據(jù)項(xiàng)作為待對比數(shù)據(jù)項(xiàng)，分別針對各個(gè)待對比數(shù)據(jù)項(xiàng)，將待對比數(shù)據(jù)項(xiàng)各組局部敏感哈希指紋值集合中各維局部敏感哈希指紋值，分別與查詢數(shù)據(jù)項(xiàng)V_查詢對應(yīng)各組局部敏感哈希指紋值集合中對應(yīng)維局部敏感哈希指紋值進(jìn)行相減，獲得對應(yīng)差值進(jìn)入步驟004；其中，l_待對比＝l_查詢，l_待對比＝1、…、L，l_查詢＝1、…、L，表示待對比數(shù)據(jù)項(xiàng)第l_待對比組局部敏感哈希指紋值集合中第k維局部敏感哈希指紋值，與查詢數(shù)據(jù)項(xiàng)V_查詢第l_查詢組局部敏感哈希指紋值集合中第k維局部敏感哈希指紋值的相減結(jié)果；

步驟004.針對所有差值判斷是否存在絕對值大于1的是則定義該所對應(yīng)待對比數(shù)據(jù)項(xiàng)第l_待對比組局部敏感哈希指紋值集合與查詢數(shù)據(jù)項(xiàng)V_查詢第l_查詢組局部敏感哈希指紋值集合之間的組相似性權(quán)重并進(jìn)入步驟005；否則進(jìn)入步驟006；

步驟005.針對所有待對比數(shù)據(jù)項(xiàng)的局部敏感哈希指紋值集合中剩余局部敏感哈希指紋值集合，判斷是否存在所對應(yīng)所有差值的絕對值均不大于1的局部敏感哈希指紋值集合，是則進(jìn)入步驟006；否則進(jìn)入步驟008；

步驟006.分別針對所對應(yīng)所有差值的絕對值均不大于1的各組局部敏感哈希指紋值集合，根據(jù)其對應(yīng)的獲得所對應(yīng)的各個(gè)待對比數(shù)據(jù)項(xiàng)第l_待對比組局部敏感哈希指紋值集合，按如下公式：

獲得所對應(yīng)待對比數(shù)據(jù)項(xiàng)第l_待對比組局部敏感哈希指紋值集合中第k維局部敏感哈希指紋值，與查詢數(shù)據(jù)項(xiàng)V_查詢第l_查詢組局部敏感哈希指紋值集合中第k維局部敏感哈希指紋值的單位相似性權(quán)重然后進(jìn)入步驟007；

步驟007.針對所對應(yīng)所有差值的絕對值均不大于1的各組局部敏感哈希指紋值集合，根據(jù)如下公式：

獲得其對應(yīng)所對應(yīng)待對比數(shù)據(jù)項(xiàng)第l_待對比組局部敏感哈希指紋值集合與查詢數(shù)據(jù)項(xiàng)V_查詢第l_查詢組局部敏感哈希指紋值集合的組相似性權(quán)重并進(jìn)入步驟008；其中，λ為預(yù)設(shè)常數(shù)；

步驟008.分別針對無線傳感網(wǎng)絡(luò)中各個(gè)待對比數(shù)據(jù)項(xiàng)，將待對比數(shù)據(jù)項(xiàng)所有L組局部敏感哈希指紋值集合，分別相對于查詢數(shù)據(jù)項(xiàng)V_查詢對應(yīng)各組局部敏感哈希指紋值集合的組相似性權(quán)重相加，獲得該待對比數(shù)據(jù)項(xiàng)相對于查詢數(shù)據(jù)項(xiàng)V_查詢的相似性權(quán)重，并進(jìn)入步驟009；

步驟009.針對無線傳感網(wǎng)絡(luò)中各個(gè)待對比數(shù)據(jù)項(xiàng)相對于查詢數(shù)據(jù)項(xiàng)V_查詢的相似性權(quán)重，篩選獲得大于預(yù)設(shè)相似性權(quán)重閾值的相似性權(quán)重所對應(yīng)的待對比數(shù)據(jù)項(xiàng)，作為候選數(shù)據(jù)項(xiàng)，并進(jìn)入步驟010；

步驟010.根據(jù)查詢數(shù)據(jù)項(xiàng)V_查詢進(jìn)行局部敏感哈希映射前的數(shù)據(jù)，以及各個(gè)候選數(shù)據(jù)項(xiàng)進(jìn)行局部敏感哈希映射前的數(shù)據(jù)，分別計(jì)算各個(gè)候選數(shù)據(jù)項(xiàng)和查詢數(shù)據(jù)項(xiàng)V_查詢之間的歐式距離，然后篩選獲得大于預(yù)設(shè)歐式距離閾值的歐式距離所對應(yīng)的候選數(shù)據(jù)項(xiàng)，即查詢數(shù)據(jù)項(xiàng)V_查詢的相似性查詢結(jié)果。