Text · dataset · 2025
Mining Distance-Based Outliers in Near Linear Time
Listed in Open NASA
Full title: Mining Distance-Based Outliers in Near Linear Time with Randomization and a Simple Pruning Rule
Description
Abstract
Defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. Recently, much work has been conducted with the goal of finding fast algorithms for this task. We show that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used.
Read the rest (1 more)
We test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. Our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.
Links
Get the data
- BaySchwabacherKDD2003.pdf c3.nasa.gov/dashlink/static/media/publication/BaySchwabacherKDD2003.pdf ↗
download · from open nasa gov
Where it is published
- Open NASA dataset page data.nasa.gov/dataset/mining-distance-based-outliers-in-near-linear-time ↗
landing page · from open nasa gov
Catalogue records · 1
- CKAN API data.nasa.gov/api/3/action/package_show?id=0e97b25d-c7ea-46ef-9ac4-255a3d666… ↗
metadata API · from open nasa gov
Related
- Possibly the same asMining Distance-Based Outliers in Near Linear Time
Provenance · 1 source records, 6 field assertions
| Source | Key | Last seen | Raw |
|---|---|---|---|
| Open NASA | 0e97b25d-c7ea-46ef-9ac4-255a3d66632b | 20 h ago | JSON v1 |
| Field | Assertion | Extractor | Evidence |
|---|---|---|---|
| created_date | source · open nasa gov | connector:open_nasa_gov@1.0.0 | |
| description | source · open nasa gov | connector:open_nasa_gov@1.0.0 | /notes |
| license_text | source · open nasa gov | connector:open_nasa_gov@1.0.0 | |
| publication_date | source · open nasa gov | connector:open_nasa_gov@1.0.0 | |
| title | source · open nasa gov | connector:open_nasa_gov@1.0.0 | /title |
| updated_date | source · open nasa gov | connector:open_nasa_gov@1.0.0 |