We study I he problem of computing approximate quantiles in large-scale sensor networks communication-efficient ly, a problem previously studied by Greenwald and Khana [12] and Shrivastava et al. [21]. Their algorithms have a total communication cost of O(k log~2 n/∈) and O(k 1og u/∈), respectively, where k is the number of nodes in the network, n is the total size of the data sets held by all the nodes, u is the universe size, and t is the required approximation error. In this paper, we present a sampling based quantile computation algorithm with O(kh/∈~(1/2)) total communication (h is the height of the routing tree), which grows sublinearly with the network size except in the pathological case h = Θ(k). In our experiments on both synthetic and real data sets, this improvement translates into a 10 to 100-fold communication reduction for achieving the same accuracy in the computed quantiles. Meanwhile, the maximum individual node communication of our algorithm is no higher than that of the previous two algorithms.
展开▼
机译：我们研究了在大型传感器网络中高效通信地计算近似分位数的问题，这是Greenwald和Khana [12]和Shrivastava等人先前研究的问题。 [21]。他们的算法的总通信成本分别为O（k log〜2 n /∈）和O（k 1og u /∈），其中k是网络中的节点数，n是数据集的总大小由所有节点组成，u是宇宙大小，t是所需的近似误差。在本文中，我们提出了一种基于采样的分位数计算算法，其总通信量为O（kh /∈〜（1/2））（h是路由树的高度），除病理情况外，该算法随着网络规模而线性增长h =Θ（k）。在我们对合成数据集和真实数据集进行的实验中，这种改进将通信量减少了10到100倍，从而在计算分位数上实现了相同的精度。同时，我们算法的最大单节点通信量不高于前两种算法。
展开▼
