- Title
- LiNearN : A new approach to nearest neighbour density estimator
- Creator
- Wells, Jonathan; Ting, Kaiming; Washio, Takashi
- Date
- 2014
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/160049
- Identifier
- vital:12103
- Identifier
-
https://doi.org/10.1016/j.patcog.2014.01.013
- Identifier
- ISSN:0031-3203
- Abstract
- Despite their wide spread use, nearest neighbour density estimators have two fundamental limitations: O(n2) time complexity and O(n) space complexity. Both limitations constrain nearest neighbour density estimators to small data sets only. Recent progress using indexing schemes has improved to near linear time complexity only.We propose a new approach, called LiNearN for Linear time Nearest Neighbour algorithm, that yields the first nearest neighbour density estimator having O(n) time complexity and constant space complexity, as far as we know. This is achieved without using any indexing scheme because LiNearN uses a subsampling approach for which the subsample values are significantly less than the data size. Like existing density estimators, our asymptotic analysis reveals that the new density estimator has a parameter to trade off between bias and variance. We show that algorithms based on the new nearest neighbour density estimator can easily scale up to data sets with millions of instances in anomaly detection and clustering tasks. Highlights•Reject the premise that a NN algorithm must find the NN for every instance.•The first NN density estimator that has O(n) time complexity and O(1) space complexity.•These complexities are achieved without using any indexing scheme.•Our asymptotic analysis reveals that it trades off between bias and variance.•Easily scales up to large data sets in anomaly detection and clustering tasks.
- Publisher
- Elsevier Ltd.
- Relation
- Pattern Recognition Vol. 47, no. 8 (2014), p. 2702-2720
- Rights
- Copyright © 2014 Elsevier Ltd. All rights reserved
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0801 Artificial Intelligence and Image Processing; 0806 Information Systems; 0906 Electrical and Electronic Engineering; K -Nearest neighbour; Density-based; Anomaly detection; Clustering
- Reviewed
- Hits: 1514
- Visitors: 1467
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|