In many emerging applications, the data which has to be monitored is of very high volume, dynamic, and distributed, making it infeasible to collect the distinct data streams to a central node and process them there. Often, the monitoring problem consists of determining whether the value of a global function, which depends on the union of all streams, crossed a certain threshold. A great deal of effort is directed at reducing communication overhead by transforming the monitoring of the global function to the testing of local constraints, checked independently at the nodes. Recently, geometric monitoring (GM) proved to be very useful for constructing such local constraints for general (non-linear, non-monotonic) functions. Alas, in all current variants of geometric monitoring, the constraints at all nodes share an identical structure and are, thus, unsuitable for handling heterogeneous streams, which obey different distributions at the distinct nodes. To remedy this, we propose a general approach for geometric monitoring of heterogeneous streams (HGM), which defines constraints tailored to fit the distinct data distributions at the nodes. While optimally selecting the constraints is an NP-hard problem, we provide a practical solution, which seeks to reduce running time by hierarchically clustering nodes with similar data distributions and then solving more, but simpler, optimization problems. Experiments are provided to support the validity of the proposed approach.
For a few years now, processing and monitoring of
distributed streams has been emerging as a major effort in
data management, with dedicated systems being developed
for the task [
Geometric monitoring (GM) [
The geometric technique can support any scoring function
f (), evaluated at the average of the dynamic data vectors.
Thus, f () is not assumed to obey some simple property (e.g.,
linearity or monotonicity). To add to the generality of the
technique [
A crucial component for reducing the communication required by the geometric method is the design of the safe-zone in each node. Nodes remain silent as long as their local vectors remain within their safe-zone. Thus, good safe-zones increase the probability that nodes will remain silent, while also guaranteeing correctness: a global threshold violation cannot occur unless at least one node’s local vector lies outside the corresponding node’s safe-zone.
However, prior work on geometric monitoring has failed to take into account the nature of heterogeneous data streams, in which the data distribution of the local vectors at different nodes may vary significantly. This has led to a uniform treatment of all nodes, independently of their characteristics, and the assignment of identical safe-zones (i.e., of the same shape and size) to all nodes.
As we demonstrate in this paper, designing safe-zones that take into account the data distribution of nodes can lead to efficiently monitoring threshold queries at a fraction (requiring an order of magnitude fewer messages) of what prior techniques achieve. However, designing different safe-zones for the nodes is by no means an easy task. In fact, the problem is NP-hard (proof omitted due to lack of space). We thus propose a more practical solution that hierarchically clusters nodes, based on the similarity of their data distributions, and then seeks to solve many small (and easier) optimization problems.
The contributions of this work are: • We formulate a far more general safe-zone assignment problem than those which were treated so far. Instead of constructing one safe-zone which is common to all nodes, we seek to fit each node with a safe-zone that suits its data distribution. • We present a practical solution, which uses hierarchical clustering of the nodes to construct the safe-zones, while applying various geometric and computational tools. • The resulting safe-zones were tested on real data, where we demonstrate that: (i) the hierarchical clustering approach dramatically reduces the running time of the safezone assignment process, (ii) our techniques may result in one order of magnitude (or even larger) improvements in communication over previous geometric monitoring methods, even for a small number of nodes.
Outline. We survey prior work on the geometric approach in Section 2. In Section 3 we formulate our optimization problem, which involves the design of safe-zones at the nodes. Section 4 presents our algorithmic framework. Experiments are resented in Section 5. Lastly, conclusions are offered.
Hereafter we denote our proposed method for geometric monitoring of heterogeneous streams as HGM, in contrast to prior work on geometric monitoring that is denoted GM.
Space limitations allow us to only survey previous work
on geometric monitoring (GM). We now describe some basic
ideas and concepts of the GM technique, which was
introduced and applied to monitor distributed data streams in [
As described in Section 1, each node Ni maintains a local
vector vi, while the monitoring function f () is evaluated
at the average v of the vi vectors. Before the monitoring
process, each node Ni is assigned a subset of the data space,
denoted as Si – its safe-zone – such that, as long as the local
vectors are inside their respective safe-zones, it is guaranteed
that the global function’s value did not cross the threshold;
thus the node remains silent as long as its local vector vi is
inside Si. If vi ∈/ Si (local violation), a violation recovery
(“balancing”) algorithm [
For details and scope of GM see [
Basic definitions relating to GM. A basic construct is the admissible region, defined by A , {v|f (v) ≤ T }. Since the value we wish to monitor is f v1+.n..+vn , any viable assignment of safe-zones must satisfy n ^ (vi ∈ Si) → v = (v1 + ... + vn)/n ∈ A. This guarantees i=1 that as long as all nodes are silent, the average of the vi vectors remains in A and, therefore, the function has not crossed the threshold. The question is, of course, how to determine the safe-zone Si of each node Ni; in a sense to be made precise in Section 3, it is desirable for the safe-zones to be as large as possible.
In [
Here we assume that C is given; it can be provided by any of the abovementioned methods (obviously, if A itself is convex, we just choose C = A). We propose to extend previous work in a more general direction. Our goal here is to handle a basic problem which haunts all the existing GM variants: the shapes of the safe-zones at different nodes are identical. Thus, if the data is heterogeneous across the distinct streams (an example is depicted in Figure 1), meaning that the data at different nodes obeys different distributions, existing GM algorithms will perform poorly, causing many local violations that do not correspond to global threshold crossing (“false alarms”).
C S1 N1
N2
S2
In this paper, we present a more general approach that allows to assign differently shaped safe-zones to different nodes. Our approach requires tackling a difficult optimization problem, for which practical solutions need to be devised.
We now seek to formulate an optimization problem, whose solution defines the safe-zones at all nodes. The safe-zones should satisfy the following properties: Correctness: If Si denotes the safe-zone at node Ni, we mnust have: S2 ie^=v1er(yvi t∈hrSeis)ho→ld (cvr1os+sin..g. +byvnf)(/vn) w∈illCr.esTulhtisinenasusarefes-ztohnaet N1 S1 N2 breach in at least one node.
Expansiveness: Every safe-zone breach (local violation) S1 S2
triggers communication, so the safe-zones should be as “large”
as possible. We measure the “size” of a safe-zone Si by its
probability volume, defined as SRi pi(v)dv where pi is the pdf 2 C
of the data at node Ni. Probabilistic models have proved
useful in predicting missing and future stream values in var- Figure 2: Schematic example of HGM safe-zone
asious monitoring and processing tasks [
Subject to S1⊕···⊕Sn ⊆ C (correctness)
n
where S1⊕·n··⊕Sn = v1+·n··+vn |v1 ∈ S1, . . . , vn ∈ Sn , or the
Minkowski sum [
n A, we use S1⊕...⊕Sn ⊆ C. This preserves correctness, since
n C ⊆ A. The reason we chose to use C is that typically it’s much easier to check the constraint for the Minkowski average containment in a convex set; this is discussed in Section 4.4.
To derive the target function R p1dv1 · ... · R pndvn, which
S1 Sn
estimates the probability that the local vectors of all nodes
will remain in their safe-zones, we assumed that the data is
not correlated between nodes (hence we multiply the
individual probabilities), as it was the case in the experiments
in Section 5 (see also [
Note that correctness and expansiveness have to reach a “compromise”: figuratively speaking, the correctness constraint restricts the size of the safe-zones, while the probability volume increases as the safe-zones become larger. This trade-off is central in the solution of the optimization problem.
The advantage of the resulting safe-zones is demonstrated by a schematic example (Figure 2), in which C and the stream pdfs are identical to those in Figure 1. In HGM, however, the individual safe-zones can be shaped very differently from C, allowing a much better coverage of the pdfs, while adhering to the correctness constraint. Intuitively speaking, nodes can trade “geometric slack” between them; here S1 trades “vertical slack” for “horizontal slack”.
We now briefly describe the overall operation of the
distributed nodes. The computation of the safe-zones is
initially performed by a coordinator node, using a process
described in this section. This process is performed
infrequently, since there is no need to change the safe-zones of
a node unless a global threshold violation occurs. As
described in Section 3, the input to the algorithm is: (1) The
probability distribution functions p1, . . . , pn at the n nodes.
These pdfs can be of any kind (e.g., Gaussian [
Given this input, the coordinator applies the algorithm described in Sections 4.1 to 4.5 to compute S1...Sn which solve the optimization problem defined in Section 3. Then, node Nk is assigned Sk. 4.1
In order to efficiently solve our optimization problem, we need to answer several questions: • What kinds of shapes to consider for candidate safezones? This is discussed in Section 4.2. • The target function is defined as the product of integrals of the respective pdfs on the candidate safe-zones. Given candidate safe-zones, how do we efficiently compute the target function? This is discussed in Section 4.3. • Given candidate safe-zones, how do we efficiently test if their Minkowski average lies in C? This is discussed in Section 4.4. • As we will point out, the number of variables to optimize over is very large, with this number increasing with the number of nodes. It is well-known that the computational cost of general optimization routines increases at a superlinear rate with the number of variables. To remedy this issue, we propose in Section 4.5 a hierarchical clustering approach, which uses a divide-and-conquer algorithm to reduce the problem to that of recursively computing safezones for small numbers of nodes. 4.2
The first step in solving an optimization problem is determining the parameters to optimize over. Here, the space of parameters is huge – all subsets of the Euclidean space are candidates for safe-zones. For one-dimensional (scalar) data, intervals provide a reasonable choice for safe-zones, but for higher dimensions no clear candidate exists.
To achieve a practical solution, we choose the safe-zones from a parametric family of shapes, denoted by S. This family of shapes should satisfy the following requirements: • It should be broad enough so that its members can reasonably approximate every subset which is a viable candidate for a safe-zone. • The members of S should have a relatively simple shape.
In practice, this means that they are polytopes with a
restricted number of vertices, or can be defined by a small
number of implicit equations (e.g., polynomials [
Minkowski average of members of S (Section 4.4).
The last two conditions allow efficient optimization. If
computing the integrals of the pdf or the Minkowski average are
time consuming, the optimization process may be lengthy.
We thus considered and applied in our algorithms various
polytopes (such as triangles, boxes, or more general
polytope) as safe-zones; this yielded good results in [
The choices of S applied here have provided good results in terms of safe-zone simplicity and effectiveness. However, the challenge of choosing the best shape for arbitrary functions and data distributions is quite formidable, and we plan to continue studying it in the future. 4.3
The target function is defined as the product of integrals of the respective pdfs on the candidate safe-zones. Typically, data is provided as discrete samples. The integral can be computed by first approximating the discrete samples by a continuous pdf, and then integrating it over the safe-zone. We used this approach, fitting a GMM (Gaussian Mixture Model) to the discrete data and integrating it over the safezones, which were defined as polytopes. To accelerate the computation of the integral, we used Green’s Theorem to reduce a double integral to a one-dimensional integral over the polygon’s boundary, for the two-dimensional data sets in the experiments. For higher dimensions, the integral can also be reduced to integrals of lower dimensions, or computed using Monte-Carlo methods. 4.4
A simple method to test the Minkowski sum constraint
relies on the following result [
Lemma 1. If P and Q are convex polytopes with vertices {Pi}, {Qj}, then P ⊕ Q is equal to the convex hull of the set {Pi + Qj}.
Now, assume we wish to test whether the Minkowski average of P and Q is contained in C. Since C is convex, it contains the convex hull of every of its subsets; hence it suffices to test whether the points (Pi + Qj)/2 are in C, for all i, j. If not all points are inside C, then the constraint violation can be measured by the maximal distance of a point (Pi + Qj)/2 from C’s boundary. The method easily generalizes to more polytopes: for three polytopes it is required to test the average of all triplets of vertices, etc. 4.5
While the algorithms presented in Sections 4.3-4.4 reduce
the running time for computing the safe-zones, our
optimization problem still poses a formidable difficulty. For
example, fitting octagonal safe-zones [
We first perform a bottom-up hierarchical clustering of
the nodes. To achieve this, a distance measure between
nodes needs to be defined. Since a node is represented by
its data vectors, a distance measure should be defined
between subsets of the Euclidean space. We apply the method
in [
After the hierarchical clustering is completed, the safezones are assigned top-down: first, the children of the root are assigned safe-zones under the constraint that their Minkowski average is contained in C. In the next level, the grandchildren of the root are assigned safe-zones under the constraint that their Minkowski average is contained in their parent nodes’ safe-zones, etc. The leaves are either individual nodes, or clusters which are uniform enough and can all be assigned safe-zones with identical shapes. 5.
HGM was implemented and compared with the GM method,
as described in [
5.1.1
Our data consists of air pollutant measurements taken
from “AirBase – The European Air Quality Database” [
To solve the optimization problem, it is necessary to define
a parametric family of shapes S from which the safe-zones
will be chosen. Section 4.2 discusses the properties this
family should satisfy. In [
The triangular safe-zones (Section 5.2) have two degrees of
freedom each (Mi and βi, see Figure 3), hence for n nodes
we have 2n parameters to optimize over. The safe-zones
in Section 5.3 require 36 parameters each. In all cases we
used the Matlab routine fmincon to solve the optimization
problem [
This set of experiments concerned monitoring the ratio
between two pollutants, NO and NO2, measured in distinct
sensors. Each of the n nodes holds a vector (xi, yi) (the two
concentrations), and the monitored function is PP xyii (in [
Improvement Over Previous GM Work. We compared HGM with GM in terms of the number of produced local violations. In Figure 5, the number of safe-zone violations is compared for various numbers of nodes. HGM results in significantly fewer local violations, even for a small number of nodes. As the number of nodes increases, the benefits of HGM over GM increase. For a modest network size of 10 nodes, HGM requires less than an order of magnitude fewer messages than GM. 5.3
Another example consists of monitoring a quadratic function with more general polyhedral safe-zones in three variables (Figure 6). The data consists of measurements of three pollutants (NO, NO2, SO2), and the safe-zones are polyhedra with 12 vertices. The admissible region A is the ellipsoid depicted in pink; since it is convex, C = A. As the extent of the data is far larger than A, the safe-zones surround the regions in which the data is denser. Here we did not compare to previous methods.
An approach for minimizing communication while monitoring threshold queries over heterogeneous distributed streams was presented. It is formulated as an optimization problem of a geometric and probabilistic flavor, whose solution assigns each node a “safe-zone” with the property that a node may remain silent as long as its data vector is in its safe-zone. While the problem is known to be difficult, a practical solution using a hierarchical clustering algorithm is presented and implemented for two and three dimensional data, allowing to achieve substantial improvement over previous work, while using rather simple safe-zones which also reduce the computational effort at the nodes.
This work was partially supported by the European Commission under ICT-FP7-LIFT-255951 (Local Inference in Massively Distributed Systems).