Retrieval system and method using distance index
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11)
-
-
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.
-
Specification