基于双阈值的分布式Top-|K|查询方法
基于双阈值的分布式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日
【发明者】李国瑞, 王颖 申请人:东北大学
【专利摘要】本发明涉及基于双阈值的分布式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日
【发明者】李国瑞, 王颖 申请人:东北大学
最新回复(0)