REAL-TIME DATA ANALYTICS IN SENSOR NETWORKS - Managing and Mining Sensor Data - page 188

but outlying sensor readings are geographically independent. The algo-
rithm described in this study has each sensor compute the difference of
its reading to the median reading of its neighboring sensors. Then the
sensor collects all these differences from its neighborhood and standard-
izes them. If the absolute value of its standardized difference is larger
thanathreshold, d , then this sensor is deemed an outlier.
The TACO framework [40] was recently proposed by Giatrakos et al.
to operate in a WSN. In order to identify outliers, TACO takes into
account both the history of measurements of a given sensor, as well
as the spatial correlations with measurements of other sensors in the
vicinity. The outlier detection scheme is based on a two-level hashing
mechanism. The first level of hashing takes place locally in each sensor,
and is based on Locality Sensitive Hashing [23]. This is used for dimen-
sionality reduction, since the recent history of sensor data readings can
be succinctly represented in a space of much smaller dimensionality. As-
suming a clustered organization of the sensor network (i.e., hierarchical
organization with just two levels), each node communicates this reduced
representation of its history to the corresponding cluster-head, which
subsequently checks for similar representations among the other nodes
in the cluster. Similarity measures such as cosine similarity, Jaccard co-
ecient and correlation coecient, are supported. The representations
that do not find any similar matches make part of a list of potential
outliers that is further communicated to all the cluster-heads of the sen-
sor network. This communication step is eciently implemented using
a second hashing mechanism based on the hamming weight of the repre-
sentations. Overall, the approach has the advantage that it can provide
probabilistic guarantees on the accuracy of the results.
Giatrakos et al. [39] proposed a similar technique, only based on the
trends of the sensed data series.
3.3.2 Exact Approaches. Unlike the works above, some stud-
ies have proposed techniques for outlier detection that guarantee no false
negatives (i.e., they identify all outliers). This is a desirable property
for several critical applications (e.g., structural integrity monitoring).
The work by Branch et al. [13] describes a technique for distributed
outlier detection, where the goal is to identify global outliers (i.e., with
respect to the data collected by all sensors). This technique supports
definitions of outliers that conform to certain anti-monotonicity and
smoothness properties (e.g., it supports the distance to k th nearest neigh-
bor [78], but not the density-based LOF outliers [15]). According to the
proposed algorithm, each node maintains a local list of outliers, along
with additional information on the data it has transmitted to its neigh-