Probably correct k-nearest neighbor search in high dimensions

DOI10.1016/J.PATCOG.2009.09.026MaRDI QIDQ962679zbMATH OpenOpenAlexFDO

Authors Jun Toyama, Mineichi Kudo, Hideyuki Imai

Publication date 7 April 2010

Published in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.patcog.2009.09.026

zbMATH Keywords

pattern recognitionPAC frameworkprobably correct algorithmthe \(k\)-nearest neighbor method

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1559575
• scientific article; zbMATH DE number 2065612
• scientific article; zbMATH DE number 437552
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions

Cites work

• scientific article; zbMATH DE number 47593 (Why is no real title available?)
• scientific article; zbMATH DE number 1163871 (Why is no real title available?)
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1893569 (Why is no real title available?)
• A Branch and Bound Algorithm for Computing k-Nearest Neighbors
• An Algorithm for Finding Best Matches in Logarithmic Expected Time
• An Algorithm for Finding Nearest Neighbors
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Multidimensional binary search trees used for associative searching
• Nearest neighbor pattern classification
• Optimal Expected-Time Algorithms for Closest Point Problems

Cited in

(4)

• Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data
• Probabilistic proximity searching algorithms based on compact partitions
• Constructing a high-dimensional \(k\)NN-graph using a Z-order curve
• Reducing non-determinism of \(k\)-NN searching in non-ordered discrete data spaces

Describes a project that uses

Uses Software

• MNIST

This page was built for publication: Probably correct \(k\)-nearest neighbor search in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q962679)