Detecting graph-based spatial outliers.
of outliers can lead to the discovery of unexpected, interesting, and useful knowledge. Existing methods are designed for detecting spatial outliers in multidimensional geometric data sets, where a distance metric is available. In this paper, we focus on detecting spatial outliers in graph structured data sets. We define statistical tests, analyze the statistical foundation underlying our approach, design several fast algorithms to detect spatial outliers, and provide a cost model for outlier detection procedures. In addition, we provide experimental results from the application of our algorithms on a Minneapolis-St.Paul(Twin Cities) traffic dataset to show their effectiveness and usefulness.
Introduction
Data mining is a process to extract nontrivial, previously unknown and potentially useful infor-
mation(such as knowledge rules, constraints, regularities) from data in databases [11, 4]. The
explosive growth in data and databases used in business management, government administra-
tion, and scientific data analysis has created a need for tools that can automatically transform
the processed data into useful information and knowledge. Spatial data mining is a process of
discovering interesting and useful but implicit spatial patterns. With the enormous amounts of
spatial data obtained from satellite images, medical images, GIS, etc., it is a nontrivial task for
humans to explore spatial data in detail. Spatial data sets and patterns are abundant in many
application domains related to NASA, the National Imagery and Mapping Agency(NIMA), the
National Cancer Institute(NCI), and the Unite States Department of Transportation(USDOT).
Data Mining tasks can be classified into four general categories: (a) dependency detection
(e.g., association rules) (b) class identification (e.g., classification, clustering) (c) class description
(e.g., concept generalization), and (d) exception/outlier detection [9]. The objective of the
first three categories is to identify patterns or rules from a significant portion of a data set.
On the other hand, the outlier detection problem focuses on the identification of a very small
subset of data objects often viewed as noises, errors, exceptions, or deviations. Outliers have
been informally defined as observations which appear to be inconsistent with the remainder of
that set of data [2], or which deviate so much from other observations so as to arouse suspicions
that they were generated by a different mechanism [6]. The identification of outliers can lead to
the discovery of unexpected knowledge and has a number of practical applications in areas such
as credit card fraud, the performance analysis of athletes, voting irregularities, bankruptcy, and
weather prediction.
Outliers in a spatial data set can be classified into three categories: set-based outliers, multi-dimensional
space-based outliers, and graph-based outliers. A set-based outlier is a data object
whose attributes are inconsistent with attribute values of other objects in a given data set regardless
of spatial relationships. Both multi-dimensional space-based outliers and graph-based
outliers are spatial outliers, that is, data objects that are significantly different in attribute values
from the collection of data objects among spatial neighborhoods. However, multi-dimension
space-based outliers and graph-based outliers are based on different spatial neighborhood defini-
tions. In multi-dimensional space-based outlier detection, the definition of spatial neighborhood
is based on Euclidean distance, while in graph-based spatial outlier detections, the definition is
based on graph connectivity.
Many spatial outlier detection algorithms have been recently proposed; however, spatial
outlier detection remains challenging for various reasons. First, the choice of a neighborhood
is nontrivial. Second,the design of statistical tests for spatial outliers needs to account for the
distribution of the attribute values at various locations as well as the aggregate distribution
of attribute values over the neighborhoods. In addition, the computation cost of determining
parameters for a neighborhood-based test can be high due to the possibility of join computations
In this paper, we formulate a general framework for detecting outliers in spatial graph data
sets, and propose an efficient graph-based outlier detection algorithm. We provide cost models
for outlier detection queries, and compare underlying data storage and clustering methods
that facilitate outlier query processing. We also use our basic algorithm to detect spatial
and temporal outliers in a Minneapolis-St.Paul(Twin Cities) traffic data set, and show the
correctness and effectiveness of our approach.
1.1 An Illustrative Application Domain: Traffic Data Set
In 1995, the University of Minnesota and the Traffic Management Center(TMC) Freeway Operations
group started the development of a database to archive sensor network measurements
from the freeway system in the Twin Cities. The sensor network includes about nine hundred
stations, each of which contains one to four loop detectors, depending on the number of lanes.
Sensors embedded in the freeways monitor the occupancy and volume of traffic on the road.
At regular intervals, this information is sent to the Traffic Management Center for operational
purposes, e.g., ramp meter control, and research on traffic modeling and experiments. Figure 1
shows a map of the stations on highways within the Twin-Cities metropolitan area, where each
polygon represents one station. Interstate freeways include I-35W, I35E, I-94, I-394, I-494, and
I-694. State trunk highways include TH-100, TH-169, TH-212, TH-252, TH-5, TH-55, TH-62,
TH-65, and TH-77. I-494 and I-694 together forming a ring around the Twin Cities. I-94 passes
from East to North-West, while I-35W and I-35E run in a North-South direction. Downtown
Minneapolis is located at the intersection of I-94, I-394, and I-35W, and downtown Saint Paul
is located at the intersection of I-35E and I-94.
I-
I-
I-
I-
I-
I-
I-
I-
I-
I-3

Figure

1: Detector map in station level

Figure

2(a) demonstrates the relationship between a station and its encompassing detectors.
For each station, there is one detector installed in each lane. The traffic flow information
measured by each detector can then be aggregated to the station level. Figure 2(b) shows the
three basic data tables for the traffic data. The station table stores the geographical location
and some related attributes for each station. The relationship between each detector and its
corresponding station is captured in the detector table. The value table records all the volume
and occupancy information within each 5-minute time slot at each particular station.
Detector 50
Detector 51
Detector 52
Station 20
(a) Relationship between detectors
and stations2
Detector Station1
Detector Table
Time
Detector Volume Occupancy260 12Value

Table

Polygon
Boundary
(3,5),(4,10),.
(5,7),(6,4),.
Station Location
26th St.
28th St.
Freeway
Direction
Q4
Q4
Station Table
Zone
(b) Three basic tables

Figure

2: Detector-station Relationship and Basic Tables
In this application, each station exhibits both graph and attribute properties. The topological
space is the map, where each station represents a node and the connection between each
station and its surrounding stations can be represented as an edge. The attribute space for
each station is the traffic flow information (e.g., volume, occupancy) stored in the value table.
In this application, we are interested in discovering the location of stations whose measurements
are inconsistent with those of their graph-based spatial neighbors and the time periods
when those abnormalities arise. This outlier detection task is to:
ffl Build a statistical model for a spatial data set
ffl Check whether a specific station is an outlier
ffl Check whether stations on a route are outliers
We use three neighborhood definitions in this application as shown in Figure 3. First, we
define a neighborhood based on spatial graph connectivity as a spatial graph neighborhood. In

Figure

are the spatial neighbors of (s are connected to
s 2 in a spatial graph. Second, we define a neighborhood based on time series as a temporal
neighborhood. In Figure 3, (s are the temporal neighbors of (s
t 3 are consecutive time slots. In addition, we define a neighborhood based on both space and
time series as a spatial-temporal neighborhood. In Figure 3, (s
are the spatial-temporal neighbors of (s
are connected to s 2 in a spatial graph, and t 1 , t 2 , and t 3 are consecutive time slots.
1.2 Problem Formulation
In this section, we formally define the spatial outlier detection problem. Given a spatial frame-work
S for the underlying spatial graph G, an attribute f over S, and neighborhood relationship
R, we can build a model and construct statistical tests for spatial outliers based on a spatial
graph according to the given confidence level threshold. The problem is formally defined as
follows.
Spatial Outlier Detection Problem
Given:
ffl A spatial graph is a spatial framework consisting of locations
Temporal
Neighborhood
Spatial-Temporal
Neighborhood
Time
Space
Legend
Neighbors
Spatial
Temporal
Neighbors
Additional Neighbors
in Spatial-Temporal
Neighborhood
Spatial-Temporal
Window of
Neighborhood
Neighborhood

Figure

3: Spatial and Temporal outlier in traffic data
\Theta S) is a collection of edges between locations in S.
ffl A neighborhood relationship R ' S \Theta S consistent with E
ffl An attribute function f a set of real numbers
ffl An aggregate function f aggr : R N ! a set of real numbers to summarize values of
attribute f over a neighborhood relationship R N ' R
ffl Confidence level threshold '
Find: A set O of spatial outliers O
Objective:
ffl Correctness: outliers identified by a method have significantly different
attribute values with those of their neighborhood
ffl Efficiency: to minimize the computation time
Constraints:
ffl Attribute values for different locations in S have a normal distribution
ffl The size of the data set is much greater than the main memory size
ffl The range of attribute function f is the set of real numbers
The formulation shows two subtasks in this spatial outlier detection problem: (a) the design
of a statistical model M and a test for spatial outliers (b) the design of an efficient computation
method to estimate parameters of the test, test whether a specific spatial location is an outlier,
and test whether spatial locations on a given path are outliers.
1.3 Paper Scope and Outline
This paper focuses on graph-based spatial outlier detection using a single attribute. Outlier
detection in a multi-dimensional space using multiple attributes is outside the scope of this
paper.
The rest of the paper is organized as follows. Section 2 reviews related work and discusses our
contributions. In Section 3, we propose our graph-based spatial outlier detection algorithm and
discuss its computational complexity. The cost models for different outlier query processing
are analyzed in Section 4. Section 5 presents our experimental design. The experimental
observation and results are shown in Section 6. We summarize our work in Section 7.
Related Work and Our Contribution
Many outlier detection algorithms [1, 2, 3, 8, 9, 12, 14, 16] have been recently proposed. As
shown in Figure 4, these methods can be broadly classified into two categories, namely set-based
outlier detection methods and spatial-set-based outlier detection methods. The set-based outlier
detection algorithms [2, 7] consider the statistical distribution of attribute values, ignoring the
spatial relationships among items. Numerous outlier detection tests, known as discordancy
tests [2, 7], have been developed for different circumstances, depending on the data distribution,
the number of expected outliers, and the types of expected outliers. The main idea is to fit the
data set to a known standard distribution, and develop a test based on distribution properties.
Outlier Detection Methods
Distance-based
Wavelet
Depth threshold
Distance to k-th
Neighbor
Density in
Neighborhood
Multi-dimensional
metric spatial data set
Graph-based
spatial data set
attribute value
Statistical
distribution of
based Spatial set based
based
Spatial Graph
Detection
Based Outlier

Figure

4: Classification of outlier detection methods
Spatial-set-based outlier detection methods consider both attribute values and spatial rela-
tionships. They can be further grouped into two categories, namely multi-dimensional metric
space-based methods and graph-based methods. The multi-dimensional metric space-based
methods model data sets as a collection of points in a multidimensional space, and provide
tests based on concepts such as distance, density, convex-hull depth. We discuss different example
tests now. Knorr and Ng presented the notion of distance-based outliers [8, 9]. For a
dimensional data set T with N objects; an object O in T is a DB(p;D)-outlier if at least
a fraction p of the objects in T lies greater than distance D from O. Ramaswamy et al. [13]
proposed a formulation for distance-based outliers based on the distance of a point from its
th nearest neighbor. After ranking points by the distance to its k th nearest neighbor, the top
n points are declared as outliers. Breunig et al. [3] introduced the notion of a "local" outlier
where the outlier-degree of an object is determined by taking into account the clustering structure
in a bounded neighborhood of the object, e.g., k nearest neighbors. They formally defined
the outlier factor to capture this relative degree of isolation or outlierness. Their notions of
outliers are based on the same theoretical foundation as density-based cluster analysis [1]. In
computational geometry, some depth-based approaches [14, 12] organize data objects in convex
hull layers in data space according to their peeling depth [12], and outliers are expected to be
found from data objects with a shallow depth value. Conceptually, depth-based outlier detection
methods are capable of processing multidimensional datasets. However, with the best case
computational complexity of \Omega\Gamma N dk=2e ) for computing a convex hull, where N is the number of
objects and k is the dimensionality of the dataset, depth-based outlier detection methods may
not be applicable for high dimensional data sets. Yu et al. [16] introduced an outlier detection
approach, called FindOut, which identifies outliers by removing clusters from the original data.
Its key idea is to apply signal processing techniques to transform the space and find the dense
regions in the transformed space. The remaining objects in the non-dense regions are labeled
as outliers.
Methods for detecting outliers in multi-dimensional Euclidean space have some limitation.
First, multi-dimensional approaches assume that the data items are embedded in a isometric
metric space and do not capture the spatial graph structure. Consider the application domain
of traffic data analysis. A multi-dimensional method may put a detector station in the neighborhood
of another detector even if they are on opposite sides of the highway (e.g., I-35W north
bound at exit 230, and I-35W south bound at exit 230), leading to the potentially incorrect
identification of bad detector. Secondly, they do not exploit apriori information about the statistical
distribution of attribute data. Last, they seldom provide a confidence measure of the
discovered outliers.
In this paper, we formulate a general framework for detecting spatial outliers in a spatial data
set with an underlying graph structure. We define neighborhood-based statistics and validate
the statistical distribution. We then design a statistically correct test for discovering spatial
outliers, and develop a fast algorithm to estimate model parameters, as well as to determine
the results of a spatial outlier test on a given item. In addition, we evaluate our method in
Twin Cities traffic data set and show the effectiveness and usefulness of our approach.
3 Our Approach: Spatial Outlier Detection Algorithm
In this section, we list the key design decisions and propose an I/O efficient algorithm for spatial
graph based outliers.
3.1 Choice of Spatial Statistic
For spatial statistics, several parameters should be pre-determined before running the spatial
outlier test. First, the neighborhood can be selected based on a fixed cardinality or a fixed graph
distance or a fixed Euclidean distance. Second, the choice of neighborhood aggregate function
can be mean, variance, and auto-correlation. Third, the choice for comparing a location with
its neighbors can use either just a number or a vector of attribute values. Finally, the statistic
for base distribution can be selected from various choices.
The statistics we used are is the attribute value
for a data record x, N(x) is the fixed cardinality set of neighbors of x, and E y2N(x) (f(y)) is the
average attribute value for neighbors of x. Statistic S(x) denotes the difference of the attribute
value of each data object x and the average attribute value of x 0 s neighbors.
3.2 Characterizing the Distribution of the Statistic
normally distributed if attribute
value f(x) is normally distributed.
Proof:
Given the definition of neighborhood, for each data record x, the average attribute values
neighbors can be calculated. Since attribute values f(x) are normally
distributed and an average of normal variables is also normally distributed, the average attribute
values neighbors is also a normal distribution for a fixed cardinality
neighborhood.
Since the attribute value and the average attribute value over neighbors are two normal
variable, the distribution of the difference of S(x) of each data object x and the average
attribute value of x 0 s neighbors is also normally distributed. \Xi
3.3 Test for Outlier Detection
The test for detecting an outlier can be described as j S(x)\Gamma- s
oe s
For each data object x
with an attribute value f(x), the S(x) is the difference of the attribute value of data object x
and the average attribute value of its neighbors; - s is the mean value of all S(x), and oe s is the
standard deviation of all S(x). The choice of ' depends on the specified confidence interval.
For example, a confidence interval of 95 percent will lead to ' - 2.
3.4 Computation of Test Parameters
We now propose an I/O efficient algorithm to calculate the test parameters, e.g., mean and standard
deviation for the statistics, as shown in Algorithm 1. The computed mean and standard
deviation can then be used to detect the outlier in the incoming data set.
Given an attribute data set V and the connectivity graph G, the TPC algorithm first
retrieves the neighbor nodes from G for each data object x. It then computes the difference of
the attribute value of x and the average of the attribute values of x 0 s neighbor nodes. These
different values are then stored as a set in the AvgDist Set. Finally, the AvgDist Set is used to
get the distribution value - s and oe s . Note that the data objects are processed on a page basis
to reduce redundant I/O.
3.5 Computation of Test Results
The neighborhood aggregate statistics value, e.g., mean and standard deviation, computed in
the TPC algorithm can be used to verify the outliers in an incoming data set. The two verification
procedures are Route Outlier Detection(ROD) and Random Node Verification(RNV). The
Test Parameters Computation(TPC) Algorithm
Input: S is the multidimensional attribute space;
D is the attribute data set in S;
F is the distance function in
ND is the depth of neighbor;
E) is the spatial graph;
O i =Get One Object(i,D); /* Select each object from D */
NNS=Find Neighbor Nodes Set(O i ,ND,G);
Find neighbor nodes of O i from G */
Accum Dist=0;
O k =Get One Object(j,NNS); /* Select each object from NNS */
Accum Dist += F (O
Dist / jNNSj;
Add Element(AvgDist Set,i); /* Add the element to AvgDist Set */
Mean(AvgDist
Dev(AvgDist Set); /* Compute Standard Deviation */
return (- s ,oe s ).
Algorithm 1: Pseudo-code for test parameters computation
ROD procedure detects the spatial outliers from a user specified route, as shown in Algorithm 2.
The RNV procedure check the outlierness from a set of randomly generated nodes. Given route
RN in the data set D with graph structure G, the ROD algorithm first retrieves the neighboring
nodes from G for each data object x in the route RN , then it computes the difference
S(x) between the attribute value of x and the average of attribute values of x 0 s neighboring
nodes. Each S(x) can then be tested using the spatial outlier detection test j S(x)\Gamma- s
oe s
' is predetermined by the given confidence interval. The steps to detect outliers in both ROD
and RNV are similar, except that the RNV has no shared data access needs across tests for
different nodes. The I/O operations for Find Neighbor Nodes Set() in different iterations are
independent of each other in RNV. We note that the operation Find Neighbor Nodes Set() is
executed once in each iteration and dominates the I/O cost of the entire algorithm. The storage
of the data set should support the I/O efficient computation of this operation. We discuss the
choice for storage structure and provide an experimental comparison in Section 5 and 6.
The I/O cost of ROD and RNV are also dominated by the I/O cost of
Find Neighbor Nodes Set() operation.
Analytical Evaluation and Cost Models
In this section, we provide simple algebraic cost models for the I/O cost of outlier detection
operations, using the Connectivity Residue Ratio(CRR) measure of physical page clustering
methods. The CRR value is defined as follows.
Route Outlier Detection(ROD) Algorithm
Input: S is the multidimensional attribute space;
D is the attribute data set in S;
F is the distance function in
ND is the depth of neighbor;
E) is the spatial graph;
CI is the confidence interval;
are mean and standard deviation calculated in TPC;
RN is the set of node in a route;
Output: Outlier Set.
O i =Get One Object(i,D); /* Select each object from D */
NNS=Find Neighbor Nodes Set(O i ,ND,G);
Find neighbor nodes of O i from G */
Accum Dist=0;
O k =Get One Object(j,NNS); /* Select each object from NNS */
Accum Dist += F (O
oe s
/*Check the normal distribution table */
Check Normal Table(T value ,CI)== True)f
Add Element(Outlier Set,i); /* Add the element to Outlier Set */
return Outlier Set.
Algorithm 2: Pseudo-code for route outlier detection
number of unsplit edges
otal numbe of edges
The CRR value is determined by the page clustering method, the data record size, and
the page size. Figure 5 gives an example of CRR value calculation. The blocking factor, i.e.,
the number of data records within a page is three, and there are nine data records. The data
records are clustered into three pages. There are a total of nine edges and six unsplit edges.
The CRR value of this graph can be calculated as

Table

1 lists the symbols used to develop our cost formulas. ff is the CRR value. fi denotes
the blocking factor, which is the number of data records that can be stored in one memory
page.   is the average number of nodes in the neighbor list of a node. N is the total number
of node in the data set, L is the number of node along a route, and R is the number of nodes
randomly generated by users for spatial outlier verification.
Page B
Page C
Page A

Figure

5: Example of CRR
Symbol Meaning
ff The CRR value
Average blocking factor
Total number of nodes
L Number of nodes in a route
R Number of nodes in a random set
Average number of neighbors for each node

Table

1: Symbols used in Cost Analysis
4.1 Cost Modeling for Test Parameters Computation(TPC) Algorithm
The TPC algorithm is a nest loop index join. Suppose that we use two memory buffers. If one
memory buffer stores the data object x used in the outer loop and the other memory buffer is
reserved for processing the neighbors of x, we get the following cost function to estimate the
number number of page accesses.
The outer loop retrieves all the data records on a page basis, and has an aggregated cost
of N
fi . For each node x, on average, ff     neighbors are in the same page as x, and can be
processed without redundant I/O. Additional data page accesses are needed to retrieve the
other neighbors, and it takes at most (1 \Gamma ff)     data page accesses. Thus the
expected total cost for the inner loop is N
4.2 Cost Modeling for Route Outlier Detection(ROD) algorithm
We get the following cost function to estimate the number of page accesses with two memory
buffers for ROD algorithm. One memory buffer is reserved for processing the node x to be
verified, and the other is used to process the neighbors of x.
For each node x, on the average, its successor node y is on the same page as x with probability
ff, and can be processed with no redundant page accesses. The cost to access all the nodes
along a route is L   To process the neighbors of each node, ff     neighbors are on
the same page as x. Additional data page accesses are needed to retrieve the other
neighbors, and it takes at most (1 \Gamma ff)     data page accesses.
4.3 Cost Modeling for Random Node Verification(RNV) algorithm
We get the following cost function to estimate the number of page accesses with two memory
buffers for the RNV algorithm. One memory buffer is reserved for processing the node x to be
verified, the other is used to process the neighbors of x.
Since the memory buffer is assumed to be cleared for each consecutive random node, we
need R page accesses to process all these random nodes. For each node x, ff     neighbors are
on the same page as x, and can be processed without extra I/O. Additional data page accesses
are needed to retrieve the other neighbors, and it takes at most (1 \Gamma ff)     data page
accesses. Thus, the expected total cost to process the neighbor of R nodes is R
5 Experiment Design
In this section, we describe the layout of our experiments and then illustrate the candidate
clustering methods.
5.1 Experimental Layout
The design of our experiments is shown in Figure 6. Using the Twin Cities Highway Connectivity
Graph(TCHCG), we took data from the TCHCG and physically stored the data set into
data pages using different clustering strategies and page sizes. These data pages were then
processed to generate the global distribution or sampling distribution, depending on the size of
the data sets.
We compared different data page clustering schemes: CCAM
[15], Z-ordering [10], and Cell-tree [5]. Other parameters of interest were the size of the memory
buffer, the buffering strategies, the memory block size(page size), and the number of neighbors.
The measures of our experiments were the CRR values and I/O cost for each outlier detection
procedure.
Clustering
method
Page
Size
Sets of pages
of data
Sets of pages
of data
Highway
Connectivity
Graph
Twin-Cities
Buffering
Size
Buffer No of
Neighbors
Buffering strategy
No of neighbors
Buffer size
Z-order
Cell-tree
Test
Parameters
Test Parameters
Computation (TPC)
(Nest loop index join) CRR
I/O Cost
Route Outlier
Detection(ROD).
Verification (RNV).
Random Node

Figure

Experimental Layout
The experiments were conducted on many graphs. We present the results on a representative
graph, which is a spatial network with 990 nodes that represents the traffic detector stations for
a 20-square-mile section of the Twin Cities area. This data set is provided by the Minnesota
Dept. of Transportation(MnDot).
We used a common record type for all the clustering methods. Each record contains a node
and its neighbor-list, i.e., a successor-list and a predecessor-list. We also conducted performance
comparisons of the I/O cost for outlier-detection query processing.
5.2 Candidate Clustering Methods
In this section we describe the candidate clustering methods used in the experiments.
Connectivity-Clustered Access Method(CCAM): CCAM [15] clusters the nodes of
the graph via graph partitioning, e.g., Metis. Other graph-partitioning methods can also be
used as the basis of our scheme. In addition, an auxiliary secondary index is used to support
query operations. The choice of a secondary index can be tailored to the application. We used
the tree with Z-order in our experiments, since the benchmark graph was embedded in
graphical space. Other access methods such as the R-tree and Grid File can alternatively be
created on top of the data file, as secondary indices in CCAM to suit the application.
Linear Clustering by Z-order: Z-order [10] utilizes spatial information while imposing
a total order on the points. The Z-order of a coordinate (x,y) is computed by interweaving
the bits in the binary representation of the two values. Alternatively, Hilbert ordering may be
used. A conventional one-dimensional primary index (e.g. B + -tree) can be used to facilitate
the search.
Cell Tree: A cell tree [5] is a height-balanced tree. Each cell tree node corresponds, not
necessarily to a rectangular box, but to a convex polyhedron. A cell tree restricts polyhedra
to partitions of a BSP(Binary Space Partitioning), to avoid overlaps among sibling polyhedra.
Each cell tree node corresponds to one disk space, and the leaf nodes contain all the information
required to answer a given search query. The cell tree can be viewed as a combination of a
BSP- and R + -tree, or as a BSP-tree mapped on paged secondary memory.
6 Experimental Results
In this section, we illustrate the outlier examples detected in the traffic data set, present the
results of our experiments, and test the effectiveness of the different page clustering methods.
To simplify the comparison, the I/O cost represents the number of data pages accessed. This
represents the relative performance of the various methods for very large databases. For smaller
databases, the I/O cost associated with the indices should be measured. Here we present the
evaluation of I/O cost for the TPC algorithm. The evaluations of I/O cost for the RNV and
ROD algorithms are available in the full version paper.
6.1 Outliers Detected
We tested the effectiveness of our algorithm on the Twin Cities traffic data set and detected
numerous outliers, as described in the following examples.
Time
Volume
Traffic Volume v.s. Time for Station 138 on 1/12 1997
(a) Station 138
Volume
Traffic Volume v.s. Time for Station 139 on 1/12 1997
(b) Outlier Station 139
Time
Volume
Traffic Volume v.s. Time for Station 140 on 1/12 1997
(c) Station 140

Figure

7: Outlier station 139 and its neighbor stations on 1/12 1997
In

Figure

7, the abnormal station(Station 139) was detected with volume values significantly
inconsistent with the volume values of its neighboring stations 138 and 140. Note that our basic
algorithm detects outlier stations in each time slot; the detected outlier stations in each time
slot are then aggregated on a daily basis.4080120160Average Traffic Volume(Time v.s. Station)
Time
Station
ID(North
Bound)
(a) I-35W North
Bound2060100140Average Traffic Volume(Time v.s. Station)
Time
Station
ID(South
Bound)
(b) I-35W South
Bound

Figure

8: An example of outliers

Figure

8 shows another example of traffic flow outliers. Figures 8(a) and (b) are the traffic
volume maps for I-35W North Bound and South Bound, respectively, on 1/21/1997. The X-axis
is a 5-minute time slot for the whole day and the Y-axis is the label of the stations installed
on the highway, starting from 1 on the north end to 61 on the south end. The abnormal white
line at 2:45pm and the white rectangle from 8:20am to 10:00am on the X-axis and between
stations 29 to 34 on the Y-axis can be easily observed from both (a) and (b). The white line
at 2:45pm is an instance of temporal outliers, where the white rectangle is a spatial-temporal
outlier. Moreover, station 9 in Figure 8(a) exhibits inconsistent traffic flow compared with its
neighboring stations, and was detected as a spatial outlier.
6.2 Testing Statistical Assumption
In this traffic data set, the volume values of all stations at one moment are approximately a
normal distribution. The histogram of stations on different volumes are shown in Figure 9(a)
with a normal probability distribution superimposed. As can be seen in Figure 9(a), the normal
distribution approximates the volume distribution very well. We calculated the interval of
v and oe are the mean and standard
deviation of the volume distribution, and the percentages of measurements falling in the three
intervals are equal to 68.27%, 95.45%, and 99.73%, respectively. This pattern fits well with a
normal distribution since the expected values in a normal distribution are 68%, 95%, and 100%.
Moreover, we plot the normal probability plot in Figure9(b), and it appears linear. Hence the
volume values of all stations at the same time are approximately a normal distribution.
Given the definition of neighborhood, we then calculate the average volume value ( -
around its k neighbors according to topological relationship for each station. Since the volume
values are normally distributed, the average of the normal variables is also a normal distribution.
Volume Distribution at 10:00am on 1/15/1997
Volume Value
Number
of
Stations
(a) Histogram of traffic volume
distribution
Probability
Volume Normal Distribution Probability Plot at 10:00am on 1/15/1997
(b) Normal probability plot
for traffic volume distribu-
tion
4100Normalized Volume Difference over Spatial Neighborhood at 10:00am on 1/15/1997
Normalized Volume Difference over Spatial Neighborhood
Number
of
Stations
(c) Histogram of volume difference
over neighborhood

Figure

9: Verification of normal distribution for traffic volumes and volume difference over
neighbors
Since the volume values and the average volume values over neighborhoods are normally dis-
tributed, the difference(v \Gamma -
v) between these volumes and their corresponding average volume
values over neighborhoods is also a normal distribution since the difference of the two random
normal random variables is always normal, as shown in Figure 9(c). Given the confidence level
100(1-ff)%, we can calculate the confidence interval for the difference distributions, i.e., 100(1-
ff) percentage of difference value distribution lies between \Gammaz ff=2 and z ff=2 standard deviation
of the mean in the sample space. So we can classify the spatial outliers at the given confidence
level threshold.
6.3 Evaluation of Proposed Cost Model
We evaluated the I/O cost for different clustering methods for outlier detection procedures,
namely, Test Parameters Computation(TPC), Route Outlier Detection(ROD) and Random
Node Verification(RNV). The experiments used Twin-Cities traffic data with page size 1K
bytes, and two memory buffers. Table 2 shows the number of data page accesses for each
procedure under various clustering methods. The CRR value for each method is also listed in
the table. The cost function for TPC is C
ff). The cost function for
RNV is ff). The cost function for ROD is
as described in Section 4.2.
Clustering Parameters Computation Random Node Verification Route Outlier Detect
Method Actual Predicted Actual Predicted Actual Predicted CRR
Zord 1263 1269 349 357 78 79 0.31

Table

2: The actual I/O cost and predicted cost model for different clustering methods
As shown in Table 1, CCAM produced the lowest number of data page accesses for the
outlier detection procedures. This is to be expected, since CCAM generated the highest CRR
value.
6.4 Evaluation of I/O cost for TPC algorithm
In this section, we present the results of our evaluation of the I/O cost and CRR value for
alternative clustering methods while computing the test parameters. The parameters of interest
are buffer size, page size, number of neighbors, and neighborhood depth.
6.4.1 The effect of page size and CRR value

Figures

(a) and (b) show the number of data pages accessed and the CRR values respectively,
for different page clustering methods as the page sizes change. The buffer size is fixed at
Kbytes. As can be seen, a higher CRR value implies a lower number of data page accesses, as
predicted in the cost model. CCAM outperforms the other competitors for all four page sizes,
and CELL has better performance than Z-order clustering.
6.4.2 The effect of neighborhood cardinality
We evaluated the effect of varying the number of neighbors and the depth of neighbors for
different page clustering methods. We fixed the page size at 1K, and the buffer size at 4K,
and used the LRU buffering strategy. Figure 11 shows the number of page accesses as the
number of neighbors for each node increases from 2 to 10. CCAM has better performance
than Z-order and CELL. The performance ranking for each page clustering method remains the
same for different numbers of neighbors. Figure 11 shows the number of page accesses as the
Number
of
page
Page Size (K bytes)
Zord
(a) Page Accesses0.40.60.811 2 3 4 5 6 7 8
CRR
Value
Page Size (K Bytes)
Zord
(b) CRR

Figure

10: Effect of page size on data page accesses and CRR (buffer size = 32K)
neighborhood depth increases from 1 to 5. CCAM has better performance than Z-order and
CELL for all the neighborhood depths.5001500250035004500
Number
of
page
No of Neighbors
Zord
(a) Number of Neighbors1000300050007000
Number
of
page
Neighborhood Depth
Zord
(b) Neighborhood Depth

Figure

11: Effect of neighborhood cardinality on data page accesses (Page size = 1K, Buffer
Conclusions
In this paper, we focused on detecting outliers in spatial graph data sets. We proposed the
notion of a neighbor outlier in graph structured data sets, designed a fast algorithm to detect
outliers, analyzed the statistical foundation underlying our approach, provided the cost models
for different outlier detection procedures, and compared the performance of our approach
using different data clustering approaches. In addition, we provided experimental results from
the application of our algorithm on Twin Cities traffic archival to show its effectiveness and
usefulness.
We have evaluated alternative clustering methods for neighbor outlier query processing,
including model construction, random node verification, and route outlier detection. Our experimental
results show that the CCAM, which achieves the highest CRR, provides the best
overall performance.

Acknowledgment

We are particularly grateful to Professor Vipin Kumar, and our Spatial Database Group members, Weili Wu,
Yan Huang, Xiaobin Ma,and Hui Xiong for their helpful comments and valuable discussions. We would also like
to express our thanks to Kim Koffolt for improving the readability and technical accuracy of this paper.
This work is supported in part by USDOT grant on high performance spatial visualization of traffic data, and
is sponsored in part by the Army High Performance Computing Research Center under the auspices of the Department
of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract
number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the
government, and no official endorsement should be inferred. This work was also supported in part by NSF grant
#9631539.



--R

Optics: Ordering points to identify the clustering structure.
Outliers in Statistical Data.
Optics-of: Identifying local outliers.
Advances in Knowledge Discovery and Data Mining.
The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases
of Outliers.
Applied Multivariate Statistical Analysis.
A unified notion of outliers: Properties and computation.
Algorithms for mining distance-based outliers in large datasets
A Class of Data Structures for Associative Searching.
Knowledge Discovery in Databases.
Computatinal Geometry: An Introduction.
Efficient algorithms for mining outliers from large data sets.
Computing depth contours of bivariate point clouds.
A connectivity-clustered access method for aggregate queries on transportation networks-a summary of results
Finding outliers in very large datasets.
--TR
Computational geometry: an introduction
Applied multivariate statistical analysis
Computing depth contours of bivariate point clouds
OPTICS
Efficient algorithms for mining outliers from large data sets
A class of data structures for associative searching
The Design of the Cell Tree
OPTICS-OF
Algorithms for Mining Distance-Based Outliers in Large Datasets

--CTR
Yan Huang , Hui Xiong , Shashi Shekhar , Jian Pei, Mining confident co-location rules without a support threshold, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
a <u>L</u>inear <u>S</u>emantic <u>S</u>can <u>S</u>tatistic technique for detecting anomalous windows, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Sanjay Chawla , Pei Sun, SLOM: a new measure for local spatial outliers, Knowledge and Information Systems, v.9 n.4, p.412-429, April 2006
Shashi Shekhar , Yan Huang , Judy Djugash , Changqing Zhou, Vector map compression: a clustering approach, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA
Ian Davidson , Goutam Paul, Locating secret messages in images, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Jeffrey Xu Yu , Weining Qian , Hongjun Lu , Aoying Zhou, Finding centric local outliers in categorical/numerical spaces, Knowledge and Information Systems, v.9 n.3, p.309-338, March 2006

Chang-Tien Lu , Yufeng Kou , Jiang Zhao , Li Chen, Detecting and tracking regional outliers in meteorological data, Information Sciences: an International Journal, v.177 n.7, p.1609-1632, April, 2007
Victoria Hodge , Jim Austin, A Survey of Outlier Detection Methodologies, Artificial Intelligence Review, v.22 n.2, p.85-126, October 2004
outlier detection;spatial graphs;Spatial Data Mining