Welcome to D
SIGMOD'00
= SIGMOD'00 We
= Plenary Talk
<<< = SIGMOD'00 Pa>>>
PODS'00
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

Efficient Algorithms for Mining Outliers from Large Data Sets


Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim

  View Paper (PDF)  

Return to Research Sessions


Abstract

In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nestedloop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.


References


Note: References link to DBLP on the Web.

[AAR96]
Andreas Arning , Rakesh Agrawal , Prabhakar Raghavan : A Linear Method for Deviation Detection in Large Databases. KDD 1996 : 164-169
[AMS+95]
Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo : Fast Discovery of Association Rules. Advances in Knowledge Discovery and Data Mining. 1996 : 307-328
[BKNS00]
Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander : LOF: Identifying Density-Based Local Outliers. SIGMOD Conference 2000 : 93-104
[BKSS90]
Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990 : 322-331
[BL94]
...
[EKX95]
Martin Ester , Hans-Peter Kriegel , Xiaowei Xu : A Database Interface for Clustering in Large Spatial Databases. KDD 1995 : 94-99
[GRS98]
Sudipto Guha , Rajeev Rastogi , Kyuseok Shim : CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998 : 73-84
[JD88]
Anil K. Jain , Richard C. Dubes: Algorithms for Clustering Data. Prentice-Hall 1988
[KN98]
Edwin M. Knorr , Raymond T. Ng : Algorithms for Mining Distance-Based Outliers in Large Datasets. VLDB 1998 : 392-403
[KN99]
Edwin M. Knorr , Raymond T. Ng : Finding Intensional Knowledge of Distance-Based Outliers. VLDB 1999 : 211-222
[NH94]
Raymond T. Ng , Jiawei Han : Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994 : 144-155
[RKV95]
Nick Roussopoulos , Stephen Kelley , Frédéic Vincent : Nearest Neighbor Queries. SIGMOD Conference 1995 : 71-79
[RRS98]
...
[RS98]
Rajeev Rastogi , Kyuseok Shim : PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning. VLDB 1998 : 404-415
[Sam89]
Hanan Samet : The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[SAM98]
Sunita Sarawagi , Rakesh Agrawal , Nimrod Megiddo : Discovery-Driven Exploration of OLAP Data Cubes. EDBT 1998 : 168-182
[ZRL96]
Tian Zhang , Raghu Ramakrishnan , Miron Livny : BIRCH: An Efficient Data Clustering Method for Very Large Databases. SIGMOD Conf. 1996 : 103-114

Referenced by

  1. Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander : LOF: Identifying Density-Based Local Outliers. SIGMOD Conference 2000 : 93-104

BIBTEX


@inproceedings{DBLP:conf/sigmod/RamaswamyRS00,
  author    = {Sridhar Ramaswamy and
                Rajeev Rastogi and
                Kyuseok Shim},
   editor    = {Weidong Chen and
                Jeffrey F. Naughton and
                Philip A. Bernstein},
   title     = {Efficient Algorithms for Mining Outliers from Large Data Sets},
   booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on
                Management of Data, May 16-18, 2000, Dallas, Texas, USA},
   journal   = {SIGMOD Record},
   publisher = {ACM},
   volume    = {29},
   number    = {2},
   year      = {2000},
   isbn      = {1-58113-218-2},
   pages     = {427-438},
   crossref  = {DBLP:conf/sigmod/2000},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.