Full Citation

Title: New Algorithms for Efficient High-Dimensional Nonparametric Classification

Citation Type: Journal Article

Publication Year: 2006

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: This paper is about non-approximate acceleration of high-dimensional nonparametric operations such as k nearest neighbor classifiers. We attempt to exploit the fact that even if we want exact answers to nonparametric queries, we usually do not need to explicitly find the data points close to the query, but merely need to answer questions about the properties of that set of data points. This offers a small amount of computational leeway, and we investigate how much that leeway can be exploited. This is applicable to many algorithms in nonparametric statistics, memory-based learningand kernel-based learning. But for clarity, this paper concentrates on pure k-NN classification. We introduce new ball-tree algorithms that on real-world data sets give accelerations from 2-fold to 100-fold compared against highly optimized traditional ball-tree-based k-NN . These results include data sets with up to 106 dimensions and 105 records, and demonstrate non-trivial speed-ups while giving exact answers.

User Submitted?: No

Authors: Liu, Ting; Moore, Andrew W.; Gray, Alexander

Periodical (Full): Journal of Machine Learning Research

Issue:

Volume: 7

Pages: 1135-1158

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: