Nearest Neighbor Methods for Non-Euclidean Manifolds

摘要

Embodiments of the invention disclose a system and a method for determining a nearest neighbor to an input data point on a non-Euclidean manifold. The data points on the non-Euclidean manifold are clustered, projected into Euclidean sub-space nearest to the cluster and mapped from the Euclidean sub-space into a Hamming space such that neighboring data points of the Hamming space corresponds to neighboring data points on the non-Euclidean manifold. The method maps the input data point to the Hamming space corresponding to a particular Euclidean sub-space, wherein the particular Euclidean sub-space is the nearest to the input data point, and selects a data point corresponding to a nearest data point to the input data point in the Hamming space as the nearest neighbor for the input data point on the non-Euclidean manifold.