[發明專利]一種應用哈希Hash劃分桶快速獲得鄰域的方法

有效

• 申請號: 201310261081.6
• 申請日: 2013-06-26
• 公開（公告）號: CN103345491B
• 公開（公告）日: 2016-11-23
• 發明（設計）人: 蔣云良;曾志勇;劉勇
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 劉曉春

1.一種應用哈希Hash劃分桶快速獲得鄰域的方法，其特征在于它包括如下步驟：

步驟一，求分桶坐標系的坐標原點x₀，

根據給定的鄰域系統NRS=<U，N,θ>，U是全部樣本記錄構成的集合，N表示鄰域關系，θ為鄰域半徑；

步驟二，求樣本的距離，

對于求樣本間的距離||x_i-x₀||;

步驟三，根據步驟二中的樣本距離，用Hash方法建立搜索桶：

對于∀xi∈U,i=1,2,···,n,]]>計算k是非負整數。以k作為hash?Key建立hash表。建立hash表在空間內的球面模型：將hash?Key作為球面的半徑，hash表在空間內就是一系列相互嵌套的球；某一hash?Key下的樣本，處于以hash?Key為半徑的球面與hashKey-1為半徑的球面之間的空間內，相鄰球面間的空間稱為所述桶，B₁，B₂，…，B_b，為由b個hash?Key值作為半徑所得的b個桶。

步驟四，獲得鄰域：

桶B_k-1，B_k，B_k+1內的記錄，獲得樣本x的鄰域。

2.如權利要求1所述的一種應用哈希Hash劃分桶快速獲得鄰域的方法，其特征在于x₀取原點或者是在N中最小值組成的一個特征向量。

3.如權利要求1所述的一種應用哈希Hash劃分桶快速獲得鄰域的方法，其特征在于當搜索桶中樣本記錄獲得鄰域時，采用的是迭代方法，只需要搜索B_k，B_k+1桶內的記錄來獲得樣本x的鄰域。