Retrieval system and method using distance index

• US 6,845,377 B2
• Filed: 03/22/2002
• Issued: 01/18/2005
• Est. Priority Date: 11/06/2001
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Kozakura, Fumihiko, Yamane, Yasuo
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/102,829
• Publication Number:
  US 20030088563A1
• Time in Patent Office: 1,033 Days
• Field of Search: 707/2, 707/3, 707/7, 707/100, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Similarity retrieval is performed through the use of a distance index which contains a concatenated key and pointer information and retains a dictionary type order in the concatenated key. The concatenated key is produced by discretizing the distance from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters and concatenating the resulting discretized distances. The use of the concatenated key allows candidate points in the d-distance neighborhood to be narrowed down.

Claims

1. An information retrieval device which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

a storage device storing an index which includes a plurality of concatenated keys and pointer information and retains a dictionary type order of the concatenated keys, each concatenated key being produced by discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters and by concatenating resulting discrete distances, the pointer information allowing access to information corresponding to the object point;

a retrieval device determining a set of object points within a predetermined distance from a point specified in the multidimensional space and acquiring information corresponding to the object points in the set through the use of the index; and

an output device outputting the acquired information.

2. The retrieval device according to claim 1, wherein each discrete distance for at least part of a plurality of object points in the multidimensional space is produced by projecting an object point onto a projection reference line to obtain an object projected point and by discretizing a distance from a projection reference point on the projection reference line to the object projected point.

3. The retrieval device according to claim 1, wherein the discrete distances are produced with a distance more than two times a threshold radius of similarity in the multidimensional space as a unit of discretization.

4. The retrieval device according to claim 1, wherein, when the multidimensional space is represented by a super cube, vertexes of the super cube are used as the reference points.

5. The retrieval device according to claim 1, wherein points on an extension of a straight line in the multidimensional space are used as the reference points.

6. The retrieval device according to claim 1, wherein, when the set of object points are included in a plurality of bands of discrete distances from a certain reference point, the retrieval device performs retrieval for each of the bands.

7. The retrieval device according to claim 6, wherein, when a range of retrieval has been narrowed down, the retrieval device switches retrieval from retrieval for each of the bands to sequential retrieval.

8. The retrieval device according to claim 1, wherein, if, in determining a predetermined number of object points in the order in which the object points are close to the specified point, the number of the object points contained in the set of object points within the predetermined distance is not less than the predetermined number, the retrieval device determines the predetermined number of object points from the set, and otherwise the retrieval device repeats a process of determining the set of object points within the predetermined distance while sequentially increasing the predetermined distance.

9. The retrieval device according to claim 1, wherein the index contains feature parameters of the information corresponding to the object points in addition to the concatenated keys and the pointer information.

10. An information retrieval device which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

a storage device storing a plurality of concatenated bit patterns and information to be retrieved corresponding to a plurality of object points in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters, each concatenated bit pattern being produced by discretizing a distance from each of a plurality of reference points to each object point representing the information to be retrieved and by concatenating a plurality of bit patterns representing resulting discrete distances; and

a retrieval device determining a set of object points within a predetermined distance from a point specified in the multidimensional space and acquiring information corresponding to the object points in the set through the use of the concatenated bit patterns; and

an output device outputting the acquired information.

11. The retrieval device according to claim 10, wherein the retrieval device narrows down candidates of object points by producing a logical product of a concatenated bit pattern for each object point and a bit pattern for a region within a predetermined distance from the specified point.

12. A computer-readable recording medium in which is stored a program for a computer to retrieve from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, the program causing the computer to perform:

determining a set of object points within a predetermined distance from a point specified in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters through the use of an index which includes a plurality of concatenated keys and pointer information and retains a dictionary type order of the concatenated keys, each concatenated key being produced by discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved and by concatenating resulting discrete distances, the pointer information allowing access to information corresponding to the object point;

acquiring information corresponding to the object points in the set through the use of the index; and

outputting the acquired information.

13. A computer-readable recording medium in which is stored a program for a computer to retrieve from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, the program causing the computer to perform:

determining a set of object points within a predetermined distance from a point specified in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters through the use of a plurality of concatenated bit patterns, each concatenated bit pattern being produced by discretizing a distance from each of a plurality of reference points to each object point representing the information to be retrieved and by concatenating a plurality of bit patterns representing resulting discrete distances;

acquiring information corresponding to the object points in the set through the use of the concatenated bit patterns; and

outputting the acquired information.

14. A propagation signal for propagating a program to a computer which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, the program causing the computer to perform:

determining a set of object points within a predetermined distance from a point specified in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters through the use of an index which includes a plurality of concatenated keys and pointer information and retains a dictionary type order of the concatenated keys, each concatenated key being produced by discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved and by concatenating resulting discrete distances, the pointer information allowing access to information corresponding to the object point;

acquiring information corresponding to the object points in the set through the use of the index; and

outputting the acquired information.

15. A propagation signal for propagating a program to a computer which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, the program causing the computer to perform:

determining a set of object points within a predetermined distance from a point specified in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters through the use of a plurality of concatenated bit patterns, each concatenated bit pattern being produced by discretizing a distance from each of a plurality of reference points to each object point representing the information to be retrieved and by concatenating a plurality of bit patterns representing resulting discrete distances;

acquiring information corresponding to the object points in the set through the use of the concatenated bit patterns; and

outputting the acquired information.

16. A computer-readable recording medium stored with data which, when referred to by a computer, allows the computer to retrieve from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter,

wherein the data has an index structure including a plurality of concatenated keys and pointer information, each concatenated key being produced by discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters and by concatenating resulting discrete distances, the pointer information allowing access to information corresponding to the object point, the index structure being configured to retain a dictionary type order of the concatenated keys and to allow the computer to determine a set of object points within a predetermined distance from a point specified in the multidimensional space through the use of the concatenated keys and acquire information corresponding to the object points in the set through the use of the pointer information.

17. A computer-readable recording medium stored with data which, when referred to by a computer, allows the computer to retrieve from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter,

wherein the data has an index structure including a plurality of concatenated bit patterns and information to be retrieved corresponding to a plurality of object points in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters, each concatenated bit pattern being produced by discretizing a distance from each of a plurality of reference points to each object point representing the information to be retrieved and by concatenating a plurality of bit patterns representing resulting discrete distances, the index structure being configured to allow the computer to determine a set of object points within a predetermined distance from a point specified in the multidimensional space and acquire information corresponding to the object points in the set through the use of the concatenated bit patterns.

18. A method of retrieving from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters;

concatenating resulting discrete distances to produce a concatenated key;

entering an index including a plurality of concatenated keys and pointer information to make access to information corresponding to the object point and retaining a dictionary type order of the concatenated keys into a computer system;

determining a set of object points within a predetermined distance from a point specified in the multidimensional space through the use of the index; and

acquiring information corresponding to the object points in the set through the use of the index.

19. A method of retrieving from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

discretizing a distances from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters;

concatenating a plurality of bit patterns representing resulting discrete distances to produce a concatenated bit pattern;

entering a plurality of concatenated bit patterns into a computer system;

determining a set of object points within a predetermined distance from a point specified in the multidimensional space through the use of the concatenated bit patterns; and

acquiring information corresponding to the object points in the set through the use of the concatenated bit patterns.

20. An information retrieval device which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

storage means for storing an index which includes a plurality of concatenated keys and pointer information and retains a dictionary type order of the concatenated keys, each concatenated key being produced by discretizing a distance from each of a plurality of reference points to an object point representing information to be retrieved in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters and by concatenating resulting discrete distances, the pointer information allowing access to information corresponding to the object point;

retrieval means for determining a set of object points within a predetermined distance from a point specified in the multidimensional space and acquiring information corresponding to the object points in the set through the use of the index; and

output means for outputting the acquired information.

21. An information retrieval device which retrieves from among information items each having a plurality of feature parameters an information item having a feature parameter similar to a specified feature parameter, comprising:

storage means for storing a plurality of concatenated bit patterns and information to be retrieved corresponding to a plurality of object points in a multidimensional space consisting of a plurality of dimensions corresponding to the plurality of feature parameters, each concatenated bit pattern being produced by discretizing a distance from each of a plurality of reference points to each object point representing the information to be retrieved and by concatenating a plurality of bit patterns representing resulting discrete distances; and

retrieval means for determining a set of object points within a predetermined distance from a point specified in the multidimensional space and acquiring information corresponding to the object points in the set through the use of the concatenated bit patterns; and

output means for outputting the acquired information.