SEARCH METHOD, SEARCH PROGRAM, AND SEARCH DEVICE

• US 20150178590A1
• Filed: 11/18/2014
• Published: 06/25/2015
• Est. Priority Date: 12/19/2013
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Noma, Yui, Konoshima, Makiko
• Granted Patent: US 9,864,926 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

A search device according to an embodiment maps a feature vector onto a hyper-sphere on the basis of parameters which include an intersection and a distance, with the intersection at which an m-dimensional feature space and a straight line passing through the hyper-sphere present in a space greater in dimension than m intersect and the distance being from the north pole of the hyper-sphere to the feature space. In this case, the search device searches for the parameters which allow the positions of feature vectors mapped onto the hyper-sphere to be concentrated on a predetermined hemisphere of the hyper-sphere.

Claims

1. A search method to be performed by a computer, the search method comprising:

acquiring a first-dimensional feature vector stored in a database; and

searching for parameters by which a position of the feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the feature vector is mapped onto the surface of the sphere on the basis of the parameters including an intersection and a distance, the intersection at which a feature space and a straight line passing through the sphere present in a space greater in dimension by one or more than the feature space intersect, the distance being from a predetermined point of the sphere to the feature space.

2. The search method according to claim 1, further comprising:

mapping a plurality of feature vectors onto the surface of the sphere by the parameters found by the searching;

generating bit strings of the feature vectors from a relationship between the position of the mapped feature vectors and a plurality of hyper-planes dividing the sphere; and

determining a similar feature vector on the basis of the generated bit strings.

3. The search method according to claim 1, wherein the searching searches for the parameters which allow the positions of the feature vectors mapped onto the surface of the sphere to be concentrated on a southern hemisphere, an eastern hemisphere, or a western hemisphere of the sphere.

4. The search method according to claim 1, wherein the searching searches for the parameters on the basis of an average value of the feature vectors and a maximum value of eigenvalues of variance-covariance matrices of the feature vectors.

5. The search method according to claim 1, wherein the searching identifies a cumulative contribution ratio curve on the basis of a principal component analysis result of the feature vectors and searches for the parameters on the basis of the cumulative contribution ratio curve.

6. The search method according to claim 1, wherein the searching searches for parameters on the basis of a hill-climbing method, a Markov Chain Monte Carlo method, or swarm intelligence.

7. A computer-readable recording medium having stored therein a search program for causing a computer to execute a process including:

acquiring a first-dimensional feature vector stored in a database; and

searching for parameters by which a position of the feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the feature vector is mapped onto the surface of the sphere on the basis of the parameters including an intersection and a distance, the intersection at which a feature space and a straight line passing through the sphere present in a space greater in dimension by one or more than the feature space intersect, the distance being from a predetermined point of the sphere to the feature space.

8. The computer-readable recording medium according to claim 7, wherein the process further comprising:

mapping a plurality of feature vectors onto the surface of the sphere by the parameters found by the searching;

generating bit strings of the feature vectors from a relationship between the position of the mapped feature vectors and a plurality of hyper-planes dividing the sphere; and

determining a similar feature vector on the basis of the generated bit strings.

9. The computer-readable recording medium according to claim 7, wherein the searching searches for the parameters which allow the positions of the feature vectors mapped onto the surface of the sphere to be concentrated on a southern hemisphere, an eastern hemisphere, or a western hemisphere of the sphere.

10. The computer-readable recording medium according to claim 7, wherein the searching searches for the parameters on the basis of an average value of the feature vectors and a maximum value of eigenvalues of variance-covariance matrices of the feature vectors.

11. The computer-readable recording medium according to claim 7, wherein the searching searches for parameters on the basis of a hill-climbing method, a Markov Chain Monte Carlo method, or swarm intelligence.

12. A search device comprising:

a memory; and

a processor coupled to the memory, wherein the processor executes a process comprising;

acquiring a first-dimensional feature vector stored in a database; and

searching for parameters by which a position of the feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the feature vector is mapped onto the surface of the sphere on the basis of the parameters including an intersection and a distance, the intersection at which a feature space and a straight line passing through the sphere present in a space greater in dimension by one or more than the feature space intersect, the distance being from a predetermined point of the sphere to the feature space.

13. The search device according to claim 12, wherein the process further comprises

mapping a plurality of feature vectors onto the surface of the sphere by the parameters found by the searching,

generating bit strings of the feature vectors from a relationship between the position of the mapped feature vectors and a plurality of hyper-planes dividing the sphere, and

determining a similar feature vector on the basis of the generated bit strings.

14. The search device according to claim 12, wherein the searching searches for the parameters which allow the positions of the feature vectors mapped onto the surface of the sphere to be concentrated on a southern hemisphere, an eastern hemisphere, or a western hemisphere of the sphere.

15. The search device according to claim 12, wherein the searching searches for the parameters on the basis of an average value of the feature vectors and a maximum value of eigenvalues of variance-covariance matrices of the feature vectors.

16. The search device according to claim 12, wherein the searching identifies a cumulative contribution ratio curve on the basis of a principal component analysis result of the feature vectors and searches for the parameters on the basis of the cumulative contribution ratio curve.

17. The search device according to claim 12, wherein the searching identifies a cumulative contribution ratio curve on the basis of a principal component analysis result of the feature vector and searches for the parameters on the basis of a gradient of the cumulative contribution ratio curve.

18. The search device according to claim 12, wherein the searching searches for parameters on the basis of a hill-climbing method, a Markov Chain Monte Carlo method, or swarm intelligence.