2000 EfficientAlgorithmsforMiningOut

• (Ramaswamy et al., 2000) ⇒ Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. (2000). “Efficient Algorithms for Mining Outliers from Large Data Sets.” In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of data. ISBN:1-58113-217-4 doi:10.1145/335191.335437

Subject Headings: Outlier Detection Algorithm.

Cited By

• http://scholar.google.com/scholar?q=%222000%22+Efficient+Algorithms+for+Mining+Outliers+from+Large+Data+Sets
• http://dl.acm.org/citation.cfm?id=335191.335437&preflayout=flat#citedby

Quotes

Abstract

In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its k^th nearest neighbor. We rank each point on the basis of its distance to its k^th 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 nested-loop 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

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2000 EfficientAlgorithmsforMiningOut	Sridhar Ramaswamy Rajeev Rastogi Kyuseok Shim			Efficient Algorithms for Mining Outliers from Large Data Sets				10.1145/335191.335437		2000