REIK覆蓋網絡的一個有效查找算法

宋靜靜

摘要：為了解決相似查找請求，我們探討了多維數據檢索問題。在很多的情況下，相似檢索是非常重要的。在本文中，我們為REIK覆蓋網絡提出了一個有效地相似查找算法，此時的網絡稱為SSREIK，SSREIK是一個新型的動態網絡結構，這是為了分布式路由消息建立的。它允許范圍估值，在分布方式中執行最近鄰節點請求，并且利用一個分布式統計資料集合，以確保找到所有的相似對象。

近幾年，P2P網絡迅速成為計算機界關注的熱點問題之一。P2P也就是對等網絡，從計算模式上來說，打破了傳統的C/S模式，在網絡中的每個節點的地位都是對等的。每個節點即充當服務器，為其他節點提供服務，同時也享用其他節點提供的服務。除此之外，節點可在任何時刻加入或離開網絡，并能路由到目的節點，節點動態地加入和離開網絡時，維護網絡的結構和功能成為設計的主要目的。在結構化P2P系統中，每個節點只存儲特定的信息或特定信息的索引。當用戶在系統中獲取信息時，必須知道這些信息存放到哪個節點。

本文我們介紹一個帶有相似查找算法的REIK覆蓋網絡，即SSREIK。它是利用分布式哈希表，確切的說，是在REIK覆蓋網絡中利用相似數據庫查找方法。

一、網絡的概述

SSREIK是解決REIK網絡相似查找的框架。在SSREIK中，每個節點都包含在兩層中，即REIK層和REIKiDistance層。在REIK網絡中，利用哈希函數將每個數據對象都映射到一個邏輯名稱空間，此空間也包含所有的邏輯節點，這樣有利于節點間的路由。由于REIK層的節點相互鏈接，所以SSREIK網絡的拓撲結構取決于REIK覆蓋網絡。

當一個新節點想加入網絡時，它先接觸一個已存在節點，并從REIKiDistance區域賦值一個鍵，它從相應的范圍接收到鍵對應的數據對象。新節點也接收到REIKiDistance的配置。為了離開網絡，節點必須通知它的后繼節點，并將自身所有數據發送到后繼節點。

REIKiDistance層形成了系統每個節點的接口。當接收到一個加入或離開操作時，它首先通過操作計算經過對象的REIKiDistance值。然后，REIK層地位鍵相應的節點，最后存儲節點或刪除。

在iDistance中由于常量c的使用，離散片組成的區域相當于簇。這樣可能會發生：一個節點對應屬于幾個簇的鍵的區間。反過來也一樣，對應一個簇的區間被劃分為幾個相鄰的REIKiDistance節點。因此，存儲數據的每個節點分別對應每個覆蓋簇。

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

在SSREIK中，每個節點都對應自己的數據，這構成了REIK覆蓋網絡。SSREIK是基于米制空間相似查找的向量檢索算法。

首先，節點在局部數據上利用簇算法。簇算法產生了簇集C={Ci：（pi，ri）}。每個簇都由一個參考點和一個半徑。每個數據對象都賦有最近簇，且利用iDistance方法映射一個一維數值。數據對象的iDistance值可用B+樹表示。系統節點在他們的局部數據中主要執行范圍查找。在簇列表中每個簇都執行范圍查找算法。算法如下所示：

此算法展示了在任意節點上如何執行查找操作。如果請求范圍與節點對應的簇區域相交，則執行第4行。因此，如果簇Ci滿足不等式

，則區間 產生B+樹。iDistance區間對應查找到的所有數據對象的簇區域。取回這些對象后，請求改進步驟。在改進步驟中，計算每個距離q的對象，如果在第8行小于r，則將對象添加到結果集S中。

對應每一個請求數據對象x，計算dist（q，x）且如果 ，則將x添加掃Range（q，r）請求結果集S中。

三、SSREIK的k個相似鄰節點（K-NN）查找

分布式P2P系統中，查找操作的每個輪回代價都非常高。理想狀態的P2P環境，優點是有個小的固定圈數，確保請求時間短，費用低。

本節中，我們介紹節點維護統計資料集的方法，此方法有助于計算從參考點p到第k個對象的距離，并避免了多重范圍請求的執行。與iDistance方法相似，節點執行相應的最近鄰節點請求。如果找到了不到k個數據對象，則增大請求半徑，直到找到k個數據對象。由于我們的方法是一個結構化P2P環境，因此可利用小半徑并不斷增加直到找到k個數據對象。

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

為了降低K-NN查找成本，每個中間節點接收到具有最短距離的節點數目不超過k。

四、總結

P2P技術應用于大量數據共享系統中。這些系統的必要條件是在大量數據中定位數據的有效方法。但是，現在的大多數P2P系統既沒有提供精確鍵匹配機制，也沒有提供有效的解決算法。本文我們對REIK網絡提出了一個相似查找算法，即SSREIK，這是一個動態結構網絡，建立了分布式路由消息。它允許范圍估值，在分布方式中執行最近鄰節點請求，并且利用一個分布式統計資料集合，以確保找到所有的相似對象。