Search method, search program, and search device

• US 9,864,926 B2
• Filed: 11/18/2014
• Issued: 01/09/2018
• Est. Priority Date: 12/19/2013
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Noma, Yui, Konoshima, Makiko
• Primary Examiner(s): Park, Chan
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US14/546,456
• Publication Number:
  US 20150178590A1
• Time in Patent Office: 1,148 Days
• 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;

searching for parameters by which a position of the first-dimensional feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the first-dimensional 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;

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.

2. The search method according to claim 1, wherein the computer 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.

3. The search method according to claim 1, wherein the computer 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.

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

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

6. A non-transitory 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;

searching for parameters by which a position of the first-dimensional feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the first-dimensional 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;

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.

7. The non-transitory computer readable recording medium according to claim 6, wherein the computer executes the process for searching 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.

8. The non-transitory computer readable recording medium according to claim 6, wherein the computer executes the process for searching for the parameters on the basis of an average value of the plurality of feature vectors and a maximum value of eigenvalues of variance-covariance matrices of the feature vectors.

9. The non-transitory computer readable recording medium according to claim 6, wherein the computer executes the process for searching for the parameters on the basis of a hill-climbing method, a Markov Chain Monte Carlo method, or swarm intelligence.

16. The non-transitory computer readable recording medium according to claim 6, wherein the computer executes the process for identifying a cumulative contribution ratio curve on the basis of a principal component analysis result of the plurality of feature vectors and searches for parameters on the basis of the cumulative contribution ratio curve.

10. 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;

searching for parameters by which a position of the first-dimensional feature vector to be mapped onto a surface of a sphere is concentrated onto a hemisphere of the sphere when the first-dimensional 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;

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.

11. The search device according to claim 10, wherein the processor executes the process for searching 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.

12. The search device according to claim 10, wherein the processor executes the process for searching 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.

13. The search device according to claim 10, wherein the processor executes the process including identifying a cumulative contribution ratio curve on the basis of a principal component analysis result of the plurality of feature vectors and searches for parameters on the basis of the cumulative contribution ratio curve.

14. The search device according to claim 10, wherein the processor executes the process including identifying a cumulative contribution ratio curve on the basis of a principal component analysis result of the first dimensional feature vector and searches for parameters on the basis of the cumulative contribution ratio curve.

15. The search device according to claim 10, wherein the processor executes the process for searching for the parameters on the basis of a hill-climbing method, a Markov Chain Monte Carlo, or swarm intelligence.