ACM通信
研究突出了
技术角度:分配你的数据并拥有它
互连系统因特网、无线网络或传感器网络几乎涵盖了所有的计算环境。因此，我们的数据不再需要存储在集中的数据库中，并被很好地组织起来;相反，它可以跨越许多不同的地点，并通过通信链路连接起来。例如，关于股票交易的记录存在于世界各地的经纪公司和其他金融实体中。
但是，如果不能有效地处理数据以产生有用的信息，数据就毫无价值。输入数据集的基本集合，如最大值、平均值或中位数，可以组合起来评估数据的统计属性，并指导决策和行动，例如，通过检测股票市场趋势。
其中一些聚合可以通过公共网络基础设施快速计算，即连接所有存储信息的节点的“生成树”。例如，一个简单的递归算法可以计算平均值:每个节点将根在某个节点的每个子树计算的平均值取平均值;然后将得到的平均值和计数一起转发给父进程，父进程再将自己子树的结果取平均值。
假设有一个时间单位，允许接收所有孩子的信息并处理它们;每次迭代取一个时间单位，时间单位的数量与生成树的深度或网络的直径成正比，表示D。
本质上，相同的算法计算最大或最小值和类似的聚合。但平均值对异常值很敏感:当数据有较大的变化时，平均值可能会错误地反映数据。在股价高度波动的日子里，以极低报价进行的单笔股票交易可以显著地影响均值，使其变得无关紧要。中位数，其他四分位数，或者一般的kth数据集的元素在这些情况下更重要。
但是，尽管这里描述的简单算法适用于均值，但它不适用于计算中值，因为内部节点上的中值不一定是其子树中值的中值。可以用一种简单的分治方法来代替。这个算法从整个元素集合开始，在每一轮中随机选择一个元素主元素。然后，算法计算出大于主元的元素个数，并在相应的子区间内进行搜索。一个相当直接的分析表明，当枢轴是均匀随机选择的，元素计数是精确的，那么预期迭代次数是渐近的对数米，树的节点数。
Kuhn、Locher和Watten-hofer在大型异构网络中使用这种顺序算法，说明了当今网络算法设计者面临的挑战，以及他们必须提出的创新来解决这些挑战。
主要的障碍在于从庞大而分散的数据集中采样支点。然而，这三位研究人员避开了这一障碍，而是派出了一支搜索考察队，在数据中寻找支点。搜索将随机遍历父生成树，从根结点开始，并随机选择要继续搜索的子结点。这个选择会受到子树的子树大小的影响，但是仔细调整偏差可以在时间内均匀随机地选择一个枢轴二维。
Kuhn, Locher和Wattenhofer的算法不是一次选择一个主元D枢纽内时间O（D)，方法是在重叠的时间间隔中错开搜索几个支点。使用D枢轴，候选人的数量减少了一个因数D在每次迭代中，导致总时间复杂度为O（D日志Dn),n是网络中的节点数。然后，他们的论文展示了如何避免随机pivot选择，从而使算法具有确定性，尽管需要付出一些代价。
有了这些算法，分布式计算数据聚集的问题现在在很大程度上得到了解决。数据可以在网络上传播，但我们可以通过挖掘来推断重要的信息。
如果你想知道:答案是否定的。没有其他算法能做得更好。作者表明，任何寻找中位数的算法(和一般的kth物品)必须与花费的时间成正比D日志DN，即使它可以抛硬币。在分布式计算理论的真正传统中，下界源于问题中固有的不确定性。
这个想法是构建许多场景，每个场景都有一个不同的中值，并使用一个信息论论证来表明需要大量的时间来消除这些场景之间的歧义。
©2008 acm 0001-0782/08/0900 $5.00
允许制作本作品的全部或部分的数字或硬拷贝用于个人或课堂使用，但前提是该拷贝不是为了盈利或商业利益而制作或分发，并且该拷贝在第一页上带有本通知和完整引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2008 ACM有限公司
没有发现记录