A paper a day keeps the doctor away: Medians and Beyond: New Aggregation Techniques for Sensor Networks
The Internet of
Things has spurred renewed interest in sensors and sensor telemetry.For each IoT application, modern
sensors--ones that support sensing, computation, and communication, collect
data about their environment, and relay it back to a "base station".
The base station aggregates data from all the sensors to make sense of the
Since most of the
sensors are deployed in settings that have severe constrains on power
consumption and battery life,it is
usually expensive to send all the raw telemetry data to the "base
station" without aggregation or sampling at each sensor. For certain class
of metrics data, such as counts, sums, and averages, the base station can
combine the aggregates from each sensor, and come up with meaningful statistics
overall. However for sensor aggregates such as median, mode, and percentiles,
the job of the base station becomes harder. The authors of the paper "Medians
and Beyond: New Aggregation Techniques for Sensor Networks" present an
algorithm called "Q-digest" that helps the base station calculate
statistics such as medians, modes, histograms, quantiles, and range queries
from aggregated sensor statistics.
The authors start by
highlighting the need for sensors to send aggregated data by citing that the
cost of transmitting one bit over the radio is more expensive than running one
instruction on the sensor.They also highlight
that from a user's perspective, in most cases, individual sensor values are not
important, and that users are fine with aggregate functions such as min/max,
count, sum, average, and percentiles. They review projects such as TinyDB and
Cougar, and expand on that work to enable computing percentiles through the
The authors first
describe Q-digest using one sensor, and then explain how to combine Q-digests
from multiple sensors to answer percentile and other queries. For one sensor,
the authors assume that the sensor captures integers with the range $[1,
The authors define a
binary partition tree over the range, with $\sigma$ leaf nodes representing the
values in the range, and the frequency of these values in the sensor data
stream. The binary tree has aheight$ \log \sigma $, and each node in the tree
represents a bucket that has a range defining the position and the width of the
bucket. For example, the root node of the tree describes the full range
$[1,\sigma]$, while its two children describe the ranges $[1,\sigma/2]$, and
$[\sigma/2+1,\sigma]$ respectively, and the leaf nodes are the raw data in the
stream. The Q-digest is a special subset of that conceptual tree that encodes
the distribution of sensor values in a compressed format, and satisfies the
Given a compression
parameter $k$, and a data stream of size $n$, a tree node $v$ is in the digest
[n/k]$ and $count(v) + count(v_p) + count (v_s) > [n/k]$ where $v_p$ is the
parent of $v$, and $v_s$ are the siblings of $v$. The root and leaf nodes are
exempt from satisfying both properties.
first property states that no node except leaf nodes should have a high count,
and the second states that no node and its siblings should have low counts. The
two properties help compress the tree into the Q-digest, and help with error bounds.
The authors walk
through an example of building and compressing the Q-digest, and provide proofs
of bounds on the size of the digest and maximum count error per node.
The authors then
show how we can use the Q-digest to answer different types of queries. For
example, to find the $q$th quantile, we sort the nodes of the Q-digest in
increasing bucket right endpoint values. The sorted list gives a post-order
traversal of the nodes of the Q-digest, that when scanned from the left and
adding the counts of value frequencies seen so far, will at some point exceed
$qn$. The node at which this happens is a good estimate of the $q$th quantile.
The authors show that the Q-digest can also be used to calculate inverse
quantile queries, range queries, and consensus queries.
The authors close by
sharing the experimental evaluation of accuracy, and message size, power
consumption of the algorithm, and discuss how to evolve the work to deal with
dropped values in the sensor network.