Patent ID: 8280839
Filing Date: 2012-10-02
Classification: G06K

Abstract:
1. A method for determining a nearest neighbor to an input data point lying on a non-Euclidean manifold from data points lying on the non-Euclidean manifold, comprising the steps of: clustering the data points into a set of clusters; determining, for each cluster, a Euclidean sub-space nearest to the cluster to form a set of Euclidean sub-spaces; projecting the data points of each cluster into the Euclidean sub-space nearest to the cluster, such that each cluster is approximated by data points lying on the Euclidean sub-space to produce a set of approximated clusters; mapping each of the approximated clusters into a corresponding Hamming space to produce a set of Hamming clusters, such that neighboring data points of the Hamming cluster corresponds to neighboring data points on the non-Euclidean manifold; mapping the input data point to the Hamming cluster corresponding to a particular Euclidean sub-space, wherein the particular Euclidean sub-space is nearest to the input data point; and selecting the data point corresponding to the 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, wherein the steps are performed in a processor.