Affiliations: Computer Science Department, University of Minnesota, 200 Union Street SE, Minneapolis, MN-55455, USA. Tel.: +1 612 6248307; Fax: +1 612 6250572; E-mail: shekhar@cs.umn.edu, ctlu@cs.umn.edu, pusheng@cs.umn.edu
Note: [1] This work is supported in part by the Army High Performance Computing Research Center under the auspices of Department
of the Army, Army Research Laboratory Cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-
C-0008, and by the National Science Foundation under grant 9631539.
Abstract: Identification of outliers can lead to the discovery of unexpected and interesting 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 a fast algorithm to detect spatial outliers, and provide cost models for outlier detection procedures. In addition, we provide experimental results from the application of our algorithm on a Minneapolis-St. Paul (Twin Cities) traffic data set to show its effectiveness and usefulness.
Keywords: outlier detection, spatial data mining, spatial graphs
