[發明專利]基于雙閾值的分布式Top?|K|查詢方法

有效

• 申請號: 201410175464.6
• 申請日: 2014-04-28
• 公開（公告）號: CN103984707B
• 公開（公告）日: 2017-04-05
• 發明（設計）人: 李國瑞;王穎
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京思海天達知識產權代理有限公司11203
• 代理人: 劉萍

1.基于雙閾值的分布式Top-|K|查詢方法，其特征在于，整個方案包括了三個階段：雙閾值計算階段、候選集計算階段、Top-|K|查詢階段；

分布式系統由m個節點構成，其中包括一個管理節點和多個成員節點，每個節點中包含一個由若干對(索引,值)構成并按值降序排列的元素列表L_j＝{(i,v_j(i)),i＝1,…n_j}，其中n_j為該節點中包含元素的個數；

管理節點遵循與成員節點相同的元素選取規則；定義全部元素和V(i)=Σj=1mvj(i),]]>部分元素和P(i)=Σj=1mvj′(i),]]>全部元素和上界U(i)=Σj=1mv‾j(i),]]>全部元素和下界L(i)=Σj=1mv‾j(i),]]>其中：

?

上述公式中v_j(i)已知表示第j個節點中索引為i的元素在當前元素選取范圍內，對于成員節點來說，該元素的值已由成員節點發送至管理節點；對于管理節點來說，該元素的值符合當前元素選取規則即在雙閾值計算階段中元素屬于前K個正元素與后K個負元素集合，在候選集計算階段中元素值屬于大于等于的正元素或小于等于的負元素集合，在Top-|K|查詢階段中元素索引屬于候選集S；因此，v_j(i)直接用于計算元素i的部分元素和、全部元素和上界或全部元素和下界；

與之相對應，v_j(i)未知表示第j個節點中索引為i的元素不在當前元素選取范圍內，對于成員節點來說，該元素的值沒有從成員節點發送至管理節點；對于管理節點來說，該元素的值不符合當前元素選取規則；因此，v_j(i)無法用于計算元素i的部分元素和、全部元素和上界或全部元素和下界，分別需要用0、正閾值或負閾值來代替；

雙閾值計算階段包括以下具體步驟：

1)成員節點向管理節點發送前K個正元素與后K個負元素集合；

2)管理節點計算所有接收元素的部分和；

3)管理節點計算前K個正元素和下界并賦值給

4)管理節點計算后K個負元素和上界并賦值給

5)管理節點計算正閾值與負閾值

6)管理節點向所有成員節點發送正閾值與負閾值

候選集計算階段包括以下具體步驟：

7)成員節點向管理節點發送所有未發送過的大于等于的正元素或小于等于的負元素集合；

8)管理節點計算所有接收元素的部分和；

9)管理節點計算前K個正元素部分和的下界并賦值給

10)管理節點計算后K個負元素部分和的上界并賦值給

11)管理節點計算所有接收元素的全部和上界；

12)管理節點計算所有接收元素的全部和下界；

13)管理節點構建候選集S＝{全部和上界或全部和下界的元素索引}；

14)管理節點向所有成員節點發送候選集S；

Top-|K|查詢階段包括以下具體步驟：

15)成員節點向管理節點發送候選集S中所有未發送過的元素集合；

16)管理節點計算候選集S中所有元素的全部和；

17)管理節點選取候選集S中絕對值最大的前K個元素。