DEIM Forum 2013 A8-1

Top-k Distance-based Outlier Detection on Uncertain Dataset
Salman Ahmed SHAIKH† and Hiroyuki KITAGAWA†† Graduate School of Systems and Information Engineering, University of Tsukuba,
1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
Abstract This paper studies the problem of top-k distance-based outlier detection on uncertain data. In thiswork, an uncertain object is modelled by a Gaussian probability density function. Since the Naive approach isvery expensive due to costly distance function between uncertain objects, a populated-cell list (PC-list) based top-k
distance-based outlier detection approach is proposed in this work. Where PC-list is a sorted list of non-empty
cells of a grid (grid is used to index dataset objects). Using PC-list, the top-k outlier detection algorithm needs
to consider only a fraction of dataset objects and hence quickly identiﬁes candidate objects for top-k outliers. An
extensive empirical study shows that our proposed approach is eﬀective, eﬃcient and scalable.
Key words Top-k Distance-based Outlier Detection, Uncertain Data, Gaussian Distribution, PC-list based Approach

1. Introduction

most commonly used PDF, i.e., Gaussian distribution. Since
the actual distance function is very costly to compute, we

Outlier detection is one of the most important data min-introduce a populated-cell list (PC-list) based top-k outlier

ing techniques with vital importance in many application

detection technique. PC-list is a sorted list of non-empty

domains including credit card fraud detection, network in-cells of a d-dimensional grid, where grid is used to index our

trusion detection, environment monitoring, etc. Hawkins [1]data. Using PC-list, our top-k outlier detection algorithm

deﬁnes an outlier as an observation that deviates so muchneeds to consider only a fraction of the dataset objects andfrom other observations as to arouse suspicion that it washence quickly identiﬁes candidate objects for top-k outliers.

generated by a diﬀerent mechanism.

The rest of the paper is organized as follows. Sec.2. sur-Most of the earliest outlier detection techniques were given

veys the related work. Sec.3. formally deﬁnes top-k distance-by statistics [2]. However, most statistical techniques are uni-

based outlier detection on uncertain datasets. Its naive ap-

variate, and in the majority of techniques, the parameter ofproach is given in Sec.4.. The PC-list and top-k algorithm

distribution is diﬃcult to determine. In order to overcome

are presented in Sec.5.. Sec.6. contains an extensive exper-

these problems several distance-based approaches for outlier

imental evaluation that demonstrates the eﬃciency and of

detection have been proposed in data mining [3], [4], [5].

proposed techniques. Sec.7. concludes our paper.

Most of the outlier detection techniques proposed in data
mining are suitable only for deterministic data. However,

2. Related Workdue to the incremental usage of sensors, RFIDs and similar

Distance-based outliers detection approach was introduced

devices for data collection these days, data contains certain

by Knorr, et al. in [3]. They deﬁned a point p to be an outlier

degree of inherent uncertainty [6], [7], [8]. The causes of un-

if at most M points are within D-distance of p. They also

certainty may include but are not limited to limitation ofpresented a Cell-based approach to eﬃciently compute theequipments, absence of data, inconsistent supply voltage anddistance-based outliers. [9] formulated distance-based out-

delay or loss of data in transfer [6]. In order to get reliable

liers as the top-t data points whose distance to their κth near-

results from such data, uncertainty needs to be considered

est neighbour is largest. Angiulli et al. in [10] gave a slightly

in calculation. Therefore in this work we study the problem

diﬀerent deﬁnition of outliers than [9] by considering the av-of top-k distance-based outlier detection on uncertain data.

erage distance to their k nearest neighbour. Besides, there

This paper assumes that uncertainty in the values obtained

are some works on the detection of distance-based outliers

from a sensor follows Gaussian distribution.

over stream data including [5] and [11]. Both of these works

In the following, uncertainty of data is modelled by theare based on the Knorr, et al. deﬁnition of distance-based

outliers. Furthermore, [11] gave an approximate algorithm
to reduce the memory space required by its exact counterpart. Later on [5] extended [11] work by adding the conceptsof multi-query and micro-cluster based distance-based outlier detection. A geometric approach of outlier detection has
also been proposed in [12]. The proposed solution is only
suitable for identifying abnormal nodes from the cluster ofnodes placed nearby and not valid for the problem whenthe measurements of a single node is classiﬁed as outliers,
based on the nodes past measurements. However all theseapproaches were given for deterministic data and could nothandle uncertain data.
Recently a lot of research has focused on managing, querying and mining of uncertain datasets [13], [14]. The problemof outlier detection on uncertain datasets was ﬁrst studied
by Aggarwal, et al. in [13]. They represented an uncertain
object by a PDF. They deﬁned an uncertain object o to bea density-based (δ, η) outlier, if the probability of o existing in some subspace of a region with density at least η isgreater than distance D from o.
This deﬁnition was given for deterministic data. However,the focus of this work is the detection of top-k outliers ona dataset whose attribute values are uncertain. We assume
that the uncertainty is given by Gaussian distribution. In
the following, we consider d-dimensional uncertain objects−→
oi , with attribute Ai = (xi,1 , ..., xi,d )T following Gaussian→
PDF with mean −µ = (µ , ..., µ )T and co-variance matrixinecessarily an outlier in full space as argued in [4]. [14] alsoi,dconsists of a set of such objects, GDB = {o1 , ..., oN }, where
N = |GDB| is the number of uncertain objects in GDB.
−→
The vector Ai is a random variable that follows Gaussian−→→
distribution A ∼ N (−µ , Σ ).
i

i

i

We assume that the observed coordinates (attribute val→ues) are vectors −µ of the objects which follow Gaussian disi

tribution. Based on this assumption, in the rest of the paper→
we will use −µ to denote the real observed coordinates (atitribute values) of object oi .
3. 1 Top-k Distance-based Outliers in Uncertain

less than δ. However, their work focuses on detecting outliers in subspaces. In practise, an outlier in subspace is not

i,1

2
2
Σi = diag(σi,1, ..., σi,d), respectively. The complete databaseData
We naturally extend Deﬁnition 1 for top-k distance-based
outliers on uncertain datasets as follows.

proposed a distance-based outlier detection algorithm on uncertain datasets, which was later extended in [15] for prob-

Definition 2. The top-k distance-based outliers are the kabilistic data streams. However in their works, an object’s

uncertain objects in the dataset GDB for which the expected

existential uncertainty is considered rather than representing

number of objects lying within D-distance is smallest.

an object by a PDF as in our work.
In [16], we proposed a cell-based approach of distancebased outlier detection on uncertain data. According to [16],an uncertain object o is a distance-based outlier if the expected number of objects lying within its D-distance is not
greater than θ = N (1 − p), where N is the number of objects
in the dataset and p is the fraction of objects that lie farther
than D-distance of o. In practise parameter p is diﬃcult to

We call objects that lie within the D-distance of an object
o as D-neighbours of o, and denote the set of D-neighboursof o as DN (o). In order to ﬁnd distance-based outliers in
GDB, the distance between uncertain objects needs to be
calculated, which is given by another distribution known as−→−→
the Gaussian diﬀerence distribution [18]. Let Ai and Aj
be two independent d-dimensional normal random vectors→→ = (µ , ..., µ )Twith means −µ = (µ , ..., µ )T and −µidetermine and is dependent on N . An arbitrary value of p
may results in a very few or a lot of outliers for diﬀerent N .
Moreover from [16], we cannot obtain the outlier’s ranking.

i

Therefore in this work, we propose PC-list based approachof top-k distance-based outlier detection, which can always
obtain k strongest outliers along with their ranking, providedk<= N.

3. Distance-based Outliers in Uncertain
Data
The very ﬁrst deﬁnition of distance-based outlier detection
was given by Knorr, et al. in [3]. They deﬁned distance-based
outliers as follows.
Definition 1. An object o in a dataset DB is a distancebased outlier, if at least fraction p of the objects in DB lies

i,1

j

i,d

j,1

j,d

2
2
and diagonal covariance matrices Σi = diag(σi,1, ..., σi,d
)
−
→
−
→
2
2
and Σj = diag(σj,1 ,..., σj,d ), respectively. Then Ai − Aj =→→, Σ + Σ ) [18]. Let P r(o , o , D) denotes the probN (−
µ −−
µ
j

i

j

i

j

ability that oj ∈ DN (oi ). Then,∫→→→, Σ + Σ )d−P r(oi , oj , D) = N (−µi − −
µ
A ,
j
i
j

(1)

R

→
→) and radius D. Here
where R is a sphere with centre (−µi − −µ
j
we only give the 2-dimensional expression for P r(oi , oj , D).
However, the expressions for higher dimensional cases canbe obtained using Eq. 1. Let oi and oj be two 2-dimensional
−
→
−
→
→
uncertain objects with attributes A ∼ N (−µ , Σ ) and A ∼
i

i

i

j

→, Σ ), where −→→ = (µ , µ )T ,N (−µµi = (µi,1 , µi,2 )T , −
µ
j
j
j
j,1
j,2

2
2
2
2
Σi = diag(σi,1, σi,2) and Σj = diag(σj,1, σj,2). Assumingthat σi,1 = σj,1 = σi,2 = σj,2 = σ, P r(oi , oj , D) is given as
follows.

Min distance
between % and .7

1
P r(oi , oj , D) =
4πσ 2
(
)
∫ D ∫ 2π(2)
−1 ( 22)exp
r − 2αr cos θ + α
r dθ dr.
24σ00where α2 = α12 +α22 and α1 = µi,1 −µj,1 and α2 = µi,2 −µj,2 .

& E Pê

.5 %- áåá Ï.6

For the proof of Eq. 2, please refer to our previous work [16].

.7Note that P r(oi , oj , D) only depends on α2 but not on coordinates of oi and oj . Hence we can denote P r(oi , oj , D)

4½>ç :%;

Figure 1: Cell Layers and Bounds Region

by P r(α, D) when there is no confusion. Computing thisprobability is usually very costly, and we have to avoid thiscomputation as much as possible.

4. Naive Approach

Lemma 1. Let oi , oj ∈ GDB be two d-dimensional uncertain objects following Gaussian distribution and α denotes
the ordinary Euclidean distance between the means of oi and

The Naive approach of the top-k outlier detection given in
Alg. 1 uses Nested-loop. The approach includes the evaluation of the distance function between each object oi ∈ GDB
and every other object in the GDB until oi can be decided
as a top-k outlier or inlier. In the worst case this approachoj . Then for t ∈ R, denoting the number of standard deviations required to enclose a large probability (say > 99%) ofa d-dimensional Gaussian distribution, the following statements hold.
(a) If α <= D − tσ, P r(oi , oj , D) ≈ 1.

2

requires the evaluation of O(N ) distance functions. Usually
it is very expensive.

(b) If α >= D + tσ, P r(oi , oj , D) ≈ 0.
Proof. The number of standard deviations s needed to

Algorithm 1 The top-k Naive Approach
Input: GDB, D, k

enclose a given probability for a d-dimensional random vari-

2: Cobj ← ϕ (Sorted list of candidate top-k outliers);

able X following Gaussian distribution can be obtained us< s} = Gd (s2 ) [?], where
ing the expression
P r{dM (X, µ) =√∑−1
dM (X, µ) =(X − µ)T(X − µ) is the Mahalanobis

3: for each oi in GDB do

distance and Gd (s2 ) is the CDF of the chi-squared distri-Output: Top-k Distance-based Outliers
1: N ← |GDB|, θ ← ∞;4:

EN (oi ) ← 0; (expected number of D-neighbours of oi )bution with d-degrees of freedom.

5:for each oj in GDB do

Hence if t denotes the value of s, such that P r{dM (X, µ) <
= t}

6:

EN (oi )+ = P r(oi , oj , D);

7:

if EN (oi ) > θ then GOTO next oi ;8:

end for

9:Insert oi and EN (oi ) into Cobj (Cobj is sorted in ascendingorder w.r.t. EN (oi ));10:

if |Cobj | > k then11:

Set θ = EN (o′ ), where o′ is the kth object in Cobj ;12:Remove all o′′ ∈ Cobj , such that EN (o′′ ) > θ;13:

end if

14: end for
15: return Cobj ;covers a large area of Gaussian distribution (say > 99%),
then for α <= D − tσ, P r(oi , oj , D) ≈ 1 and for α >= D+
tσ, P r(oi , oj , D) ≈ 0
5. 1 Structure
In order to ﬁnd the top-k distance-based outliers from an
uncertain dataset using PC-list, we ﬁrst quantize each object o ∈ GDB, to a d-dimensional space that is partitioned
into cells of length l (The cell length is discussed in Sec.
5. 3). Let Cψ1 ,...,ψd be any cell in grid G, where positive integers ψ1 , ..., ψd denote the cell indices. The layers (L1 , ..., Ln )of Cψ1 ,...,ψd ∈ G are the neighbouring cells of Cψ1 ,...,ψd , as

5. The Populated-Cells List (PC-list)

shown in Fig. 1 and are deﬁned as follows.

The Naive approach requires a lot of computation time to

L1 (Cψ1 ,...,ψd ) ={Cx1 ,...,xd |x1 = ψ1 ± 1, ..., xd = ψd ± 1,

detect top-k outliers even from a small dataset due to theCx1 ,...,xd =| Cψ1 ,...,ψd } .

costly distance calculation. To overcome this problem wepropose a PC-list-based approach of top-k outlier detection.

L2 (Cψ1 ,...,ψd ) = {Cx1 ,...,xd |x1 = ψ1 ± 2, ..., xd = ψd ± 2,

PC-list is an array of non-empty cells of a d-dimensional| Cψ1 ,...,ψd } .
Cx1 ,...,xd ∈/ L1 (Cψ1 ,...,ψd ), Cx1 ,...,xd =grid containing uncertain data objects o ∈ GDB. The PC-

L3 (Cψ1 ,...,ψd ), ..., Ln (Cψ1 ,...,ψd ) are deﬁned in a simi-

list helps in the detection of top-k distance-based outliers by

lar way.

identifying the cells containing candidate outliers.

there is no confusion. Let RD−tσ (C) denotes the re⌊⌋√gion formed by D−tσ−
1neighbouring layers of C ∈l d

We will use C to denote Cψ1 ,...,ψd when

G.

Then PC-list (P C) is a table containing a tuple(ψ1 , ..., ψd , C(C), CD−tσ (C)), denoted by ti (0 < i <= |PC|),and maximum ordinary Euclidean distances between cells

for each non-empty cell C ∈ G as shown in Fig.2. Here,the position of cells Ctp and Ctq in the grid G and can beψ1 , ..., ψd are the indices of C, C(C) is the object count of C,

deﬁned as follows.

Ctp and Ctq respectively. Distance between cells depend on

and CD−tσ (C) is the object count within cells in RD−tσ (C)(including C itself).

The region RD−tσ (C) is chosen insuch a way that for each oi ∈ C and oj ∈ RD−tσ (C),P r(oi , oj , D) ≈ 1. The tuples in the PC-list are sorted in theascending order of CD−tσ (C) column. The idea behind sorting is that outliers tend to exist in sparse region rather thandense regions. Sorting tuples in the PC-list, lets us identify
and process cells in sparse regions before dense regions andmakes pruning eﬀective. Since each ti ∈ P C corresponds toa cell C ∈ G, we will use Cti to denote the cell referred bytuple ti .

d∑2∆min (Ctp , Ctq ) = l ∗ (δmin,s
)1/2
s=1



ψps − (ψqs + 1)
where δmin,s = (ψps + 1) − ψqsψps − ψqs

4
0

ð6
1 2 3
0

1

2 3
ð5

4

ÒÚ

ÒÛ

Ý:o;

p?šÌ :o;

1

2

2

7

1

1

1

10

3

2

1

10

2

2

2

13

3

0

3

13

2

0

3

14

3

1

5

16

2

1

2

19

Figure 2: PC-list buildingψps < ψqs
ψps = ψqs

d
∑
2
)1/2
∆max (Ctp , Ctq ) = l ∗ (δmax,ss=1(ψps + 1) − ψqs
where δmax,s =ψ − (ψ + 1)
ps

4½?ç :%5á6 ;ψps > ψqs

qs

ψps >
= ψqs
ψps < ψqs

Now we can obtain bounds for cells in PC-list using precomputed P r(α, D) values and the information available in
PC-list. Let LB(P r(Ctp , Ctq )) and U B(P r(Ctp , Ctq )) denote the P r(α, D) values at minimum α >= ∆max (Ctp , Ctq )and maximum α <= ∆min (Ctp , Ctq ) respectively. Then for∑′′
Cti ∈ P C, LB(Cti ) = ( C ′ ∈P C LB(P r(Cti , Cti)) ∗ C(Cti
))
ti
∑
′
′
and U B(Cti ) = ( C ′ ∈P C U B(P r(Cti , Cti )) ∗ C(Cti )).
ti⌈⌉
Let RD+tσ (C) denotes a region formed by D+tσ
neighlbouring layers of cell C ∈ G as shown in Fig. 1. Region
RD+tσ (C) is chosen in such a way that for each oi ∈ C and5. 2 Cell Bounds

oj ∈/ RD+tσ (C), P r(oi , oj , D) approaches zero. Since the ma-

In order to identify cells Cti ∈ P C, containing only in-

jor contribution in the bounds for C ∈ G is done by the cells

liers or candidate top-k outliers, their bounds on the ex-in region RD+tσ (C), we redeﬁne the bounds for Cti ∈ P C,

pected number of D-neighbours are useful. A cell Cti canto reduce the number of pre-computations and bounds com-be pruned as an inlier cell if the minimum expected num-

putation time, as follows.

ber of D-neighbours for any object in cell Cti is greaterthan threshold θ (θ is discussed later in this section). Similarly a cell can be identiﬁed as containing top-k outliers if
the maximum expected number of D-neighbours for any object in Cti is less than θ. Since the Gaussian distribution
is unbounded, P r(oi , oj , D) is always greater than zero for
oi , oj ∈ G. Therefore all the cells in PC-list need to be considered for the computation of bounds of Cti ∈ P C. Since
our distance function depends only on α, that is, the distance between the means of two objects rather than their coordinates, we need to compute distance between cells in PClist in order to compute their bounds. Beside distance between cells, pre-computed P r(α, D) values and object countof each Cti ∈ P C are also required for the computation of
Cti ∈ P C bounds.

∑

LB(Cti ) =′′LB(P r(Cti , Cti)) ∗ C(Cti).

′ ∈{P C∩R
Cti
D+tσ (Cti )}∑U B(Cti ) =′′U B(P r(Cti , Cti)) ∗ C(Cti)′ ∈{P C∩R
Cti
D+tσ (Cti )}+ P r(α′ , D) ∗ (N −

∑

′
C(Cti
).

′ ∈{P C∩R
Cti
D+tσ (Cti )}where α′ = D + tσ, for cell objects that lie greater thanD + tσ distance from the target cell Cti .
Number of Pre-computations:

Since we computebounds using the cells in region RD+tσ (C), P r(α, D) values need to be computed only for the neighbouring layers
within D + tσ distance of any cell. For ⌈ D+tσ
⌉ neighbourl
ing layers, we require 2⌈ D+tσ
⌉ pre-computations. Two morelpre-computations are required for the cell C itself and theDistance between Cells: Let Ctp and Ctq are two cells

objects that lie greater than D + tσ distance of any cell.

in P C with indices ψp1 , ..., ψpd and ψq1 , ..., ψqd respectively.

Hence the total number of pre-computations required are

Let ∆min (Ctp , Ctq ) and ∆max (Ctp , Ctq ) denote the minimum

only 2⌈ D+tσ
⌉ + 2.
l5. 3 Candidate Outlier Cells

Algorithm 2 The Top-k Distance-based Outliers

The bounds are computed for each Cti ∈ P C, in order

Input: GDB, D, l, k

to prune inlier cells or identify outlier cells. A threshold is

Output: Top-k Distance-based Outliers

required to decide whether a Cti ∈ P C is inlier or outlier

1: N ← |GDB|, θ ← ∞;depending upon their bounds. The deﬁnition of thresholdrequires an attribute of candidate outlier cells table, hence
we deﬁne candidate outlier cells table ﬁrst.
Let Ccell denotes a table containing tuples of the form
(ψ1 , ..., ψd , C(Ctj ), LB(Ctj ), U B(Ctj )), denoted by tj (0 <j <= |Ccell |), for each candidate outlier cell in PC-list. LetkCtj∈ Ccell be a cell containing the kth object. The tuples

in Ccell are sorted in ascending order of the U B(Ctj ) attribute. A Cti ∈ P C is a candidate outlier cell whenever∑k<Ctj ∈Ccell C(Ctj ) < k or LB(Cti ) = θ, where θ = U B(Ctj )denotes the threshold.
Cell Pruning and θ Updation:

For Cti ∈ P C, if

LB(Cti ) > θ, Cti cannot contain any of the top-k outliersand can be pruned. On the other hand, if LB(Cti ) <= θ,
Cti may contain top-k outlier. We add Cti to Ccell , suchthat Ccell remain sorted of U B(Ctj ) attribute. Moreover if

2: Ccell ← ϕ; (Candidate outlier cells list)
3: Cobj ← ϕ; (Candidate outlier objects list)
4: Create cell grid G depending upon dataset values and cell

length l;
5: Map each o ∈ GDB to an appropriate cell C ∈ G;
6: Create PC-list P C, using non-empty cells of G;
7: Sort P C w.r.t. CD−tσ (C) column;/*Searching candidate outlier cells*/
8: for each Cti in |P C| do
9:

if CD−tσ (Cti ) ∗ P r(D − tα, D) > θ then Exit for loop.

10:Compute LB(Cti ) and U B(Cti );if LB(Cti ) <= θ then

11:
12:
13:

Add Cti to Ccell ; (keep Ccell sorted of U B(Ctj ))if Ccell contains >= k objects then14:k ), such that C k contain the k th object;Set θ = U B(Ctjtj

15:

Remove all Ctj from Ccell , such that LB(Ctj ) > θ;

16:
17:

end ifend if

18: end fork
U B(Cti ) < θ, add Cti to Ccell , set θ = U B(Ctj) and remove/*Calculating EN (o) of candidate top-k outliers*/′′
Ctjfrom Ccell , such that LB(Ctj) > θ, as they cannot con-

The computation of EN (o) is similar to that of Naive approachtain the top-k outliers.

in Algorithm 1. The only diﬀerence is that in this algorithm
we compute EN (o) for the candidate objects in Ccell only.

Stopping Condition: The PC-list is scanned from top tobottom for candidate outlier cells. During the scanning, if
′
′
a Cti
∈ P C is found such that P r(α, D) ∗ CD−tσ (Cti) > θ,′
where α = D − tσ, neither Cti
nor any cell after it in PC-list

can contain outliers. Hence the scanning can be stopped at

In order to do so, exact expected D-neighbours EN (o) of objects in candidate cells are calculated. The object o is thenadded to the Cobj (set of candidate outlier objects) along

this position.

with its EN (o). The objects in Cobj are sorted with respect
to EN (o). As the kth object’s EN (o) is found, threshold θ

Cell Length l: Due to the complexity of our distance func-

is updated (refer line 11 of Alg.1). During the calculation oftion, it is not possible to derive a single cell length l suit-

EN (o), if for some o′ , EN (o′ ) becomes greater than θ, thenable for all the combinations of D and variances. Very smallo′ can not be among top-k outliers and can be removed fromcell length increases the number of cells in the Grid expo-

further consideration.

nentially and the time required to construct the PC-list. A
good starting point of the cell length that we found throughexperiments is the standard deviation, i.e., l = σ.

6. Experiments

5. 4 Outlier Detection Algorithms
In this section, we present a top-k distance-based outlier
detection algorithm on uncertain dataset. The algorithm 2
ﬁrst maps dataset objects to appropriate grid cells and create PC-list in lines 4 and 5 respectively. Since the PC-list is
sorted in ascending order of its CD−tσ (Cti ) column, it guarantees that the cells in sparse region of G are at the top of
the PC-list. Hence candidate outlier cells are expected to
be at the top of the list. We scan the PC-list and add candidate outlier cells in Ccell until the stopping condition online 8 becomes true. The number of objects in CCell may begreater than k, hence additional objects need to be removed.

We conducted extensive experiments on synthetic datasetsto evaluate the eﬀectiveness and accuracy of our proposed
algorithm. The algorithm is implemented in C++, GNU
compiler. All experiments are performed on a system withan Intel Core 2 Duo, E8400 3.00GHz CPU and 2GB main
memory running Ubuntu 12.04 OS. All programs run in main
memory and no I/O cost is considered.
We use two synthetic datasets for our experiments: unimodal Gaussian (UG) and trimodal Gaussian (TG). UG
and TG are 2-dimensional and are generated using BoxMuller method [17]. A shorthand notation “DatasetN ame+
DatasetSize′′ (e.g. UG5k to denote 5,000 tuples of unimodal

1E+03
1E+02

30%

80%

Percentage

1E+04

60%
40%

25%
20%

15%
10%

1E+01
20%

1E+00
5000

10000

15000

Naive

7.35%

5%
0%

0%

Dataset Size

32.87%

35%

99.67%

99.83%

100%

1E+05

Percentage

Execution Time(s)

1E+06

UG10k

Top-k

TG10k

UG10k

(a) Naive vs. PC-list(b) Pruning Percentage

TG10k

DatasetDataset(c) Stopping Condition

Figure 3

Gaussian dataset) is used in ﬁgures.

compares the execution times of the Naive and the proposed

All the datasets are normalized to have a domain ofalgorithm on UG dataset. Our proposed algorithm is sev-

[0,1000] on every dimension. For each point z in any dataset,eral times faster than its Naive counterpart due to its strong

we create an uncertain object o, whose uncertainty is given

pruning capability as can be observed from Fig.3b. Stopping

by Gaussian distribution with mean z and standard devia-

condition discussed in Sec.5. 3 helps identify candidate out-tion σ in all the dimensions. Unless speciﬁed, the following

lier cells very quickly. Fig.3c shows the percentage of cells

parameter values are used: D = 100, σ = 10, l = 10 andconsidered in the PC-list to identify candidate outlier cells

k = 0.1% of the respective dataset size. Pre-computation

before the execution of stopping condition. The percentage istime is not included in the measurements.

comparatively higher for trimodal Gaussian dataset because
the dataset is relatively sparse and hence results in larger

20000

UG5k
UG10k
UG15k

10000
8000

Execution Time(s)Execution Time(s)

12000

6000
4000

2000
0
0.5

1

5

10

eters on the execution times. It is obvious from the graphs

5000

in Figs. 4a and 4b that smaller cell lengths require lower ex-

0

15

0.5

1

5

10

15

Cell Length(a) UG Vary l(b) TG Vary l

UG5k
UG10k
UG15k

time of the algorithm. On the other hand, large cell length
decreases the pruning eﬀect and hence increases the execu-

10000

TG5k
TG10k
TG15k

8000
6000

tion time of our algorithm. Therefore we recommend the use

4000

of cell length equal to the standard deviation as discussed in

2000

0
5

10

ecution times. However very small cell length increases thenumber of cells exponentially and therefore the execution

12000

Execution Time(s)Execution Time(s)Graphs in Fig.4 show the eﬀect of varying diﬀerent param-

10000

Cell Length

8000
7000
6000
5000
4000
3000
2000
1000
0

number of candidate outlier cells.

TG5k
TG10k
TG15k

15000

15

5

10

Sigma

15

Sigma

(c) UG Vary σ

Sec. 5. 3.
From Figs. 4c, 4d, 4e and 4f we can observe that our al-(d) TG Vary σ

9000
8000
7000
6000
5000
4000
3000
2000
1000
0

12000

Execution Time(s)Execution Time(s)gorithm is quite consistent and its performance is not much
UG5k
UG10k
UG15k

aﬀected by the variation in parameters σ and D.

10000
8000
6000

TG5k
TG10k
TG15k

Next we perform experiments by varying parameter k.
Figs. 4g and 4h show that increase in k results in increase

4000
2000
0

75

100

125

75

100

D

125

D

(e) UG Vary D

in execution time of algorithm, which is quite obvious behaviour of our algorithm.

(f) TG Vary D

7. Conclusion and Future Work
15000

35000

UG5k
UG10k
UG15k

Execution Time(s)Execution Time(s)

20000

10000

5000

30000

25000

TG5k
TG10k
TG15k

In this work, we propose a top-k distance-based outlier

20000

detection approach on uncertain datasets of Gaussian dis-

15000

10000
5000

tribution based on PC-list. Sorted PC-list helps identify

000.001*N

0.002*N

0.003*N

0.001*N

0.002*N(g) UG Vary k

0.003*Nkk(h) TG Vary k

Figure 4: Varying l, σ, D and kcandidate outlier objects very quickly without considering
all the objects in the dataset. An extensive empirical study
demonstrate the eﬃciency and scalability of our proposed
approach.

We ﬁrst conduct experiments to evaluate the eﬃciency ofour proposed top-k algorithm presented in Sec.5. 4. Fig. 3a

Acknowledgement
This work has been partly supported by Grant-in-Aid forScientiﬁc Research(A)(#24240015A).
Refereces[1] Hawkins D., ”Identi?cation of Outliers”, Chapman andHall, 1980.
[2] Barnett V., Lewis T., ”Outliers in Statistical Data”, John
Wiley, 1994.
[3] Edwin M. Knorr , Raymond T. Ng , Vladimir Tucakov.:”Distance-Based Outliers: Algorithms and Applications”,
The VLDB Journal, 2000.
[4] H.Nguyen, V.Gopalkrishnan, and I.Assent.: “An unbiased distance-based outlier detection approach for highdimensional data”, DASFAA, 2011.
[5] M.Kontaki, A.Gounaris, A.N.Papadopoulos, K.Tsichlas,
and Y.Manolopoulos.: “Continuous monitoring of distancebased outliers over data streams”, ICDE, 2011.
[6] A.B.Sharma, L.Golubchik, R. Govindan.: “Sensor faults:
Detection methods and prevalence in real-world datasets”,
ACM Transactions on Sensor Networks, Vol. 6, No. 3., June
2010.
[7] Helm I., Jalukse L., Leito I.: Measurement Uncertainty Estimation in Amperometric Sensors: A Tutorial Review. Sensors 2010.
[8] Diao, Y., Li, B., Liu, A., Peng, L., Sutton, C., Tran, T.,
Zink, M.: Capturing Data Uncertainty in High-Volume
Stream Processing., CIDR, 2009.
[9] Sridhar Ramaswamy , Rajeev Rastogi , Kyuseok Shim.:”Eﬃcient Algorithms for Mining Outliers from Large Data
Sets”, ACM, SIGMOD, 2000.
[10] Fabrizio Angiulli and Clara Pizzuti.: “Fast Outlier Detection in High Dimensional Spaces”, PKDD, 2002.
[11] Fabrizio Angiulli and Fabio Fassetti.: “Detecting distancebased outliers in streams of data”, CIKM, 2007.
[12] Sabbas Burdakis, Antonios Deligiannakis,: ”Detecting Outliers in Sensor Networks Using the Geometric Approach”,
ICDE, 2012.
[13] Aggarwal, C.C., Yu, P.S.: ”Outlier Detection with Uncertain Data”, SDM, 2008.
[14] Bin Wang, Gang Xiao, Hao Yu and Xiaochun Yang.:”Distance-Based Outlier Detection on Uncertain Data”, ICCIT, 2009.
[15] B.Wang, X.Yang, G.Wang, and G.Yu.: “Outlier detection
over sliding windows for probabilistic data streams”, Journal of Comp. Sc.& Tech., 25(3), 2010.
[16] Salman Ahmed Shaikh and Hiroyuki Kitagawa,: ”Distancebased Outlier Detection on Uncertain Data of Gaussian Distribution”, APWeb, 2012.
[17] W.Thistleton, J.A.Marsh, K.Nelson and C.Tsallis, Generalized Box-Muller method for generating q-Gaussian random
deviates, IEEE Trans. on Info. Theory, 2007.
[18] Weisstein, Eric W.:”Normal Diﬀerence Distribution”, From
MathWorld. http://mathworld.wolfram.com.