【论文评述】Algorithms for Distributed Functional Monitoring

文献:Graham Cormode, S. Muthukrishnan, and Ke Yi. 2011. Algorithms for distributed functional monitoring. ACM Trans. Algorithms 7, 2, Article 21 (March 2011), 20 pages.


本文研究这样的问题:

有一些站点,一个调度中心。有一些数据随时间到达这些站点。现在,我们要通过这个中心统计这些数据的一些属性(比如说数据总数、极值、方差等等),期望找到通信复杂度尽量低的算法。


形式化的:

个站点,一个调度中心。数据集中的数据按顺序逐一到达站点,到达时间依次为,每个数据只会到达中的一个站点。每个数据都是一个整数,即

时刻及之前到达的数据的全集,调度中心需要在每个时刻确定:

是否,如果是,输出

是否,如果是,输出.

如果,输出什么都可以。

其中是阈值,是容忍度。

如果是一个关于增函数,则上面的问题也等价于确定这样的一个时间,其满足,其中。一旦意识到现在是这样的,就输出

(可以把看作“容忍区间”,最晚应当在报警,最早在就报警也是可接受的)

另外,对于所有站点和中心都是提前已知的。


在继续展开之前,我们先提两种关于数据监测的分类方式。

第一种分类是:

  1. threshold monitoring(阈值监测):目标是确定是否超过了阈值

  2. value monitoring(值监测):目标是确定在每个时刻的近似值。

显然,完成值监测一定同时也能完成阈值监测;

另一方面,假设,分别设个值,运行相应的阈值监测程序,就可以完成容忍度为的值监测。

关于的解释:

我们在后面考虑的大多是阈值监测。

第二种分类是:

  1. one-shot monitoring(单次监测):只关心某个特定时刻的监测结果。

  2. continuous monitoring(连续监测):关心每个时刻的检测结果。

性质:

对于任意单调函数,一个通信复杂度为问题的连续监测算法可以诱导出一个的单次监测算法。

(实话讲,这个propositions的意义我没看出来,它并不能表现出连续问题更困难)


现在,我们关心下面这一族

,其中为全体数据元素的出现次数。

更简洁的,令频率向量),则

,其中-范数,即

因此

,即中有多少种不同元素。(notion abuse了一下)

,即元素的总数。

,在统计学里这是一个表征数据与uniform分布偏移程度的量。

上述函数族被称为-阶频率矩(Frequency Moments)。


我们给出一个一般算法,解决问题。

算法按“轮”执行,每轮有两个参数:
表示第轮的频率向量,

表示站点阈值。

另外,令表示第轮里站点更新频率向量

先别懵,具体的过程如下,看完你就知道这些参数是什么意思了:

(总阈值减去第轮频率矩 除以 两倍的站点数的次方)

在第轮中,站点收到的数据更新构成更新向量

这个是随着数据到来逐渐形成的,在这段过程中,每当增加(注意它取整了),就发送一个bit的信号给调度中心。(写成分数更清楚点)(即局部更新对总频率矩造成的影响为本轮阈值的几倍,就给调度中心几个信号)

当调度中心收到个信号时,就结束这一轮,并从各个站点收集,然后更新

,然后更新,然后把分发给所有站点。

然后开启第轮。

直到某轮结束时有,协调中心就发出信号,终止算法。


下面对这个算法进行分析

定理:

轮结束时,有。轮数至多为

证明:

考虑函数。(用来表征在频率矩意义上的差)

注意到,对于任意,在都只含有非负元素的情况下,关于都是凸函数。(因此可以用上琴生不等式)

第一个不等式是由于

这可以由展开式直接看出,对于向量的维:

本质上就是类似下面这种不等式的推广,

可自行验证,跟超可加性有关。(不同于凸性)

第一个不等式事实上是在说数据更新对频率矩产生的共同作用要大于局部作用的和。

那么这个“大于”有没有一个上限呢?(显然我们是需要的,否则算法的合法性会有问题)

第二个不等式就给出了这样一个上限

注意到,其等价于

这是因为,由Jensen不等式,

(第二个不等号来自关于第一个自变量的单调性)

把自变量中的提出来,

最后这个的乘数从哪来的呢?

这是因为,有个信号,因此至少在各个站点的视角攒出了,这个则是因为除了发出第个信号的站点外,其余站点都有残存的、未来得及发送信号报告的数据,每个站点的残存量,但可以任意接近

…待续