Indexing method and apparatus

• US 6,873,993 B2
• Filed: 05/24/2001
• Issued: 03/29/2005
• Est. Priority Date: 06/21/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Garner, Philip Neil, Charlesworth, Jason Peter Andrew
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US09/863,424
• Publication Number:
  US 20020052870A1
• Time in Patent Office: 1,405 Days
• Field of Search: 707 1- 6, 707100-102, 707/104.1, 704/231, 704/251
• US Class Current: 707/740
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/45 Clustering; Classification
• CPC Class Codes: G06F 16/61 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/632 Query formulation
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An indexing apparatus and method are described for use in identifying portions of data in a database for comparison with a query. In an embodiment, the index includes a key which comprises a sequence of phoneme classifications derived from the input query by classifying each of the phonemes in the input query with a number of phoneme classes, with the phonemes in each class being defined as those that are confusable with the other phonemes in the same class.

Claims

1. An apparatus for identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of sub-word units, said apparatus comprising:

a memory for storing data defining a plurality of sub-word unit classes, each class comprising sub-word units that are confusable with other sub-word units in the same class;

a memory for storing an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising;

a key associated with the entry and which is related to the identifier for the entry in a predetermined manner; and

a number of pointers which point to portions of data in the database which correspond to the key associated with the entry,

wherein each key comprises a sequence of sub-word unit classifications which is derived from a corresponding sequence of sub-word units appearing in the database by classifying each of the sub-word units in the sequence into one of the plurality of sub-word unit classes;

means for classifying each of the sub-word units in the input query into one of the plurality of sub-word unit classes and for defining one or more sub-sequences of query sub-word unit classifications;

means for determining a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query sub-word unit classifications;

means for comparing the key associated with each of the determined identifiers determined by said determining means with the corresponding sub-sequence of query sub-word unit classifications; and

means for retrieving one or more pointers from the index in accordance with the output of said comparing means, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.

2. An apparatus according to claim 1, wherein the sub-word units are phonemes.

3. An apparatus according to claim 1, wherein at least ten sub-word unit classes are defined in advance.

4. An apparatus according to claim 1, wherein each key is related to the corresponding identifier by a predetermined mathematical function.

5. An apparatus according to claim 4, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{W}{\prod <br><br>}}<br><br>\left[C<br><br>\left[i\right]<br><br>K_c\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S,$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and W is the number of sub-word unit classifications in each key.

6. An apparatus according to claim 4, wherein said determining means is operable to determine a corresponding identifier for each subsequence of query sub-word unit classifications using the predetermined mathematical function.

7. An apparatus according to claim 4, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>K_c^{\left(n-i\right)}·<br><br>C<br><br>\left[i\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and n is the number of sub-word unit classifications in each key.

8. An apparatus according to claim 1, wherein said determining means is operable to identifier a new identifier for another entry in the index for a subsequence of query sub-word unit classifications if said comparing means determines that the key for the identifier is not the same as the subsequence of query sub-word unit classifications.

9. An apparatus according to claim 8, wherein said determining means is operable to determine a new identifier using the following equation:

IDX=[IDX+V]Mod S,

where IDX is the identifier, S is the number of entries in the index, and V is a predetermined number.

10. An apparatus according to claim 1, wherein the key for one or more of the entries is a null key indicating that there are no pointers stored in the index for that entry.

11. An apparatus according to claim 1, wherein the input query is a spoken query and said apparatus further comprises a speech recognition system for processing the spoken query and for outputting the sequence of sub-word units.

12. An apparatus for searching a database in response to a query input by a user, the database comprising a plurality of sequences of sub-word units and the query comprising at least one sequence of sub-word units, said apparatus comprising:

an apparatus according to any of claims 1 to 11 for identifying one or more portions of data in the database for comparison with the input query; and

means for comparing the one a more sequences of query sub-word units with the identified one or more portions of data in the database.

13. An apparatus according to claim 12, wherein said means for comparing the input query with the portions of data in the database uses a dynamic programming comparison technique.

14. An apparatus according to claim 12, further comprising means for retrieving one or more data files in accordance with the results of said comparing means.

15. An apparatus according to claim 1, wherein the input query is a typed query and said apparatus further comprises means for converting the typed query into the sequence of sub-word units.

16. An apparatus for identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of features, said apparatus comprising:

a memory for storing data defining a plurality of feature classes, each class comprising features that are confusable with other features in the same class;

a memory for storing an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising;

a key associated with the entry and which is related to the identifier for the entry in a predetermined manner; and

a number of pointers which point to portions of data in the database which correspond to the key associated with the entry,

wherein each key comprises a sequence of feature classifications which is derived from a corresponding sequence of features appearing in the database by classifying each of the features in the sequence into one of the plurality of feature classes;

means for classifying each of the features in the input query into one of the plurality of feature classes and for defining one or more sub-sequences of query feature classifications;

means for determining a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query feature classifications;

means for comparing the key associated with each of the determined identifiers determined by said determining means with the corresponding sub-sequence of query feature classifications; and

means for retrieving one or more pointers from the index in accordance with the output of said comparing means, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.

17. A method of identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of sub-word units, the method comprising the steps of:

storing data defining a plurality of sub-word unit classes, each class comprising sub-word units that are confusable with other sub-word units in the same class;

storing an index having a plurality of entries, each entry having an associated identifier for identifying the entry,

a key associated with the entry and which is related to the identifier for the entry in a predetermined manner, and

a number of pointers which point to portions of data in the database which correspond to the key associated with the entry.

wherein each key comprises a sequence of sub-word unit classifications which is derived from a corresponding sequence of sub-word units appearing in the database by classifying each of the sub-word units in the sequence into one of the plurality of sub-word unit classes;

classifying each of the sub-word units in the input query into one of the plurality of sub-word unit classes and for defining one or more sub-sequences of query sub-word unit classifications;

determining a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query sub-word unit classifications;

comparing the key associated with each of the determined identifiers determined in said determining step with the corresponding sub-sequence of query sub-word unit classifications; and

retrieving one or more pointers from the index in accordance with the output of said comparing step, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.

18. A method according to claim 17, wherein the sub-word units are phonemes.

19. A method according to claim 17, wherein at least ten sub-word unit classes are defined in advance.

20. A method according to claim 17, wherein each key is related to the corresponding identifier by a predetermined mathematical function.

21. A method according to claim 20, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{W}{\prod <br><br>}}<br><br>\left[C<br><br>\left[i\right]<br><br>K_c\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and W is the number of sub-word unit classifications in each key.

22. A method according to claim 20, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>K_c^{\left(n-i\right)}·<br><br>C<br><br>\left[i\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and n is the number of sub-word unit classifications in each key.

23. A method according to claim 17, wherein said determining step identifies a new identifier for another entry in the index for a subsequence of query sub-word unit classifications if said comparing step determines that the key for the identifier is not the same as the subsequence of query sub-word unit classifications.

24. A method according to claim 23, wherein said determining step determines a new identifier using the following equation:

IDX=[IDX+V] Mod S,

where IDX is the identifier, S is the number of entries in the index, and V is a predetermined number.

25. A method according to claim 24, wherein said determining step determines a corresponding identifier for each subsequence of query sub-word unit classifications using the predetermined mathematical function.

26. A method according to claim 17, wherein the input query is a typed query and wherein the method further comprises a step of converting the typed query into the sequence of sub-word units.

27. A method according to claim 17, wherein the input query is a spoken query and wherein the method further comprises a step of using a speech recognition system to process the spoken query to generate the sequence of sub-word units.

28. A method of searching a database in response to a query input by a user, the database comprising a plurality of sequences of sub-word units and the query comprising at least one sequence of sub-word units, said method comprising:

method steps of claim 17 for identifying one or more portions of data in the database for comparison with the input query; and

a step of comparing the one or more sequences of query sub-word units with the identified one or more portions of data in the database.

29. A method according to claim 28, wherein said comparing step uses a dynamic programming comparison technique to compare the input query with the portions of data.

30. A method according to claim 28, further comprising a step of retrieving one or more data files in dependence upon the results of said comparing step.

31. A method according to claim 17, wherein the key for one or more of the entries is a null key indicating that there are no pointers stored in the index for that entry.

32. An apparatus for identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of sub-word units, the apparatus comprising:

a first memory operable to store data defining a plurality of sub-word unit classes, each class comprising sub-word units that are confusable with other sub-word units in the same class;

a second memory operable to more an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising;

a key associated with the entry and which is related to the identifier for the entry in a predetermined manner; and

a number of pointers which point to portions of data in the database which correspond to the key for the entry;

wherein each key comprises a sequence of sub-word unit classifications which is derived from a corresponding sequence of sub-word units appearing in the database by classifying each of the sub-word units in the sequence into one of the plurality of sub-word unit classes;

a classifier operable to classify each of the sub-word units in the input query into one of the plurality of sub-word unit classes and to define one or more sub-sequences of query sub-word unit classifications;

a determiner operable to determine a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query sub-word unit classifications;

a comparator operable to compare the key associated with each of the determined identifiers determined by said determiner with the corresponding sub-sequence of query sub-word unit classifications; and

a retriever operable to retrieve one or more pointers from the index in accordance with the output of said comparator, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.

33. An apparatus according to claim 32 wherein the sub-word units are phonemes.

34. An apparatus according to claim 32 wherein at least ten sub-word unit classes are defined in advance.

35. An apparatus according to claim 32 wherein each key is related to the corresponding identifier by a predetermined mathematical function.

36. An apparatus according to claim 35, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{W}{\prod <br><br>}}<br><br>\left[C<br><br>\left[i\right]<br><br>K_c\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and W is the number of sub-word unit classifications in each key.

37. An apparatus according to claim 35, wherein each key is related to the corresponding identifier by the following equation:

$\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>K_c^{\left(n-i\right)}·<br><br>C<br><br>\left[i\right]\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>S$

where K_c is the number of sub-word unit classes, S is the number of entries in the index, C is the number of the sub-word class to which the i^th sub-word unit in the sequence of sub-word units corresponding to the key belongs, and n is the number of sub-word unit classifications in each key.

38. An apparatus according to claim 35, wherein said determiner is operable to determine a corresponding identifier for each subsequence of query sub-word unit classifications using the predetermined mathematical function.

39. An apparatus according to claim 32, wherein said determiner is operable to identify a new identifier for another entry in the index for a subsequence of query sub-word unit classifications if said comparator determines that the key for the identifier is not the same as the subsequence of query sub-word unit classifications.

40. An apparatus according to claim 39, wherein said determiner is operable to determine a new identifier using the following equation:

IDX=[IDX+V]Mod S,

where IDX is the identifier, S is the number of entries in the index, and V is a predetermined number.

41. An apparatus according to claim 32, wherein the key for one or more of the entries is a null key indicating that there are no pointers stored in the index for that entry.

42. An apparatus according to claim 32, wherein the input query is a typed query and said apparatus further comprises a converter operable to convert the typed query into the sequence of sub-word units.

43. An apparatus according to claim 32, wherein the input query is a spoken query and said apparatus further comprises a speech recognition system operable to process the spoken query and to output the sequence of sub-word units.

44. An apparatus for searching a database in response to a query input by a user, the database comprising a plurality of sequences of sub-word units and the query comprising at least one sequence of sub-word units, said apparatus comprising:

an apparatus according to claim 32 operable to identify one or more portions of data in the database for comparison with the input query; and

a sequence comparator operable to compare the one or more sequences of query sub-word units with the identified one or more portions of data in the database.

45. An apparatus according to claim 44, wherein said sequence comparator is operable to compare the input query with the portions of data in the database using a dynamic programming comparison technique.

46. An apparatus according to claim 44, further comprising a data file retriever operable to retrieve one or more data files in accordance with the results of said sequence comparator.

47. An apparatus for identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of features, said apparatus comprising:

a first memory operable to store data defining a plurality of feature classes, each class comprising features that are confusable with other features in the same class;

a second memory operable to store an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising;

a key associated with the entry and which is related to the identifier for to entry in a predetermined manner; and

a number of pointers which point to portions of data in the database which correspond to the key for the entry,

wherein each key comprises a sequence of feature classifications which is derived from a corresponding sequence of features appearing in the database by classifying each of the features in the sequence into one of the plurality of feature classes;

a classifier operable to classify each of the features in the input query into one of the plurality of feature classes and to define one or more sub-sequences of query feature classifications;

a determiner operable to determine a corresponding identifier for an entry in said index for each of said one or more sub-sequences of query feature classifications;

a comparator operable to compare the key associated with each of the determined identifiers determined by said determiner with the corresponding sub-sequence of query feature classifications; and

a retriever operable to retrieve one or more pointers from the index in accordance with the output of said comparator, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.

48. A storage medium storing computer readable program code for executing a method of controlling a processor to identify one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of sub-word units, said program code comprising:

code for storing data defining a plurality of sub-word unit classes, each class comprising sub-word units that are confusable with other sub-word units in the same class;

code for storing an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising;

a key associated with the entry and which is related to the identifier for the entry in a predetermined manner, and

a number of pointers which point to portions of data in the database which correspond to the key for the entry,

wherein each key comprises a sequence of sub-word unit classifications which is derived from a corresponding sequence of sub-word units appearing in the database by classifying each of the sub-word units in the sequence into one of the plurality of sub-word unit classes;

code for classifying each of the sub-word units in the input query into one of the plurality of sub-word unit classes and defining one or more sub-sequences of query sub-word unit classifications;

code for determining a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query sub-word unit classifications;

code for comparing the key associated with each of the determined identifiers determined by said determining code with the corresponding sub-sequence of query sub-word unit classifications; and

code for retrieving one or more pointers from the index in accordance with the output by said comparing code, which one or more pointers identify the one or more portion of data in the database for comparison with the input query.