# 2012 ANearLinearTimeApproximationAlg

- (Pham & Pagh, 2012) ⇒ Ninh Pham, and Rasmus Pagh. (2012). “A Near-linear Time Approximation Algorithm for Angle-based Outlier Detection in High-dimensional Data.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339669

**Subject Headings:**

## Notes

## Cited By

- http://scholar.google.com/scholar?q=%222012%22+A+Near-linear+Time+Approximation+Algorithm+for+Angle-based+Outlier+Detection+in+High-dimensional+Data
- http://dl.acm.org/citation.cfm?id=2339530.2339669&preflayout=flat#citedby

## Quotes

### Author Keywords

### Abstract

Outlier mining in *d* - dimensional point sets is a fundamental and well studied data mining task due to its variety of applications.
Most such applications arise in high-dimensional domains.
A bottleneck of existing approaches is that implicit or explicit assessments on concepts of distance or nearest neighbor are deteriorated in high-dimensional data.
Following up on the work of Kriegel et al. (KDD ' 08), we investigate the use of *angle-based outlier factor* in mining high-dimensional outliers.
While their algorithm runs in cubic time (with a quadratic time heuristic), we propose a novel random projection-based technique that is able to estimate the angle-based outlier factor for all data points in time near-linear in the size of the data.
Also, our approach is suitable to be performed in parallel environment to achieve a parallel speedup.
We introduce a theoretical analysis of the quality of approximation to guarantee the reliability of our estimation algorithm.
The empirical experiments on synthetic and real world data sets demonstrate that our approach is efficient and scalable to very large high-dimensional data sets.

## References

;

Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|

2012 ANearLinearTimeApproximationAlg | Ninh Pham Rasmus Pagh | A Near-linear Time Approximation Algorithm for Angle-based Outlier Detection in High-dimensional Data | 10.1145/2339530.2339669 | 2012 |

Author | Ninh Pham + and Rasmus Pagh + |

conference | KDD-2012 + |

doi | 10.1145/2339530.2339669 + |

proceedings | Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining + |

title | A Near-linear Time Approximation Algorithm for Angle-based Outlier Detection in High-dimensional Data + |

year | 2012 + |