LiNearN: A new approach to nearest neighbour density estimator
作者：
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.
摘要
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.
论文关键词：k-nearest neighbour,Density-based,Anomaly detection,Clustering
论文评审过程：Received 30 January 2013, Revised 9 September 2013, Accepted 23 January 2014, Available online 1 February 2014.
论文官网地址：https://doi.org/10.1016/j.patcog.2014.01.013
