System, method and apparatus for conducting a keyterm search

• US 20030078913A1
• Filed: 03/02/2001
• Published: 04/24/2003
• Est. Priority Date: 03/02/2001
• Status: Active Grant

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: The United States of America As Represented By The Secretary of Agriculture
• Inventors: McGreevy, Michael W.
• Granted Patent: US 6,823,333 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A keyterm search is a method of searching a database for subsets of the database that are relevant to an input query. First, a number of relational models of subsets of a database are provided. A query is then input. The query can include one or more keyterms. Next, a gleaning model of the query is created. The gleaning model of the query is then compared to each one of the relational models of subsets of the database. The identifiers of the relevant subsets are then output.

Claims

1. A method of searching a database comprising:

providing a plurality of relational models, each one of the plurality of relational models includes one relational model of one subset of a database;

inputting a first query;

creating a relational model of the first query;

comparing the relational model of the first query to each one of the plurality of relational models of the subsets; and

outputting a first plurality of identifiers of the subsets relevant to the first query.

2. The method as recited in claim 1 wherein, each one of the plurality of relational models of subsets of the database includes a plurality of relations.

3. The method as recited in claim 2 wherein, each one of the plurality of relations has a term pair and a plurality of types of relational summation metrics (RSM).

4. The method as recited in claim 3 wherein, an order of the plurality of types of RSMs corresponds to an order of the term pair.

5. The method as recited in claim 3, further comprising, providing a plurality of stopterms.

6. The method as recited in claim 5 wherein;

if either a first term in the term pair or a second term in the term pair is one of the plurality of stopterms then the relation is not included in the relational model of the subset.

7. The method as recited in claim 3 wherein, each one of the plurality of types of RSM includes a summation of the corresponding types of relational metrics of each one of a plurality of occurrences of the term pair within a context window within the subset.

8. The method as recited in claim 7 wherein, the types of relational metrics include a non-directional contextual metric (NDCM).

9. The method as recited in claim 8 wherein:

the value of the NDCM for a single occurrence of a term pair (T1, T2) in the subset is NDCM(T1, T2)=C−

1−

N, wherein;

T1 is a first term in the term pair;

T2 is a second term in the term pair;

C is equal to a number of terms in the context window; and

N is equal to a number of terms occurring between T1 and T2.

10. The method as recited in claim 7 wherein, the types of relational metrics include a right contextual metric (RCM).

11. The method as recited in claim 10 wherein:

the RCM for a single occurrence of a term pair (T1, T2) in the subset is RCM(T1, T2), wherein;

T1 is a first term in the term pair;

T2 is a second term in the term pair;

RCM(T1, T2)=0, if T2 precedes T1; and

RCM(T1, T2)=C−

1−

N, if T1 precedes T2, wherein

C is equal to a number of terms in the context window; and

N is equal to a number of terms occurring between T1 and T2.

12. The method as recited in claim 7 wherein, the types of relational metrics include a left contextual metric (LCM).

13. The method as recited in claim 12 wherein:

the LCM for a single occurrence of a term pair (T1, T2) in the subset is LCM(T1, T2), wherein;

T1 is a first term in the term pair;

T2 is a second term in the term pair;

LCM(T1, T2)=0, if T2 follows T1; and

LCM(T1, T2)=C−

1−

N, if T1 follows T2, wherein;

C is equal to a number of terms in the context window; and

N is equal to a number of terms occurring between T1 and T2.

14. The method as recited in claim 7 wherein, the types of relational metrics include a directional contextual metric (DCM).

15. The method as recited in claim 14 wherein:

the DCM for a single occurrence of a term pair (T1, T2) in the subset is DCM(T1, T2), wherein;

T1 is a first term in the term pair;

T2 is a second term in the term pair; and

DCM(T1, T2)=RCM(T1, T2)−

LCM(T1, T2), wherein;

RCM(T1, T2) is a right contextual metric for the single occurrence of a term pair (T1, T2) in the subset;

LCM(T1, T2) is a left contextual metric for the single occurrence of a term pair (T1, T2) in the subset; and

RCM(T1, T2)≧

LCM(T1, T2)

16. The method as recited in claim 7 wherein, the types of relational metrics include a scaled frequency metric (SFM).

17. The method as recited in claim 16 wherein:

SFM=[C−

1−

N]*{[2F_M−

F₁−

F₂]/2F_M}, wherein;

C is equal to a number of terms in the context window;

N is equal to a number of terms occurring between a first term and a second term of the term pair;

F_M is equal to a frequency of occurrences of a most frequent term in the database;

F₁ is equal to a frequency of occurrences of the first term of the term pair in the database; and

F₂ is equal to a frequency of occurrences of the second term of the term pair in the database.

18. The method as recited in claim 16 wherein, the scaled frequency metric of the term pair is equal to the product of [F_M−

F₁] divided by F_M, wherein, F_M is equal to a frequency of occurrences of a most frequent term in the database, and F₁ is equal to a frequency of occurrences of the first term of the term pair in the subset.

19. The method as recited in claim 7 wherein, the context window includes a number of terms equal to a function of an average sentence length.

20. The method as recited in claim 7 wherein, the context window includes a number of terms equal to a function of an average paragraph length.

21. The method as recited in claim 7 wherein, the context window includes a number of terms equal to a pre-selected number.

22. The method as recited in claim 7 further comprising:

selecting a relation threshold value for a selected one of the plurality of types of RSMs; and

eliminating all relations having a value of the selected type of RSM less than the relation threshold value.

23. The method as recited in claim 7 further comprising:

selecting one of the plurality of types of RSMs;

selecting a pre-selected number of relations having a greatest value of the selected type of RSM from each one of the plurality of relational models of the subsets.

24. The method as recited in claim 1 wherein, each one of the plurality of identifiers of subsets corresponds to one of the plurality of subsets of the database.

25. The method as recited in claim 1 wherein, the database includes at least one of a group consisting of:

text, narratives, reports, literature, punctuation, messages, electronic mail, internet text, web site information, linguistic patterns, grammatical tags, alphabetic data, alphabetic strings, numeric data, numeric strings, alphanumeric data, alphanumeric strings, sound, music, voice, audio data, audio encoding, vocal encoding, biological information, biological data, biological representations, biological analogs, medical information, medical data, medical representations, medical sequences, medical patterns, genetic sequences, genetic representations, genetic analogs, protein sequences, protein representations, protein analogs, computer software, computer hardware, computer firmware, computer input, computer internal information, computer output, computer representations, computer analogs, sequential symbols, sequential data, sequential items, sequential objects, sequential events, sequential causes, sequential time spans, sequential actions, sequential attributes, sequential entities, sequential relations, sequential representations, patterned symbols, patterned data, patterned items, patterned objects, patterned events, patterned causes, patterned time spans, patterned actions, patterned attributes, patterned entities, patterned relations, and patterned representations.

26. The method as recited in claim 1 wherein, inputting a first query includes transforming the first query.

27. The method as recited in claim 26 wherein, transforming the first query includes at least one of a group consisting of:

not changing the first query; and

replacing a portion of the first query with an alternate portion.

28. The method as recited in claim 27 wherein, the alternate portion is cross-referenced to the portion of the first query in a look-up table.

29. The method as recited in claim 28 wherein, the look-up table comprises:

a plurality of non-empty hash chains, wherein each one of the plurality of non-empty hash chains corresponds to a first section of the portion of the first query and each one of the plurality of non-empty hash chains has a plurality of phrases beginning with the first section of the portion of the first query; and

a plurality of alternate portions, wherein each one of the plurality of alternate portions corresponds to one of the plurality of phrases.

30. The method as recited in claim 1 wherein, providing a plurality of relational models includes transforming each one of the plurality of subsets of the database.

31. The method as recited in claim 1 wherein, creating a relational model of the first query includes expanding the first query.

32. The method as recited in claim 31 wherein, expanding the first query has the process of:

comparing the first query to each one of the plurality of models of the subsets of the database;

extracting a plurality of matching relations from the models of the subsets of the database wherein each one of the matching relations comprises;

a term pair consisting of;

a term matching a term in the first query; and

a related term; and

a plurality of types of RSMs wherein each one of the plurality of types of RSMs includes a summation of a corresponding type of relational metric of each one of a plurality of occurrences of the term pair within the subset.

33. The method as recited in claim 32 wherein, the term matching a term in the first query includes at least one of a group consisting of:

a term that is identical to at least one term in the first query; and

a term that contains at least one term in the first query.

34. The method as recited in claim 32 further has, the process of reducing the plurality of matching relations to a plurality of unique relations.

35. The method as recited in claim 34 wherein, reducing the plurality of matching relations to a plurality of unique relations comprises:

selecting one of the plurality of matching relations; and

determining if a term pair from the selected matching relation is included in one of the plurality of unique relations;

if the term pair is not included in one of the plurality of unique relations, then including the matching relation among the plurality of unique relations; and

if the term pair is included in one of the plurality of unique relations, then comparing a first order of the term pair in the selected matching relation and a second order of the term pair in the unique relation;

if the first order and the second order are the same, then replacing the plurality of types of RSMs for the unique relation with a summation of the corresponding types of RSMs of the matching relation and the corresponding types of RSMs of the unique relation; and

if the first order and the second order are not the same;

reversing the order of the term pair in the matching relation;

exchanging a right directional RSM of the matching relation with a left directional RSM of the matching relation; and

replacing the plurality of types of RSMs for the unique relation with a summation of the corresponding types of RSMs of the matching relation and the corresponding types of RSMs of the unique relation having the term pair.

36. The method as recited in claim 35 wherein, reducing the plurality of matching relations further comprises eliminating each one of the plurality of matching relations having a corresponding type of RSM<

V_T, wherein V_T is a threshold value.

37. The method as recited in claim 35 wherein, reducing the plurality of matching relations further comprises:

extracting matching relations from a pre-selected quantity of relational models; and

eliminating each one of the plurality of matching relations having a corresponding type of RSM<

V_T, wherein V_T is a threshold value.

38. The method as recited in claim 35 wherein, reducing the plurality of matching relations further comprises:

eliminating each one of the plurality of matching relations having a corresponding type of RSM<

V_T, wherein V_T is a threshold value; and

selecting a pre-selected quantity of matching relations having a greatest value of the corresponding type of RSM.

39. The method as recited in claim 32 further has, determining a typical order of the term pair for each one of the plurality of matching relations.

40. The method as recited in claim 39 wherein, determining a typical order of the term pair for each one of the plurality of matching relations comprises:

comparing a magnitude of an RCM of the matching relation to a magnitude of an LCM of the matching relation;

if the RCM is larger than the LCM, then the term pair of the matching relation is in the typical order;

if the LCM is larger than the RCM, then reverse the order of the term pair in the matching relation and exchange the value of the RCM and the value of the LCM.

41. The method as recited in claim 32 further has, sorting the plurality of unique relations in order of prominence, wherein prominence is equal to a magnitude of the selected metric.

42. The method as recited in claim 1 wherein, comparing the relational model of the first query includes:

determining a plurality of first relevance metrics for a first one of the plurality of relational models of the subsets comprising;

determining an intersection model of the relational model of the first query and a first one of the plurality of relational models of the subsets including;

determining a plurality of intersection relations, wherein each one of the plurality of intersection relations has;

a shared term pair, wherein a shared term pair includes a term pair present in at least one relation in each one of the first query relational models and the first one of the plurality of the relational models of the subsets; and

a plurality of intersection metrics (IM) wherein, each one of the plurality of IM=fct(RSM_Q, RSM_S1), wherein;

RSM_Q1 is a type of relational summation metric in the relational model of the first query; and

RSM_S1 is a corresponding type of relational summation metric in the relational model of the first one of the plurality of relational models of the subsets; and

calculating a first relevance metric for each type of RSM equal to a summation of the plurality of corresponding IMs of all intersection relations; and

determining a subsequent plurality of first relevance metrics corresponding to each subsequent one of the plurality of relational models of the subsets.

43. The method as recited in claim 42 wherein, the fct(RSM_Q1, RSM_S1)=[ln RSM_Q1]*[ln RSM_S1], and RSM_Q1≧

1, and RSM_S1≧

1.

44. The method as recited in claim 42 wherein, the fct(RSM_Q1, RSM_S1)=[RSM_Q1]*[RSM_S1].

45. The method as recited in claim 42 wherein, a scale factor is applied to the fct(RSM_Q1, RSM_S1).

46. The method as recited in claim 42 wherein, determining an intersection model further has:

applying a scaling factor to the summation of the plurality of corresponding IMs.

47. The method as recited in claim 46 wherein, the scaling factor is a subset emphasis factor (SEF)=S_S/R, wherein S_S is equal to a sum of a selected type of relational metric from the subset for all shared relations and R is equal to a sum of the selected type of relational metric in the subset.

48. The method as recited in claim 46 wherein, the scaling factor is a query emphasis factor (QEF)=S_Q/Q, wherein S_Q is equal to a sum of a selected type of relational metric from the query for all shared relations and Q is equal to a sum of the selected type of relational metric in the relevance model of the first query.

49. The method as recited in claim 46 wherein, the scaling factor is a length emphasis factor (LEF)=L_s/T wherein L_s is equal to a number of terms in the subset and T is equal to a number greater than a number of terms in a largest subset of the database.

50. The method as recited in claim 46 wherein, the scaling factor is an alternate length emphasis factor (LEF_alt)=L_cap/T wherein L_cap is equal to the lesser of either a number of terms in the subset or an average number of terms in each one of the plurality of subsets, and T is equal to a number greater than a number of terms in a largest subset of the database.

51. The method as recited in claim 42 wherein, outputting a plurality of identifiers of subsets relevant to the first query includes:

outputting a plurality of types of relevance metrics corresponding to each one of the plurality of subsets;

selecting one of the plurality of types of relevance metrics;

sorting the plurality of identifiers of subsets in order of magnitude of the selected type of relevance metric; and

outputting the plurality of identifiers of subsets in order of magnitude of the selected type of relevance metric.

52. The method as recited in claim 51 wherein, the selected one of the plurality of the types of relevance metrics includes at least one of a group consisting of:

a combination of types of relevance metrics;

a weighted sum of types of relevance metrics; and

a weighted product of types of relevance metrics.

53. The method as recited in claim 51 further including, normalizing each one of the plurality of corresponding intersection metrics of all intersection relations.

54. The method as recited in claim 51 further including, outputting the relational model of the first query.

55. The method as recited in claim 51 further including, displaying a pre-selected number of subsets in order of magnitude of the selected type of relevance metric.

56. The method as recited in claim 55 further including, highlighting a plurality of shared term pairs in each one of the plurality of subsets, wherein the terms within each one of the plurality of shared term pairs, occur within a context window.

57. The method as recited in claim 56 wherein, the plurality of shared term pairs consists of a plurality of shared term pairs having a greatest magnitude of the selected type of relevance metric.

58. The method as recited in claim 51 further including, displaying a plurality of shared term pairs in each one of the plurality of subsets, wherein the terms within each one of the plurality of shared term pairs, occur within a context window.

59. The method as recited in claim 58 further including, for each one of the plurality of shared term pairs, displaying an NDCM_Q1, and NDCM_S1 and a product equal to S*[ln |NDCM_Q1|]*[ln NDCM_S1], wherein:

the NDCM_Q1 is equal to a non-directional contextual metric of the shared term pair in the query;

the NDCM_S1 is equal to a non-directional contextual metric of the shared term pair in the subset;

the NDCM_S1>

1;

the |NDCM_Q1|>

1;

S=1 if NDCM_Q1>

1; and

S=−

1if NDCM_Q1<

−

1.

60. The method as recited in claim 58 further including, for each one of the plurality of shared term pairs, displaying an NDCM_Q1, and NDCM_S1 and a product equal to [ln NDCM_Q1]*[ln NDCM_S1], wherein:

the NDCM_Q1 is equal to a non-directional contextual metric of the shared term pair in the query;

the NDCM_S1 is equal to a non-directional contextual metric of the shared term pair in the subset;

the NDCM_S1>

1; and

the NDCM_Q1>

1.

61. The method as recited in claim 58 wherein, the plurality of shared term pairs consists of a plurality of shared term pairs having a greatest magnitude of a selected type of relevance metric.

62. The method as recited in claim 42 further including:

inputting a second query;

creating a relational model of the second query;

comparing the relational model of the second query to each one of the plurality of relational models of the subsets;

outputting a second plurality of identifiers of the subsets relevant to the second query; and

combining a second plurality of relevance metrics for the second query with the plurality of relevance metrics for the first query.

63. A method as recited in claim 62 further including, determining a third plurality of identifiers of the subsets consisting of identifiers of the subsets present in both the first and second pluralities of subsets, wherein the combined relevance metric for each one of the identifiers of the subsets that are present in both the first plurality of identifiers of the subsets and the second plurality of identifiers of the subsets is greater than zero.

64. A method as recited in claim 63 wherein, combining includes calculating a product of a first type of first relevance metric and a first type of a second relevance metric.

65. A method as recited in claim 62 further including, determining a third plurality of identifiers of the subsets consisting of identifiers of the subsets present in either the first or the second plurality of subsets, or both, wherein the combined relevance metric for each one of the identifiers of the subsets in the first plurality of identifiers of the subsets, or the second plurality of identifiers of the subsets, or both, is greater than zero.

66. A method as recited in claim 65 wherein, combining includes calculating a summation of a first type of first relevance metric and a first type of a second relevance metric.

69. The method as recited in claim 57 further comprising, outputting a representation of the model based on the query.

71. The method as recited in claim 58 further comprising, outputting a representation of the model of the database.

67. A method of searching a database comprising:

providing a plurality of relational models, each one of the plurality of relational models includes one relational model of one subset of a database;

inputting a first query;

creating a relational model of the first query, wherein creating a relational model of the first query includes expanding the first query having a process of;

comparing the first query to each one of the plurality of models of the subsets of the database;

extracting a plurality of matching relations from the models of the subsets of the database wherein each one of the matching relations comprises;

a term pair consisting of;

a term matching a term in the first query, wherein the term matching the term in the first query includes at least one of a group consisting of;

a term that is identical to at least one term in the first query; and

a term that contains at least one term in the first query; and

a related term; and

a plurality of types of relational summation metrics (RSMs) wherein, each one of the plurality of types of RSMs includes a summation of the corresponding type of relational metrics of each one of a plurality of occurrences of the term pair within the subset;

comparing the relational model of the first query to each one of the plurality of relational models of the subsets; and

outputting a first plurality of identifiers of the subsets relevant to the first query.

68. A method of producing a model based on a query comprising:

providing a plurality of relational models, each one of the plurality of relational models includes one relational model of one subset of a database;

inputting a query;

creating a relational model of the query, wherein creating a relational model of the query includes expanding the query having a process of;

comparing the query to each one of the plurality of models of the subsets of the database;

extracting a plurality of matching relations from the models of the subsets of the database wherein each one of the matching relations comprises;

a term pair consisting of;

a term matching a term in the first query, wherein the term matching the term in the first query includes at least one of a group consisting of;

a term that is identical to at least one term in the first query; and

a term that contains at least one term in the first query; and

a related term; and

a plurality of types of relational summation metrics (RSMs) wherein, each one of the plurality of types of RSMs includes a summation of the corresponding type of relational metrics of each one of a plurality of occurrences of the term pair within the subset; and

outputting a model based on the query.

70. A method of producing a model of a database comprising:

providing a database;

calculating a plurality of relations wherein, each one of the plurality of relations has a term pair and a plurality of types of relational summation metrics (RSMs), and wherein, each one of the plurality of RSMs includes a summation of the corresponding types of relational metrics of each one of a plurality of occurrences of the term pair within a context window within the database, wherein the types of relational metrics include;

a non-directional contextual metric;

a right contextual metric;

a left contextual metric; and

a directional contextual metric; and

outputting a model of the database.