# US 8,280,839 B2 · Nearest neighbor methods for non-Euclidean manifolds

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,839 B2
- Document ID: US8280839B2
- Status: Granted
- Kind: B2
- Application number: 12/712,791
- Filed: 2010-02-25
- Published: 2011-08-25
- Granted: 2012-10-02
- Earliest claimed: 2010-02-25
- Assignees: Mitsubishi Electric Research Laboratories, Inc.
- Inventors: Yuri A. Ivanov; Rizwan Choudhry
- Web page: https://patentgrep.com/patent/US8280839B2

## CPC

- G06F 18/21375: {involving differential geometry, e.g. embedding of pattern manifold}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the Euclidean sub-space nearest to the cluster is a tangent space.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
mapping the approximated cluster to the corresponding Hamming space using a spectral hashing method.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
determining geodesic distances between the input data point and centers of each cluster; and
selecting the particular Euclidean sub-space as the Euclidean sub-space corresponding to the cluster having a center at a minimum geodesic distance from the input data point.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
selecting the particular Euclidean sub-space as the Euclidean sub-space having a minimal reconstruction error for the input data point.

### Claim 6 (depends on 1)

The method of claim 1, wherein the data points lie on a Riemannian manifold, and the set of Euclidean sub-spaces is a set of tangent spaces.

### Claim 7 (depends on 1)

The method of claim 1, wherein the clustering further comprises:
clustering the data points based on a Riemannian k-means method.

### Claim 8 (depends on 1)

The method of claim 1, wherein the clustering further comprises:
initializing cluster centers by randomly selecting K points from the data points;
determining, for each data point, a geodesic distance to each cluster center;
assigning the cluster center nearest to the data point as a cluster membership of the data point;
recomputing each cluster center as an extrinsic mean of the data points in each cluster based on the cluster membership; and
repeating the assigning and recomputing until convergence to the extrinsic mean.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
projecting the data points into a low-dimensional Euclidean space using a non-linear dimensionality reduction; and
determining a cluster association of the data points on the low-dimensional Euclidean space.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
performing the non-linear dimensionality reduction based on multidimensional scaling.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
performing a non-linear clustering for the determining the cluster association based on kernel k-means and/or spectral clustering.

### Claim 12 (depends on 9)

The method of claim 9, further comprising:
selecting a representative data point in each cluster to represent the cluster.

### Claim 13 (depends on 9)

The method of claim 9, wherein the selecting further comprises:
determining a mapped data point nearest to a center of the cluster in the low-dimensional Euclidean space; and
selecting the representative data point on the manifold corresponding to the mapped data point.

### Claim 14 (depends on 12)

The method of claim 12, further comprising:
mapping the data points of each cluster to the Hamming space based on kernel spectral hashing (KSH).

### Claim 15

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, wherein the data points are clustered and the data points of each cluster are projected into Euclidean sub-space nearest to the cluster and mapped from the Euclidean sub-space into a Hamming space producing a set of Hamming spaces such that neighboring data points of the Hamming space corresponds to neighboring data points on the non-Euclidean manifold, comprising steps of:
mapping 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, wherein the mapping is performed by a processor; and
selecting 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.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
determining geodesic distances between the input data point and centers of each cluster; and
selecting the particular Euclidean sub-space as the Euclidean sub-space corresponding to a cluster having a center at a minimum geodesic distance from the input data point.

### Claim 17 (depends on 15)

The method of claim 15, further comprising:
selecting the particular Euclidean sub-space as the Euclidean sub-space having a minimal reconstruction error for the input data point.

### Claim 18

A system 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, wherein the data points are clustered and the data points of each cluster are projected into Euclidean sub-space nearest to the cluster and mapped from the Euclidean sub-space into a Hamming space producing a set of Hamming spaces such that neighboring data points of the Hamming space corresponds to neighboring data points on the non-Euclidean manifold, comprising:
a processor configured to map 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, wherein the mapping is performed by a processor; and
means for selecting 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.

### Claim 19 (depends on 18)

The system of claim 18, further comprising:
means for determining geodesic distances between the input data point and centers of each cluster; and
means for selecting the particular Euclidean sub-space as the Euclidean sub-space corresponding to a cluster having a center at a minimum geodesic distance from the input data point.

### Claim 20 (depends on 18)

The system of claim 18, further comprising:
means for selecting the particular Euclidean sub-space as the Euclidean sub-space having a minimal reconstruction error for the input data point.
