【专利交易】【专利代理】【商标和版权申请】【高新技术企业认定】Tel:18215660330

基于双阈值的分布式Top-|K|查询方法

xiaoxiao2020-07-22  2

【专利交易】【专利代理】【商标和版权申请】【高新技术企业认定】Tel:18215660330

基于双阈值的分布式Top-|K|查询方法
【专利摘要】本发明涉及基于双阈值的分布式Top-|K|查询方法。整个方案包括了三个阶段:双阈值计算阶段、候选集计算阶段、Top-|K|查询阶段。本发明涉及一种分布式网络环境中查询绝对值最大的前K项元素聚合值(聚合函数的计算结果,如所有元素值的和)的方法,具体是一种通过部分已知数据构建分布式系统中元素聚合值的正、负阈值,从而在有限次交互过程中实现对绝对值最大的前K项元素聚合值进行查询的方法,可以应用于互联网、物联网等分布式系统中元素聚合值的Top-|K|项查询。本发明能够大大节省数据传输量,降低查询时延。
【专利说明】基于双阈值的分布式Top-|K|查询方法
【技术领域】
[0001]本发明涉及一种分布式网络环境中查询绝对值最大的前K项元素聚合值(聚合函数的计算结果,如所有元素值的和)的方法,具体是一种通过部分已知数据构建分布式系统中元素聚合值的正、负阈值,从而在有限次交互过程中实现对绝对值最大的前K项元素聚合值进行查询的方法,可以应用于互联网、物联网等分布式系统中元素聚合值的Top-1KI项查询。
【背景技术】
[0002]随着信息技术的不断发展,人们获取和处理数据的规模越来越大。在众多分布式应用中,如何实现快速高效地查询大规模数据集中的前|κ|项数据具有重要的作用。分布式系统中需要处理的数据集分散在多个节点内,如图1所示。因此,获取同一元素的聚合值需要在多个节点间传递相应元素的信息。进而,查询绝对值最大的前K项元素聚合值需要在分布式系统中频繁传递 大量的交互信息,从而造成带宽的消耗和查询的延时。
[0003]目前,分布式系 统中Top-1Kl查询采用单阈值的方法,查询过程需要在管理节点和成员节点间进行多次信息交换,需要消耗大量的带宽并产生较长时间的延迟,同时无法提前确定需求交互的次数。其他的Top-κ方法只适用于具有单调特性的聚合函数,无法实现对绝对值最大的前K项元素聚合值进行查询的需求。

【发明内容】

[0004]本发明的目的在于查询分布式系统中绝对值最大的前K项元素的聚合值,适用于具有两阶段单调特性的聚合函数。
[0005]为实现上述目的,本发明采取了以下技术方案。整个方案包括了三个阶段:双阈值计算阶段、候选集计算阶段、Top-1Kl查询阶段。方案中管理节点与成员节点之间的交互过程如图2所不。
[0006]分布式系统由m个节点构成,其中包括一个管理节点和多个成员节点,每个节点中包含一个由若干对(索引,值)构成并按值降序排列的元素列表Lj= {(i,Vj(i)),i=I,…η」},其中η」为该节点中包含元素的个数。管理节点遵循与成员节点相同的元素选
取规则。定义全部元素和
【权利要求】
1.基于双阈值的分布式Top-lKl查询方法,其特征在于,整个方案包括了三个阶段:双阈值计算阶段、候选集计算阶段、Top-ΙκΙ查询阶段; 分布式系统由m个节点构成,其中包括一个管理节点和多个成员节点,每个节点中包含一个由若干对(索引,值)构成并按值降序排列的元素列表Lj= {(i,vdi)),i = 1,...ηj},其中ηj为该节点中包含元素的个数;




管理节点遵循与成员节点相同的元素选取规则;定义全部元素和
【文档编号】G06F17/30GK103984707SQ201410175464
【公开日】2014年8月13日 申请日期:2014年4月28日 优先权日:2014年4月28日
【发明者】李国瑞, 王颖 申请人:东北大学

【专利交易】【专利代理】【商标和版权申请】【高新技术企业认定】Tel:18215660330

最新回复(0)