Approximate aggregation for tracking quantiles and range countings in wireless sensor networks

作者：He, Zaobo; Cai, Zhipeng^*; Cheng, Siyao; Wang, Xiaoming

来源：Theoretical Computer Science, 2015, 607: 381-390.

DOI：10.1016/j.tcs.2015.07.056

• Quantiles
• Range countings
• Approximate aggregation

We consider the problem of tracking quantiles and range countings in wireless sensor networks. The quantiles and range countings are two important aggregations to characterize a data distribution. Let S(t) = (d(1), ... , d(n)) denote the multi-set of sensory data that have arrived until time t, which is a sequence of data orderly collected by nodes s(1), s(2), ... , s(k). One of our goals is to continuously track epsilon-approximate phi-quantiles (0 <= phi <= 1) of S(t) for all phi's with efficient total communication cost and balanced individual communication cost. The other goal is to track (epsilon, delta)-approximate range countings satisfying the requirement of arbitrary precision specified by different users. In this paper, a deterministic tracking algorithm based on a dynamic binary tree is proposed to track epsilon-approximate phi-quantiles, whose total communication cost is O (k/epsilon . log n . log(2)(1/epsilon)), where k is the number of the nodes in a network, n is the total number of the data, and epsilon is the user-specified approximation error. For range countings, a Bernoulli sampling based algorithm is proposed to track (epsilon, delta)-approximate range countings, whose t

• 出版日期2015-11-23
• 单位哈尔滨工业大学; 陕西师范大学