REIK覆蓋網(wǎng)絡(luò)的一個(gè)有效查找算法

宋靜靜

摘要：為了解決相似查找請(qǐng)求，我們探討了多維數(shù)據(jù)檢索問題。在很多的情況下，相似檢索是非常重要的。在本文中，我們?yōu)镽EIK覆蓋網(wǎng)絡(luò)提出了一個(gè)有效地相似查找算法，此時(shí)的網(wǎng)絡(luò)稱為SSREIK，SSREIK是一個(gè)新型的動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)，這是為了分布式路由消息建立的。它允許范圍估值，在分布方式中執(zhí)行最近鄰節(jié)點(diǎn)請(qǐng)求，并且利用一個(gè)分布式統(tǒng)計(jì)資料集合，以確保找到所有的相似對(duì)象。

近幾年，P2P網(wǎng)絡(luò)迅速成為計(jì)算機(jī)界關(guān)注的熱點(diǎn)問題之一。P2P也就是對(duì)等網(wǎng)絡(luò)，從計(jì)算模式上來說，打破了傳統(tǒng)的C/S模式，在網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的地位都是對(duì)等的。每個(gè)節(jié)點(diǎn)即充當(dāng)服務(wù)器，為其他節(jié)點(diǎn)提供服務(wù)，同時(shí)也享用其他節(jié)點(diǎn)提供的服務(wù)。除此之外，節(jié)點(diǎn)可在任何時(shí)刻加入或離開網(wǎng)絡(luò)，并能路由到目的節(jié)點(diǎn)，節(jié)點(diǎn)動(dòng)態(tài)地加入和離開網(wǎng)絡(luò)時(shí)，維護(hù)網(wǎng)絡(luò)的結(jié)構(gòu)和功能成為設(shè)計(jì)的主要目的。在結(jié)構(gòu)化P2P系統(tǒng)中，每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定的信息或特定信息的索引。當(dāng)用戶在系統(tǒng)中獲取信息時(shí)，必須知道這些信息存放到哪個(gè)節(jié)點(diǎn)。

本文我們介紹一個(gè)帶有相似查找算法的REIK覆蓋網(wǎng)絡(luò)，即SSREIK。它是利用分布式哈希表，確切的說，是在REIK覆蓋網(wǎng)絡(luò)中利用相似數(shù)據(jù)庫(kù)查找方法。

一、網(wǎng)絡(luò)的概述

SSREIK是解決REIK網(wǎng)絡(luò)相似查找的框架。在SSREIK中，每個(gè)節(jié)點(diǎn)都包含在兩層中，即REIK層和REIKiDistance層。在REIK網(wǎng)絡(luò)中，利用哈希函數(shù)將每個(gè)數(shù)據(jù)對(duì)象都映射到一個(gè)邏輯名稱空間，此空間也包含所有的邏輯節(jié)點(diǎn)，這樣有利于節(jié)點(diǎn)間的路由。由于REIK層的節(jié)點(diǎn)相互鏈接，所以SSREIK網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)取決于REIK覆蓋網(wǎng)絡(luò)。

當(dāng)一個(gè)新節(jié)點(diǎn)想加入網(wǎng)絡(luò)時(shí)，它先接觸一個(gè)已存在節(jié)點(diǎn)，并從REIKiDistance區(qū)域賦值一個(gè)鍵，它從相應(yīng)的范圍接收到鍵對(duì)應(yīng)的數(shù)據(jù)對(duì)象。新節(jié)點(diǎn)也接收到REIKiDistance的配置。為了離開網(wǎng)絡(luò)，節(jié)點(diǎn)必須通知它的后繼節(jié)點(diǎn)，并將自身所有數(shù)據(jù)發(fā)送到后繼節(jié)點(diǎn)。

REIKiDistance層形成了系統(tǒng)每個(gè)節(jié)點(diǎn)的接口。當(dāng)接收到一個(gè)加入或離開操作時(shí)，它首先通過操作計(jì)算經(jīng)過對(duì)象的REIKiDistance值。然后，REIK層地位鍵相應(yīng)的節(jié)點(diǎn)，最后存儲(chǔ)節(jié)點(diǎn)或刪除。

在iDistance中由于常量c的使用，離散片組成的區(qū)域相當(dāng)于簇。這樣可能會(huì)發(fā)生：一個(gè)節(jié)點(diǎn)對(duì)應(yīng)屬于幾個(gè)簇的鍵的區(qū)間。反過來也一樣，對(duì)應(yīng)一個(gè)簇的區(qū)間被劃分為幾個(gè)相鄰的REIKiDistance節(jié)點(diǎn)。因此，存儲(chǔ)數(shù)據(jù)的每個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)每個(gè)覆蓋簇。

二、SSREIK的距離檢索查找（iDistance）

在SSREIK中，每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)自己的數(shù)據(jù)，這構(gòu)成了REIK覆蓋網(wǎng)絡(luò)。SSREIK是基于米制空間相似查找的向量檢索算法。

首先，節(jié)點(diǎn)在局部數(shù)據(jù)上利用簇算法。簇算法產(chǎn)生了簇集C={Ci：（pi，ri）}。每個(gè)簇都由一個(gè)參考點(diǎn)和一個(gè)半徑。每個(gè)數(shù)據(jù)對(duì)象都賦有最近簇，且利用iDistance方法映射一個(gè)一維數(shù)值。數(shù)據(jù)對(duì)象的iDistance值可用B+樹表示。系統(tǒng)節(jié)點(diǎn)在他們的局部數(shù)據(jù)中主要執(zhí)行范圍查找。在簇列表中每個(gè)簇都執(zhí)行范圍查找算法。算法如下所示：

此算法展示了在任意節(jié)點(diǎn)上如何執(zhí)行查找操作。如果請(qǐng)求范圍與節(jié)點(diǎn)對(duì)應(yīng)的簇區(qū)域相交，則執(zhí)行第4行。因此，如果簇Ci滿足不等式

，則區(qū)間 產(chǎn)生B+樹。iDistance區(qū)間對(duì)應(yīng)查找到的所有數(shù)據(jù)對(duì)象的簇區(qū)域。取回這些對(duì)象后，請(qǐng)求改進(jìn)步驟。在改進(jìn)步驟中，計(jì)算每個(gè)距離q的對(duì)象，如果在第8行小于r，則將對(duì)象添加到結(jié)果集S中。

對(duì)應(yīng)每一個(gè)請(qǐng)求數(shù)據(jù)對(duì)象x，計(jì)算dist（q，x）且如果 ，則將x添加掃Range（q，r）請(qǐng)求結(jié)果集S中。

三、SSREIK的k個(gè)相似鄰節(jié)點(diǎn)（K-NN）查找

分布式P2P系統(tǒng)中，查找操作的每個(gè)輪回代價(jià)都非常高。理想狀態(tài)的P2P環(huán)境，優(yōu)點(diǎn)是有個(gè)小的固定圈數(shù)，確保請(qǐng)求時(shí)間短，費(fèi)用低。

本節(jié)中，我們介紹節(jié)點(diǎn)維護(hù)統(tǒng)計(jì)資料集的方法，此方法有助于計(jì)算從參考點(diǎn)p到第k個(gè)對(duì)象的距離，并避免了多重范圍請(qǐng)求的執(zhí)行。與iDistance方法相似，節(jié)點(diǎn)執(zhí)行相應(yīng)的最近鄰節(jié)點(diǎn)請(qǐng)求。如果找到了不到k個(gè)數(shù)據(jù)對(duì)象，則增大請(qǐng)求半徑，直到找到k個(gè)數(shù)據(jù)對(duì)象。由于我們的方法是一個(gè)結(jié)構(gòu)化P2P環(huán)境，因此可利用小半徑并不斷增加直到找到k個(gè)數(shù)據(jù)對(duì)象。

通過分布式統(tǒng)計(jì)資料計(jì)算請(qǐng)求半徑。如果為了查找k個(gè)對(duì)象操作失敗，則不會(huì)避免第二次請(qǐng)求。在第二次請(qǐng)求中，上限由起始節(jié)點(diǎn)估算。為了減少查找操作成本，我們的方法利用了逐步增長(zhǎng)半徑。請(qǐng)求范圍R（q，r）的底限為rlow，即R（q，r，rlow），且滿足不等式 。在B+樹中修改兩個(gè)區(qū)間分別為：

為了降低K-NN查找成本，每個(gè)中間節(jié)點(diǎn)接收到具有最短距離的節(jié)點(diǎn)數(shù)目不超過k。

四、總結(jié)

P2P技術(shù)應(yīng)用于大量數(shù)據(jù)共享系統(tǒng)中。這些系統(tǒng)的必要條件是在大量數(shù)據(jù)中定位數(shù)據(jù)的有效方法。但是，現(xiàn)在的大多數(shù)P2P系統(tǒng)既沒有提供精確鍵匹配機(jī)制，也沒有提供有效的解決算法。本文我們對(duì)REIK網(wǎng)絡(luò)提出了一個(gè)相似查找算法，即SSREIK，這是一個(gè)動(dòng)態(tài)結(jié)構(gòu)網(wǎng)絡(luò)，建立了分布式路由消息。它允許范圍估值，在分布方式中執(zhí)行最近鄰節(jié)點(diǎn)請(qǐng)求，并且利用一個(gè)分布式統(tǒng)計(jì)資料集合，以確保找到所有的相似對(duì)象。