| |
|
|
DATABASE OR FILE ACCESSING |
System, method and apparatus for conducting a phrase search6741981
Abstract
A phrase 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 sequences of terms. Next, a relational model of the query is created. The relational 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
What is claimed is:
1. A method of searching a database comprising:
providing a plurality of relational models wherein each of the plurality of relational models includes a relational model of at least one subset of a database and a plurality of relations, wherein each of the plurality of relations includes at least one subset term pair and a subset plurality of types of relational summation metrics (RSMs) that include a summation of values of the corresponding type of relational metric of occurrences of the at least one subset term pair within at least one context window within the at least one subset and includes at least one of a right contextual metric (RCM) and a left contextual metric (LCM);
inputting a first query for the database;
creating a relational model of the first query, wherein the relational model of the first query includes at least one first query relation, each of the first query relations having a first query term pair and a first query plurality of types of relational summation metrics;
comparing the relational model of the first query to each one of the plurality of relational models of the subsets; and
outputting at least one identifier of the subsets relevant to the first query.
2. The method as recited in claim 1, wherein, an order of said plurality of types of RSMs corresponds to an order of said term pair.
3. The method as recited in claim 1, further comprising, providing at least one stopterm.
4. The method as recited in claim 3, further comprising, when either a first term in said subset term pair or a second term in said subset term pair is one of said at least one stopterm, said relation is not included in said relational model of said at least one subset.
5. The method as recited in claim 3, further comprising, when a first stopterm is included in said first query, then the first stopterm is no longer included in said at least one stopterm.
6. The method as recited in claim 3, further comprising, when a first stopterm is included in said first query, said at least one stopterm no longer includes any stopterm.
7. The method as recited in claim 1, further comprising choosing said types of RSMs to include a non-directional contextual metric (NDCM).
8. The method as recited in claim 7, further comprising providing a value NDCM(T1, T2)=C-1-N of said NDCM for a single occurrence of a term pair (T1, T2) in said subset wherein:
T1 is a first term in said term pair;
T2 is a second term in said term pair;
C is equal to a number of terms in said context window; and
N is equal to a number of terms occurring between T1 and T2.
9. The method as recited in claim 1, further comprising
providing a value RCM(T1, T2) for said RCM for a single occurrence of a term pair (T1, T2) in said subset wherein:
T1 is a first term in the said term pair;
T2 is a second term in the said 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 said context window; and
N is equal to a number of terms occurring between T1 and T2.
10. The method as recited in claim 1, further comprising providing a value LCM(T1, T2) for said LCM for a single occurrence of a term pair (T1, T2) in said subset wherein:
T1 is a first term in said term pair;
T2 is a second term in said term pair;
LCM(T1, T2)=0, follows T1; and
LCM(T1, T2)=C-1-N, if T1 follows T2, wherein:
C is equal to a number of terms in said context window; and
N is equal to a number of terms occurring between T1 and T2.
11. The method as recited in claim 1, further comprising including in said types of relational metrics a directional contextual metric (DCM).
12. The method as recited in claim 11, further comprising providing at least one directional contextual metric (DCM) among said types of relational metrics, wherein:
the DCM for a single occurrence of a term pair (T1, T2) in the subset has a value DCM(T1, T2), wherein:
T1 is a first term in said term pair;
T2 is a second term in said term pair;
DCM(T1, T2)=RCM(T1, T2)-LCM(T1, T2), wherein:
RCM(T1, T2) is a right contextual metric for a single occurrence of said term pair (T1, T2) in said subset;
LCM(T1, T2) is a left contextual metric for a single occurrence of said term pair (T1, T2) in said subset; and
RCM(T1, T2).gtoreq.LCM(T1, T2).
13. The method as recited in claim 1, further comprising providing said context window having a window size that is a function of an average sentence length.
14. The method as recited in claim 1, further comprising providing said context window having a window size that is a function of an avenge paragraph length.
15. The method as recited in claim 1, further comprising providing said context window having a window size that is a pre-selected number of terms.
16. The method as recited in claim 1, further comprising:
providing a relation threshold value for a selected one of said subset plurality of types of RSMs; and
eliminating all relations having a value of said selected type of RSM less than the relation threshold value.
17. The method as recited in claim 1, further comprising:
selecting one of said subset plurality of types of RSMs; and
selecting a pre-selected number of relations having a greatest value of the selected type of RSM from at least one of the said plurality of relational models of said subsets.
18. The method as recited in claim 1, further comprising choosing said first query to include one or more query fields.
19. The method as recited in claim 18, further comprising creating a relational model of said first query by a process comprising:
creating one or more relational models of said one or more query fields wherein, each of said one or more relational models of said one or more query fields includes at least one relational model of one of said one or more query fields in the said first query, wherein each one of said one or more relational models of said one or more query fields has one or more relations; and p1 combining said one or more relational models of said one or more query fields in said first query into a first query relational model.
20. The method as recited in claim 1, further comprising providing one or more stopterms, wherein, if neither a first term in said first query term pair nor a second term in said first query term pair is one of the one or more stopterms said RSMs are increased.
21. The method as recited in claim 1, further comprising, providing one or more stopterms, wherein, if both a first term in said first query term pair and a second term in said first query term pair are included in the one or more stopterms said RSMs are decreased.
22. The method as recited in claim 1, further comprising, providing one or more stopterms, wherein, if either but not both a first term in said first query term pair and a second term in said first query term pair is one of the one or more stopterms said RSMs are unchanged.
23. The method as recited in claim 1, further comprising providing one or more emphasis terms, wherein, if neither a first term in said first query term pair nor a second term in said first query term pair is one of the one or more emphasis terms said RSMs are decreased.
24. The method as recited in claim 1, further comprising providing one or more emphasis terms, wherein, if both a first term in said first query term pair and a second term in said first query term pair are included in the one or more emphasis terms said RSMs are increased.
25. The method as recited in claim 1, further comprising providing one or more emphasis terms, wherein, if either but not both a first term in said first query term pair and a second term in said first query term pair is one of the one or more emphasis terms said RSMs are unchanged.
26. The method as recited in claim 1, further comprising:
providing one or more stop relations, wherein each of the stop relations includes a first term and a second term and a plurality of types of relational metrics; and
eliminating the one or more stop relations from the relational model of said first query.
27. The method as recited in claim 1, further comprising inputting said first query by a process comprising transforming the first query.
28. The method as recited in claim 27, transforming said first query by a process comprising at least one of a group process consisting of:
not changing said first query; and
replacing a selected portion of said first query with an alternate portion from a substitution list.
29. The method as recited in claim 28, further comprising cross referencing said alternate portion to said selected portion of said first query in a look-up table.
30. The method as recited in claim 29, further comprising choosing said look-up table to comprise[[s]]:
one or more non-empty hash chains, wherein each of the one or more non-empty bash chains corresponds to a first section of said selected portion of said first query and each of the one or more hash chains has one or more phrases, each phrase consisting of one or more of said terms, beginning with the first section of said selected portion of said first query; and
one or more alternate portions, wherein each one of the one or more alternate portions corresponds to one of the one or more phrases.
31. The method as recited in claim 1 further comprising choosing at least one identifier of said subsets to correspond to at least one subsets of said database.
32. The method as recited in claim 1 further comprising choosing said database to included 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 lime 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.
33. A method of searching a database comprising:
providing a plurality of relational models wherein each of the plurality of relational models includes one relational model of at least one subset of a database;
inputting a first query, having one or more query fields, for the database;
creating a relational model of the first query, wherein the relational model of the first query includes at least one relation, each relation having a first query term pair and a first query plurality of types of relational summation metrics, by a process comprising:
creating one or more relational models of the one or more query fields wherein each of said one or more relational models of the one or more query fields includes at least one relational model of one of the one or more query fields in the first query, wherein each of the one or more relational models of the one or more query fields has one or more relations; and
combining the one or more relational models of the one or more query fields in the first query into a first query relational model by a process comprising:
analyzing a first one of the one or more relational models of the one or more query fields including:
determining if a first relation from the first one of the one or more relational models of the one or more query fields is included in the first query model by a process comprising:
selecting a first relation from the first one of the one or more relational models of the one or more query fields, wherein the selected first relation includes a first term pair;
determining if the first term pair is included in one of the one or more relations in the first query model;
when the first term pair is not included in one of the one or more relations in the first query model, then including the selected first relation in the first query model; and
when the first term pair is included in one of the one or more relations in the first query model, comparing a first order of the first term pair in the selected first relation wit a second order of the first term pair in the relation from the first query model containing the first term pair;
when the first order and the second order are the same, combining a plurality of types of Relational Summation Metrics (RSMs) of the selected first relation in the first query field model, with a corresponding plurality of types of RSMs of the relation containing the first term pair in the first query model; and
when the first order and the second order are not the same,
reversing the order of the term pair in the selected first relation and exchanging a right directional RSM of the selected first relation with a left directional RSM of the selected first relation; and
combining a plurality of types of RSMs of the selected first relation in the first query field model, with a corresponding plurality of types of RSMs of the relation containing the first term pair in the first query model; and
determining if a subsequent relation from the first one of the one or more relational models of the one or more query fields is included in the first query model; and
analyzing a subsequent one of the one or more relational models of the one or more query fields; and
comparing the relational model of the first query to each one of the plurality of relational models of the subsets; and
calculating a plurality of first relevance metric values corresponding to each of the subsets; and
outputting at least one identifier of the subsets relevant to the first query.
34. The method as recited in claim 33, further comprising performing said process of combining said plurality of types of RSMs of said selected first relation in said query field model, with said corresponding plurality of types of RSMs of said relation containing said first term pair in said first query model by a process comprising:
selecting one of said plurality of types of RSMs;
selecting said relation from either of said first query field model or said first query model, wherein said selected relation has a greatest magnitude of said selected type of RSM; and
replacing said relation containing said first term pair in said first query model with the selected relation.
35. The method as recited in claim 33 further comprising selected one of said plurality of said types of said relevance metrics to include at least one of a group consisting of:
a combination of types of said relevance metrics;
a weighted sum of types of said relevance metrics; and
a weighted product of types of said relevance metrics.
36. The method as recited in claim 33, further comprising combining said plurality of type of RSMs of said selected first relation in said query field model, with said corresponding plurality of types of RSMs of said relation containing said first term pair in first query model includes:
calculating a summation of value of said corresponding plurality of types of RSMs from said relation containing the first term pair in both said first query field model and said first query model; and
replacing said plurality of types of RSMs for the relation containing said first term pair in said first query model with the summation of values of said corresponding plurality of types of RSMs.
37. The method as recited in claim 33, further comprising:
selecting at least one of said one or more query fields in said first query; and
assigning a weight to the selected query field, wherein each one of said plurality of types of RSMs corresponding to the selected query field is scaled by a factor determined by a weight.
38. A method of searching a database comprising:
providing a plurality of relational models wherein each of the plurality of relational models includes one relational model of at least one subset of a database
inputting a first query, having one or more query fields, for the database;
creating a relational model of the first query, wherein the relational model of the query includes at least one relation having a first query term pair and a first query plurality of types of relational summation metrics, by a process comprising:
creating one or more relational models of said one or more query fields wherein each of said one or more relational models of said one or more query fields includes at least one relational model of one of said one or more query fields in the first query, wherein each of said one or more relational models of said one or more query fields has one or more relations; and
calculating for each one of the one or more relations in each one of the one or more relational models of the one or more first query fields a summation of values of each of the corresponding types of the relational metrics of each one of one or more occurrences of a first query term pair within the query field, wherein, the plurality of types of the relational metrics include at least one of a non-directional contextual metric (NDCM), a right contextual metric (RCM), a left contextual metric (LCM), and a directional contextual metric (DCM); and
combining the one or more relational models of the one or more query fields in the first query into a first query relational model; and
comparing the relational model of the first query to each one of the plurality of relational models of the subsets; and
calculating a plurality of first relevance metric values corresponding to each of the subsets;
outputting at least one identifier of the subsets relevant to the first query.
39. A method of searching a database comprising:
providing a plurality of relational models wherein each of the plurality of relational models includes one relational model of at least one subset of a database;
inputting a first query, having one or more query fields, for the database;
creating a relational model of the first query, wherein the relational model of the first query includes at least one first query relation having a first query term pair and a first query plurality of types of relational summation metrics, by a process comprising:
creating one or more relational models of the one or more query fields wherein each of said one or more relational models of the one or more query fields includes at least one relational model of one of the one or more query fields in the first query, wherein each of the one or more relational models of the one or more query fields has one or more relations; and
combining the one or more relational models of the one or more query fields in the first query into a first query relational model;
comparing the relational model of the first query to each one of the plurality of relational models of the subsets by a process comprising:
calculating a plurality of first relevance metrics for a first one of said plurality of relational models of said subsets by a process comprising:
determining an intersection model of said relational model of said first query and a first one of said plurality of relational models of said subsets by a process comprising:
determining one or more intersection relations, wherein each of the intersection relations has:
a shared term pair that includes a term pair present in at least one relation in each one of said first query relational model and the first one of said plurality of the relational models of said subsets; and
a plurality of intersection metrics (IM), wherein each IM is a function fct(RSM.sub.Q1, RSM.sub.S1), wherein:
RSM.sub.Q1 is a type of Relational Summation Metric (RSM) in the relational model of said first query; and
RSM.sub.S1 is a corresponding type of said RSM in the relational model of the first one of said plurality of relational models of said subsets; and
calculating a first relevance metric for each of the plurality of types of said RSMs equal to a function 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 said plurality of relational models of said subsets; and
outputting a first list of one or more identifiers of the subsets relevant to the first query, wherein each identifier has a corresponding type of first relevance metric for each of the plurality of types of said RSM.
40. The method as recited in claim 39, wherein said process of determining said one or more intersection relations further comprises:
determining a first order of said shared term pair in said first query relational model and a second order of said shared term pair in said first one of said plurality of the relational models of said subsets; and
reversing the second order and exchanging an RCM and an LCM of the subset relation having said shared term pair in the first one of said plurality of the relational models of said subsets, when the first order and second order are not equal.
41. The method as recited in claim 39, further comprising choosing said function fct(RSM.sub.Q1, RSM.sub.S1)=(RSM.sub.Q1)*(RSM.sub.S1).
42. The method as recited in claim 39, further comprising applying a scale factor to said fct(RSM.sub.Q1, RSM.sub.S1).
43. The method as recited in claim 39, further comprising choosing said function of said plurality of corresponding IMs of all intersection relations to include a summation of said plurality of corresponding IMs of all intersection relations.
44. The method as recited in claim 39, further comprising choosing said function of said plurality of corresponding IMs of all intersection relations to include a summation of values of each of said plurality of types of RSM.sub.Q1 in all of said one or more first query relations having said shared term pair included in said one or more intersection relations.
45. The method as recited in claim 39, further comprising calculating said plurality of first relevance metrics for said first one of said plurality of relational models of said subsets by a process comprising assigning a zero relevance to the first one of the plurality of subsets if all term pairs of said relational model of said first query are not included in said relational model of the first subset.
46. The method as recited in claim 39, wherein determining said intersection model further comprises:
applying a scaling factor to said function of said plurality of corresponding intersection metrics.
47. The method as recited in claim 46, further comprising choosing said scaling factor to be a subset emphasis factor (SEF)=S.sub.S /R, wherein S.sub.S is equal to a summation of values of a selected said type of relational summation metric (RSM) from all subset relations having one of said shared term pairs in the first one of said plurality of relational models of said subsets and R is equal to a summation of values of the selected said type of relational summation metric (RSM) in all of said subset relations in the first one of said plurality of relational models of said subsets.
48. The method as recited in claim 46, further comprising choosing said scaling factor to be a query emphasis factor (QEF)=S.sub.Q /Q, wherein S.sub.Q is equal to a summation of values of a selected said type of relational summation metric (RSM) from all of said query relations having one of said shared term pairs in said relational model of the said first query and Q is equal to a summation of values of the selected said type of relational summation metric (RSM) in all of said query relations in said relational model of said first query.
49. The method as recited in claim 46, further comprising choosing said scaling factor to be a length emphasis factor (LEF)=L.sub.S /T, wherein L.sub.S is equal to a number of terms in said subset and T is equal to a number greater than a number of terms in a largest subset of said database.
50. The method as recited in claim 46, further comprising choosing said scaling factor to be an alternate length emphasis factor (LEF.sub.alt)=L.sub.cap /T, wherein, L.sub.cap is equal to the lesser of either a number of terms in said subset or an average number of terms in each one of said plurality of subsets, and T is equal to a number greater than a number of terms in a largest subset of said database.
51. The method as recited in claim 39, wherein outputting said at least one identifier of said subsets relevant to said first query comprises:
outputting a plurality of types of said relevance metrics corresponding to each of said subsets;
selecting one of said plurality of types of said relevance metrics; and
sorting identifiers of said subsets in order of magnitude of the selected one of said plurality of types of relevance metrics.
52. The method as recited in claim 51, further comprising choosing said selected one of said plurality of types of relevance metrics to include at least one of a group consisting of:
a combination of types of said relevance metrics;
a weighted sum of types of said relevance metrics; and
a weighted product of types of said relevance metrics.
53. The method as recited in claim 51, further comprising mormalizing each of said plurality of corresponding intersection metrics of all of said intersection relations.
54. The method as recited in claim 51, further comprising outputting said relational model of said first query.
55. The method as recited in claim 51, further comprising displaying a pre-selected number of said subsets in order of magnitude of said selected type of relevance metric.
56. The method as recited in claim 55, further comprising highlighting one or more said shared term pairs in each of said subsets relevant to said first query, wherein the terms within each of said one or more shared tern pairs, occur within at least one context window in the subset.
57. The method as recited in claim 56, further comprising choosing one or more of said shared term pairs to consist of said shared term pairs having a greatest magnitude of a selected type of said relevance metric.
58. The method as recited in claim 51, further comprising displaying one or more of said shared term pairs that are included in each one of said subsets relevant to said first query, wherein terms within each one of said one or more shared term pairs occur within at least one context window in the subset.
59. The method as recited in claim 58, further comprising determining a typical order of each of said shared term pairs by process comprising:
comparing a magnitude of an RCM of said shared term pair to a magnitude of an LCM of said shared term pair;
when the RCM is larger said shared term pair is in typical order;
when the LCM is larger, reverse an order of said shared term pair and exchange the RCM and the LCM.
60. The method as recited in claim 58, further comprising, for each one of said one or more shared term pairs, displaying a feedback metric of the query (FBM.sub.Q1) equal to a combination of an LCM.sub.Q1 and an RCM.sub.Q1 and displaying a feedback metric of a subset (FBM.sub.S1) equal to a combination of an LCM.sub.S1 and an RCM.sub.S1 and a product equal to wherein the LCM.sub.Q1 is equal to a left contextual metric of said shared term pair in said query, the RCM.sub.Q1 is equal to a right contextual metric of said shared term pair in said query, LCM.sub.S1 is equal to a left contextual metric of said shared term pair in said subset and the RCM.sub.S1 is equal to a right contextual metric of said shared term pair in said subset.
61. The method as recited in claim 58, further comprising choosing said plurality of said shared term pairs to consist of one or more of said shared term pairs having a greatest magnitude of a selected type of said relevance metric.
62. The method as recited in claim 39, further comprising:
inputting a second query;
creating a relational model of the second query;
comparing the relational model of the second query to each one of said plurality of relational models of said subsets;
outputting a second list of one or more identifier of said subsets relevant to the second query; and
determining a plurality of combined relevance metric values by combining, for each of said types of RSM, values of a second plurality of said relevance metrics for the second query with values of said first plurality of relevance metrics for said first query.
63. A method as recited in claim 62, further comprising determining a third list of one or more identifiers of said subsets to consist of at least one identifier of said subsets present in both of said first and second lists of one or more identifiers of said subsets, wherein, for a selected one of said types of RSM, said combined relevance metric values are greater than zero for each of the identifiers included in the third list of identifiers.
64. A method as recited in claim 63 further comprising computing at least one of said combined relevance metric values by a process comprising calculating a product of values 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 comprising determining a third list of one or more identifiers of said subsets to consist of at least one identifier of said subsets present in either or both of said first and second lists of one or more identifiers of said subsets, wherein, for a selected one of said types of RSM, said combined relevance metric values are greater than zero for each of the identifiers included in the third list of identifiers.
66. A method as recited in claim 65, further comprising computing at least one of said combined relevance metric values by a process comprising calculating a summation of values of a first type of first relevance metric and a first type of a second relevance metric.
Description
FIELD OF THE INVENTION
The present invention relates to relational analysis and representation, database information retrieval and search engine technology and, more specifically, a system and method of analyzing data in context.
BACKGROUND OF THE INVENTION
The vast amount of text and other types of information available in electronic form have contributed substantially to an "information glut." In response, researchers are creating a variety of methods to address the need to efficiently access electronically stored information. Current methods are typically based on finding and exploiting patterns in collections of text. Variations among the methods and the factions are primarily due to varying allegiances to linguistics, quantitative analysis, representations of domain expertise, and the practical demands of the applications. Typical applications involve finding items of interest from large collections of text, having appropriate items routed to the correct people, and condensing the contents of many documents into a summary form.
One known application includes various forms of, and attempts to improve upon, keyword search type technologies. These improvements include statistical analysis and analysis based upon grammar or parts of speech. Statistical analysis generally relies upon the concept that common or often-repeated terms are of greater importance than less common or rarely used terms. Parts of speech attach importance to different terms based upon whether the term is a noun, verb, pronoun, adverb, adjective, article, etc. Typically a noun would have more importance than an article therefore nouns would be processed where articles would be ignored.
Other known methods of processing electronic information include various methods of retrieving text documents. One example is the work of Hawking, D. A. and Thistlewaite, P. B.: Proximity Operators--So Near And Yet So Far. In D. K. Harman, (ed.) Proc. Fourth Text Retrieval Conf. (TREC), pp 131-144, NIST Special Publication 500-236, 1996. Hawking, D. A. and Thistlewaite, P. B.: Relevance Weighting Using Distance Between Term Occurrences. Technical Report TR-CS-96-08, Department of Computer Science, Australian National University, June 1996 (Hawking and Thistlewaite (1995, 1996)) on the PADRE system.
The PADRE system applies complex proximity metrics to determine the relevance of documents. PADRE measures the spans of text that contain clusters of any number of target words. Thus, PADRE is based on complex, multi-way ("N-ary") relations. PADRE's spans and clusters have complex, non-intuitive, and somewhat arbitrary definitions. Each use of PADRE to rank documents requires a user to manually select and specify a small group of words that might be closely clustered in the text. PADRE relevance criteria are based on the assumption that the greatest relevance is achieved when all of the target words are closest to each other. PADRE relevance criteria are generated manually, by the user's own "human free association." PADRE, therefore, is imprecise and often generates inaccurate search/comparison results.
Other prior art methods include various methodologies of data mining. See for example: Fayyad, U.; Piatetsky-Shapiro, G.; and Smyth, P: The KDD Process for Extracting Useful Knowledge from Volumes of Data. Comm. ACM, vol. 39, no. 11, 1996, pp. 27-34 (Fayyad, et al., 1996). Search engines Zorn, P.; Emanoil, M.; Marshall, L; and Panek, M.: Advanced Web Searching: Tricks of the Trade. ONLINE, vol. 20, no. 3, 1996, pp. 14-28, (Zorn, et al., 1996). Discourse analysis Kitani, T.; Eriguchi, Y.; and Hara, M.: Pattern Matching and Discourse Processing in Information Extraction from Japanese Text. JAIR, vol. 2, 1994, pp. 89-100, (Kitani, et al., 1994). Information extraction Cowie, J. and Lehnert, W.: Information Extraction. Comm. ACM, vol. 39, no. 1, 1996, pp. 81-91, (Cowie, et al., 1996). Information filtering Foltz, P. W. and Dumais, S. T.: Personalized Information Delivery--An Analysis of Information Filtering Methods. Comm. ACM, vol. 35, no. 12, 1992, pp. 51-60, (Foltz, et al., 1992). Information retrieval Salton, G.: Developments in Automatic Text Retrieval, Science, vol. 253, 1991, pp. 974-980, (Salton Developments . . . 1991) and digital libraries Fox, E. A.; Akscyn, R. M.; Furuta, R. K.; and Leggett, J. J.: Digital Libraries--Introduction. Comm. ACM., vol. 38, no. 4, pp. 22-28, 1995 (Fox, et al. 1995). Cutting across these approaches are concerns about how to subdivide words and collections of words into useful pieces, how to categorize the pieces, how to detect and utilize various relations among the pieces, and how transform the many pieces into a smaller number of representative pieces.
Most keyword search methods use term indexing such as used by Salton, G.: A blueprint for automatic indexing. ACM SIGIR Forum, vol. 16, no. 2, 1981. Reprinted in ACM SIGIR Forum, vol. 31, no. 1, 1997, pp. 23-36. (Salton, A blueprint . . . 1981), where a word list represents each document and internal query. As a consequence, given a keyword as a user query, these methods use merely the presence of the keyword in documents as the main criterion of relevance. Some methods such as Jing, Y. and Croft, W. B.: An Association Thesaurus for Information Retrieval. Technical Report 94-17, University of Massachusetts, 1994 (Jing and Croft, 1994); Gauch, S., and Wang, J.: Corpus analysis for TREC 5 query expansion. Proc. TREC 5, NIST SP 500-238, 1996, pp. 537-547 (Gauch & Wang, 1996); Xu, J., and Croft, W.: Query expansion using local and global document analysis. Proc. ACM SIGIR, 1996, pp. 4-11. (Xu and Croft, 1996); McDonald, J., Ogden, W., and Foltz, P.: Interactive information retrieval using term relationship networks. Proc. TREC 6, NIST SP 500-240, 1997, pp. 379-383 (McDonald, Ogden, and Foltz, 1997), utilize term associations to identify or display additional query keywords that are associated with the user-supplied keywords. This results in, "query drift". Query drift occurs when the additional query keywords retrieve documents that are poorly related or unrelated to the original keywords. Further, term index methods are ineffective in ranking documents on the basis of keywords in context.
In the proximity indexing method of Hawking and Thistlewaite (1996, 1996), a query consists of a user-identified collection of words. These query words are compared with the words in the documents of the database. The search method seeks documents containing length-limited sequences of words that contain subsets of the query words. Documents containing greater numbers of query words in shorter sequences of words are considered to have greater relevance. Further, as with other conventional term indexing schemes, the method of Hawking et al. allows a single query term to be used to identify documents containing the term, but cannot rank the identified documents containing the single query term according to the relevance of the documents to the contexts of the single query term within each document.
Most phrase search and retrieval methods that currently exist, such as Fagan, J. L.: Experiments in automatic phrase indexing for document retrieval: A comparison of syntactic and non-syntactic methods. Ph.D. thesis TR87-868, Department of Computer Science, Cornell University, 1987 (Fagan (1987)); Croft, W. B., Turtle, H. R., and Lewis, D. D.: The use of phrases and structure queries in information retrieval. Proc. ACM SIGIR, 1991, pp. 32-45 (Croft, Turtle, and Lewis (1991)); Gey, F. C., and Chen, A.: Phrase discovery for English and cross-language retrieval at TREC 6. Proc. TREC 6, NIST SP 500-240, 1997, pp. 637-644 (Gey and Chen (1997); Gutwin, C., Paynter, G., Witten, I. H., Nevill-Manning, C., and Frank E.: Improving browsing in digital libraries with keyphrase indexes. TR 98-1, Computer Science Department, University of Saskatchewan, 1998 (Gutwin, Paynter, Witten, Nevill-Manning, and Frank (1998)); Jones, S., and Stavely, M.: Phrasier: A system for interactive document retrieval using keyphrases. Proc. ACM SIGIR, 1999, pp. 160-167 (Jones and Staveley (1999)), and Jing and Croft (1994) all treat query phrases as single terms, and typically rely on lists of key phrases that have been generated at some previous time, to represent each document. This approach allows little flexibility in matching query phrases with similar phrases in the text, and this approach requires that all possible phrases be identified in advance, typically using statistical or "natural language processing" (NLP) methods.
NLP phrase search methods are subject to problems such as mistagging, as described by Fagan (1987). Statistical phrase search methods, such as in Turpin, A., and Moffat, A.: Statistical phrases for vector-space information retrieval. Proc. ACM SIGIR, 1999, pp. 309-310 (Turpin and Moffat (1999)), depend on phrase frequency, and therefore are ineffective in searching for most phrases because most phrases occur infrequently. Croft, Turtle, and Lewis (1991) also dismisses the concept of implicitly representing phrases as term associations. Further, the pair-wise association metric of Croft, Turtle, and Lewis (1991) does not include or suggest a measurement of degree or direction of word proximity. Instead, the association method of Croft, Turtle, and Lewis (1991) uses entire documents as the contextual scope, and considers any two words that occur in the same document as being related to the same extent that any other pair of words in the document are related.
There are several methods of displaying phrases contained in collections of text as a way to assist a user in domain analysis or query formulation and refinement. Known methods such as Godby, C. J.: Two techniques for the identification of phrases in full text. Annual Review of OCLC Research. Online Computer Library Center, Dublin, Ohio, 1994 (Godby (1994)); Normore, L., Bendig, M., and Godby, C. J.: WordView: Understanding words in context. Proc. Intell. User Interf., 1999, pp. 194 (Normore, Bendig, and Godby (1999)); Zamir, E., and Etzioni, E.: Grouper: A dynamic clustering interface to web search results. Proc. 8.sup.th International World Wide Web Conference (WWW8), 1999 (Zamir and Etzioni, (1999)); Gutwin, Paynter, Witten, Nevill-Manning, and Frank (1998); and Jones and Staveley (1999), maintain explicit and incomplete lists of phrases. Some phrase generation methods such as Church, K., Gale, W., Hanks, P., and Hindle, D.: Using statistics in lexical analysis. In U. Zemik (ed.), Lexical Acquisition: Using On-Line Resources To Build A Lexicon. Lawrence Earlbaum, Hillsdale, N.J., 1991 (Church, Gale, Hanks, and Hindle (1991)); Gey and Chen (1997); and Godby (1994), use contextual association to identify important word pairs, but do not identify longer phrases, or do not use the same associative method to identify phrases having more than two words. Some known methods such as Gelbart, D., and Smith, J. C.: Beyond boolean search: FLEXICON, a legal text-based intelligent system. Proc. ACM Artificial Intelligence & Law, 1991, pp. 225-234 (Gelbart and Smith (1991)); Gutwin, Paynter, Witten, Nevill-Manning, and Frank (1998); and Jones and Staveley (1999) rely on manual identification of phrases at a critical point in the process.
The "natural language processing" (NLP) methods such as Godby (1994); Jing and Croft (1994); Gutwin, Paynter, Witten, Nevill-Manning, and Frank (1998); Jones and Staveley (1999); and de Lima, E. F., and Pedersen, J. O.: Phrase recognition and expansion for short, precision-biased queries based on a query log. Proc. ACM SIGIR, 1999, pp. 145-152 (de Lima and Pedersen (1999)), classify words by part of speech using grammatical taggers and apply a grammar-based set of allowable patterns. These methods typically remove all punctuation and stopwords as a preliminary step, and most then discover only simple or compound nouns leaving all other phrases unrecognizable.
Keyphind and Phrasier methods of Gutwin, Paynter, Witten, Nevill-Manning, and Frank (1998) and Jones and Staveley (1999), identify some of the phrases in sets of documents that are relevant to initial user queries, and require users to select among the identified phrases to refine subsequent searches. Keyphind and Phrasier then rely on Natural Language Processing (NLP) methods of grammatical tagging and require pre-existing lists of identifiable phrases. In addition, Keyphind and Phrasier apply very restrictive limits on usable phrases, which significantly reduces the number and types of phrases that can be identified in documents. Keyphind and Phrasier's methods restrict the amount of phrase information available for determinations of document relevance.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, a phrase 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 sequences of terms. Next, a relational model of the query is created. The relational 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.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements.
FIG. 1 illustrates one embodiment of a process 100 of producing a relational model of a database;
FIG. 2 illustrates one embodiment of a process 200 to combine a number of relational models of databases to produce one relational model;
FIG. 3 illustrates one embodiment of a process 300 to determine a non-directional contextual metric (NDCM) for each one of the term pairs within a context window;
FIG. 4 illustrates one embodiment of a process 400 to determine a left contextual metric (LCM) for each one of the term pairs within a context window;
FIG. 5 illustrates one embodiment of a process 500 to determine a right contextual metric (RCM) for each one of the term pairs within a context window;
FIG. 6 illustrates one embodiment of a process 600 to determine a directional contextual metric (DCM) for each one of the term pairs within a context window;
FIG. 6A shows one embodiment of a relational model represented in a network model diagram;
FIG. 7 illustrates one embodiment of an overview of a keyterm search process;
FIG. 8 illustrates one embodiment of expanding the query;
FIG. 9 illustrates one process of reducing the number of matching relations to a number of unique relations;
FIG. 10 illustrates one embodiment of a process of comparing a relational model of the query to each one of the relational models of subsets;
FIG. 11 illustrates an overview of one embodiment of the phrase search process;
FIG. 12 shows one process where the query includes a number of query fields;
FIG. 13 illustrates a method of combining the query field models;
FIG. 14 illustrates one embodiment of comparing a query model to each one of the relational models of subsets;
FIG. 15 illustrates one embodiment of a process of re-weighting a query model;
FIG. 16 shows one embodiment of generating phrases from a database of text;
FIGS. 17 and 17A illustrate a process of determining the phrases, which are contextually related to the query, from the model of the database such as in block 1608 of FIG. 16;
FIG. 18 illustrates one method of updating the conditional list of phrases;
FIG. 19 shows one embodiment of phrase discovery;
FIG. 20 shows an overview of one embodiment of the phrase extraction process;
FIG. 20A illustrates one embodiment of the phrase starting positions process;
FIG. 20B illustrates one embodiment of saving single term phrases;
FIG. 20C shows one embodiment of saving a phrase by combining the current phrase into the phrase list;
FIGS. 20D and 20E illustrate two embodiments of extracting selected multiterm phrases at each starting position;
FIG. 21 illustrates one embodiment of culling the extracted phrases;
FIG. 22 illustrates one embodiment of gathering related phrases;
FIG. 22A illustrates one embodiment of ranking the phrases output from the extracting and culling processes;
FIG. 22B illustrates one embodiment of ranking the selected phrases;
FIG. 22C illustrates one embodiment of a process of emphasizing the locally relevant relations and de-emphasizing the globally relevant relations;
FIG. 22D illustrates one embodiment of emphasizing the locally relevant phrases and de-emphasizing the globally relevant phrases; and
FIG. 23 shows a high-level block diagram of a computer system.
DETAILED DESCRIPTION
As will be described in more detail below, various methods of searching and extracting information from a database are described. The first described method is a method of contextually analyzing and modeling a database. The second described method is a method a searching a model of a database for subsets of the database that are relevant to a keyterm. The third described method is a method a searching a model of a database for subsets of the database that are relevant to a phrase. The fourth method described is a method of generating a list of phrases from a model of a database. The fifth described method is a method of discovering phrases in a database. Additional, alternative embodiments are also described.
Modeling a Database
A method and apparatus for contextually analyzing and modeling a database is disclosed. The database and/or a model of the database can also be searched, compared and portions extracted therefrom. For one embodiment, contextual analysis converts bodies of data, such as a database or a subset of a database, into a number of contextual associations or relations. The value of each contextual relation can be expressed as a metric value. Further, metric values can also include a directional metric value or indication.
For one embodiment, the contextual associations of a term provide contextual meaning of the term. For example, the term "fatigue" can refer to human physical tiredness such as "Fatigue impaired the person's judgment." Or "fatigue" can refer to breakdown of the structure of a material such as "Metal fatigue caused the aluminum coupling to break." A first aggregation of associations between term pairs such as: "fatigue" and "person", "fatigue" and "impaired", and "fatigue" and "judgment" can be clearly differentiated from a second aggregation of associations such as "metal" and "fatigue", "fatigue" and "aluminum", "fatigue" and "coupling", and "fatigue" and "break". Thus, when searching a database of subsets for subsets containing the notion of "fatigue" in the sense of human physical tiredness, subsets having greater similarity to the first aggregation of associations are more likely to include the appropriate sense of "fatigue", so these subsets would be retrieved. Further, the contextual associations found in the retrieved subsets can both refine and extend the contextual meaning of the term "fatigue".
The database to be modeled can include text and the examples presented below use text to more clearly illustrate the invention. Other types of data could also be equivalently used in alternative embodiments. Some examples of the types of data contemplated include but are not limited to: text (e.g. narratives, reports, literature, punctuation, messages, electronic mail, internet text, and web site information); linguistic patterns; grammatical tags; alphabetic, numeric, and alphanumeric data and strings; sound, music, voice, audio data, audio encoding, and vocal encoding; biological and medical information, data, representations, sequences, and patterns; genetic sequences, representations, and analogs; protein sequences, presentations, and analogs; computer software, hardware, firmware, input, internal information, output, and their representations and analogs; and patterned or sequential symbols, data, items, objects, events, causes, time spans, actions, attributes, entities, relations, and representations.
Modeling a database can also include representing the database as a collection or list of contextual relations, wherein each relation is an association of two terms, so that each relation includes a term pair. A model can represent any body or database of terms, wherein a term is a specific segment of the data from the database. Using a text database, a term could be a word or a portion of a word such as a syllable. A term in a DNA database for example, could be a particular DNA sequence or segment or a portion thereof. A term in a music database could be one or more notes, rests, chords, key changes, measures, or passages. Examples of databases that could be modeled include a body of terms, such as a collection of one or more narrative documents, or only a single term, or a single phrase. A collection of multiple phrases could also be modeled. In addition, combinations and subdivisions of the above examples could also be modeled as described in more detail below.
Relevance ranking a collection of models is a method of quantifying the degree of similarity of a first model (i.e., a criterion model) and each one of the models in the collection, and assigning a rank ordering to the models in the collection according to their degree of similarity to the first model. The same rank ordering can also be assigned, for example, to the collection of identifiers of the models in the collection, or a collection of subsets of a database represented by the models of the collection. The features of the criterion model are compared to the features of each one of the collection of other models. As will be described in more detail below, the features can include the relations and the contextual measurements, i.e. the relational metric values of the relations in the models. The collection of other models is then ranked in order of similarity to the criterion model. As an example: the criterion model is a model of a query. The criterion model is then compared to a number of models of narratives. Then each one of the corresponding narratives is ranked according to the corresponding level of similarity of that narrative's corresponding model to the criterion model. As another alternative, the criteria model can represent any level of text and combination of text, or data from the database, or combination of segments of sets of databases.
Relations and Relational Metrics
A relation includes a pair of terms also referred to as a term pair, and a number of types of relational metrics. The term pair includes a first term and a second term. Each one of the types of relational metrics represents a type of contextual association between the two terms. A relation can be represented in the form of: term1, term2, metric1, metric2, . . . metricN. One example of a relation is: crew, fatigue, 6, 4, . . . 8.
A relation can represent different levels of context in the body of text within which the term pair occurs. At one level, the relation can describe the context of one instance or occurrence of the term pair within a database. In another level, a summation relation can represent a summation of all instances of the term pair within a database or within a set of specified subsets of the database. A model of a database is a collection of such summation relations that represent all occurrences of all term pairs that occur within the database being modeled.
For one embodiment, a term from a database is selected and the contextual relationship between the selected term and every other term in the database can be determined. For example, given a database of 100 terms, the first term is selected and then paired with each of the other 99 terms in the database. For each of the 99 term pairs the metrics are calculated. This results in 99 relations. Then the second term is selected and paired with each of the other 99 terms and so forth. The process continues until each one of the 100 terms in the database has been selected, paired with each one of the other 99 terms and the corresponding metric values calculated. As the database grows larger, the number of relations created in this embodiment also grows exponentially larger. As the number of terms separating the selected term from the paired term increases, the relationship between the terms becomes less and less significant. In one alternative, if a term is one of a group of terms to be excluded, then no relations containing the term are determined.
The contextual analysis can be conducted within a sliding window referred to as a context window. The context window selects and analyzes one context window-sized portion of the database at a time and then the context window is incremented, term-by-term, through the database to analyze all of the term pairs in the database. For example, in a 100-term database, using a 10-term context window, the context window is initially applied to the first 10 terms, terms 1-10. The relations between each one of the terms and the other 9 terms in the context window are determined. Then, the context window is shifted one term to encompass terms 2-11 of the database and the relations between each one of the terms and the other 9 terms in the context window are determined. The process continues until the entire database has been analyzed. A smaller context window captures the more local associations among terms. A larger context window captures more global associations among terms. The context window can be centered on a selected term. In one alternative, redundant relations can be eliminated by including only a single relation between a term in one position within the database and another term in another position in the database.
In one embodiment of contextual analysis, a term in the sequence of terms in a database or subset of a database is selected. Relations are determined between the selected term and each of the other terms in a left context window associated with the selected term, and relations are also determined between the selected term and each of the terms in a right context window associated with the selected term. In one alternative, the left context window can contain L terms and the right context window can contain R terms. In another alternative, each context window can contain C terms, that is, L=R=C. A left context window of size C can include the selected term, up to C-1 of the terms that precede the selected term, and no terms that follow the selected term. A right context window of size C can include the selected term, and up to C-1 of the terms that follow the selected term, and no terms that precede the selected term. A context window of size C can include fewer than C terms if the selected term is at or near the beginning or end of the sequence of terms. For example, if the selected term is the 6.sup.th term in a sequence, then only 5 terms precede the selected term, and if the left context window is of size C=10, only 6 terms, the selected term and the 5 terms that precede the selected term, appear in the left context window. In a similar example, if the selected term is the 95.sup.th term in a sequence of 100 terms, then only 5 terms follow the selected term, and if the right context window is of size C=10, only 6 terms, the selected term and the 5 terms that follow the selected term, appear in the right context window. After relations are determined for a selected term, a subsequent term can be selected from the terms that have not yet been selected from the sequence of terms, and relations can be determined for the new selected term as described above. The process can continue until all terms in the sequence of terms have been selected, and all relations have been determined for the selected terms. Alternatively, the process can continue until all of the terms in the sequence of terms that are also in a collection of terms of interest have been selected, and all relations have been determined for the selected terms. In one alternative, redundant relations can be eliminated by including only a single relation between a term in one position within the database and a term in another position within the database.
FIG. 1 illustrates one embodiment of a process 100 of producing a relational model of a database. A database to be modeled is provided in process block 102. A context window is selected in block 104. Alternatively, the size of the context window can be varied. The size of the context window can be manually selected. The context window can automatically adjust to an average size of a portion of the database being modeled. For example, the portion could be a sentence, a phrase, a paragraph or any other subset of the database. The size of the context window can vary as a function of the data being scanned.
A first term from the database is selected in block 106. Several relations are determined in block 108. Each relation includes a number of types of contextual metrics between the selected term and each one of the terms included in the context window. Various processes to determine various types of contextual metrics are described more fully below. Next, a subsequent term is selected in blocks 110, 112 and the relations that include the new selected term are determined.
When the relations including the last term from the database have been determined, there are no subsequent terms so the collected relations are summarized. A first relation having a selected term pair is selected in block 114. All other instances of the relations having the selected term pair are then summarized into a summation relation in block 116. The summation relation includes the term pair and a number of types relational summation metrics (RSMs). Each one of the types of RSMs includes a summation of the corresponding types of metrics of each instance of the term pair. The RSM can be a sum of the corresponding types of metrics of each instance of the term pair. Alternatively, the RSM can be a normalized sum of the corresponding types of metrics of each instance of the term pair. For another alternative, the RSM can be a scaled sum of the corresponding types of metrics of each instance of the term pair. The RSM can also be equal to the metric value of one type of contextual metric for the one instance of the term pair that has the highest magnitude of the selected type of contextual metric, of all instances of the term pair. Other methods of producing a summation metric of the corresponding types of metrics of each instance of the term pair as known to one skilled in the art are also contemplated as various additional embodiments.
The summation relation is then included in a relational model of the database in block 118. The process of summarizing relations continues in blocks 120, 122, until a last relation is summarized and then the relational model of the database is output at block 124. The relational model of the database can be output in the form of a list of relations, or a sorted list of relations or, one of the types of RSMs can be selected and the relations sorted in the order of the selected RSM. Alternatively, the summation relations can be accumulated, as each instance of a relation is determined.
FIG. 2 illustrates one embodiment of a process 200 to combine a number of relational models of databases to produce one relational model. FIG. 2 illustrates combining a first relational model of a first database and a second relational model of a second database in block 202 but additional models can be easily combined through a similar process or through iterative use of the process 200. A first summation relation from the first relational model is selected in block 204. A combined summation relation including the term pair from the selected summation relation is then determined by reviewing each of the relations in the second relational model that include the term pair from the selected relation in block 206. The combined summation relation is determined as described above in FIG. 1. The combined summation relation is then included in the combined relational model. The process continues through each one of the summation relations in the first model in blocks 210, 212. Then, each one of the summation relations in the second relational model that contain term pairs that are not included the first relational model are then included in the combined relational model in blocks 214, 216. The combined relational model is then output at block 218.
Various types of relational metrics are contemplated. Some examples of the types of relational metrics are described in more detail below. The examples described are merely illustrative of the types of relational metrics contemplated and should not be read as exhaustive or limited to the examples described. One of the types of relational metrics is a standard relational metric, also referred to as a non-directional contextual metric (NDCM). Another type of relational metric is a left contextual metric (LCM). Another type of relational metric is a right contextual metric (RCM). Yet another type of relational metric is a directional contextual metric (DCM). Still another type of relational metric is a scaled frequency metric (SFM). Each of the above-described metrics is more fully described below. Additional types of relational metrics are also contemplated and one skilled in the art could conceive of several additional contextual metrics that could be also used as described below.
A relation with a term pair and multiple types of contextual metrics can be presented in any form. One form of expressing such a relation is the term pair followed by a list of the contextual metric values. Examples include: term1, term2, NDCM, or term1, term2, NDCM, LCM, RCM, or term1, term2, NDCM, DCM, SFM, or term1, term2, NDCM, LCM, RCM . . . "Nth" contextual metric.
Calculating Metric Values
FIG. 3 illustrates one embodiment of a process 300 to determine a non-directional contextual metric (NDCM) for each one of the term pairs within a context window. First, a starting term T1 is selected and identified in block 302. A first term in the context window is identified as T2 in block 304. An NDCM is then determined in block 306. The NDCM=C-1-N, where C is equal to a number of terms in the context window, and N is equal to a number of terms occurring between a first term and a second term of the term pair. The relation containing the term pair T1, T2 and the NDCM is then output in block 308. The process 300 continues to determine NDCMs for each of the remaining term pairs whose first terms occur within the context window and that start with T1, in blocks 310, 312. For example, the non-directional contextual metric of a term pair (A, B) is measured with respect to the number N of terms that occur between the terms A and B. If terms A and B are immediately adjacent, no terms are between A and B and therefore N=0 and the NDCM is equal to C-1-0.
FIG. 4 illustrates one embodiment of a process 400 to determine a left contextual metric (LCM) for each one of the term pairs within a context window. First a starting term T1 is selected and identified in block 402. A first term in the context window is identified as T2 in block 404. A LCM is then determined in block 406. The LCM value associated with a particular occurrence of a term pair (T1, T2) in a subset is LCM(T1, T2). If T2 follows T1 in a subset, then LCM(T1, T2) is equal to 0. If T2 precedes T1 in the subset, then LCM(T1, T2) is equal to C-1-N, where 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. The relation containing the term pair T1, T2 and the LCM is then output in block 408. The process 400 continues to determine LCMs for each of the remaining term pairs in the context window that start with T1 in blocks 410, 412. If, for example, the terms T1 and T2 occur in the order of T2 followed by T1 and T2 occurs 3 terms to the left of T1, and a context window is 8, then the LCM(T1, T2) would be C-1-N=8-1-2=5. For another example, if terms T1 and T2 occur in the order of T1 and then T2 and a context window is 8, then T2 occurs to the right of T1, then the LCM(T1, T2) is equal to zero since LCM(T1, T2) is zero for all occurrences of T2 that follow this occurrence of T1 within the context window.
FIG. 5 illustrates one embodiment of a process 500 to determine a right contextual metric (RCM) for each one of the term pairs within a context window. First a starting term T1 is selected and identified in block 502. A first term in the context window is identified as T2 in block 504. An RCM is then determined in block 506. The RCM value associated with a particular occurrence of a term pair (T1, T2) in a subset is RCM(T1, T2). If T2 precedes T1 in the subset, then RCM(T1, T2)=0. If T2 follows T1 in the subset, then RCM(T1, T2) is equal to C-1-N, where 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. The relation containing the term pair T1, T2 and the RCM is then output in block 508. The process 500 continues to determine RCMs for each of the remaining term pairs in the context window that start with T1 in blocks 510, 512. If, for example the terms T1 and T2 occur in the order of T1 and then T2, and T2 occurs 3 terms to the right of T1, and a context window is 8, then the RCM(T1, T2) would be C-1-N=8-1-2=5. For another example, if the terms T1 and T2 occur in the order of T2 and then T1 and a context window is 8, then the RCM(T1, T2) is equal to 0, because the RCM(T1, T2) is zero for all occurrences of T2 that precede this occurrence of T1 in the context window.
FIG. 6 illustrates one embodiment of a process 600 to determine a directional contextual metric (DCM) for each one of the term pairs within a context window. First a starting term T1 is selected and identified in block 602. A first term in the context window is identified as T2 in block 604. A DCM is then determined in block 606. The DCM(T1, T2) is equal to RCM(T1, T2)-LCM(T1, T2) and is applied to relations whose terms are ordered to ensure that RCM is greater than or equal to LCM. Alternatively, DCMs of less than zero can be accommodated. The relation containing the term pair T1, T2 and the DCM is then output in block 608. The process 600 continues to determine DCMs for each of the remaining term pairs in the context window that start with T1 in blocks 610, 612.
The scaled frequency metric (SFM) is equal to (C-1-N)*{(2F.sub.M -F.sub.1 -F.sub.2)/2F.sub.M }. C is equal to the number of terms in the context window. N is equal to the number of terms occurring between a first term and a second term of the term pair. F.sub.M is equal to a frequency of occurrences of a most frequent term in the database. F.sub.1 is equal to a frequency of occurrences of a first term of the term pair in the database. F.sub.2 is equal to a frequency of occurrences of a second term of the term pair in the database.
In the following example sentence, which contains one instance of the term ENGLISH followed by one instance of the term PHRASEOLOGY, the term PHRASEOLOGY is in the right context of the term ENGLISH, and the term ENGLISH is in the left context of the term PHRASEOLOGY.
BETTER ENGLISH SPEAKING FOREIGN CTLRS AND USE OF STD PHRASEOLOGY IS NEEDED.
Using a context window (C) equal to 10 terms, treating the sentence as the entire database, and observing that there are N=7 terms between ENGLISH and PHRASEOLOGY, the corresponding metrics have the following values:
The NDCM(ENGLISH, PHRASEOLOGY), or the measure of the extent that ENGLISH and PHRASEOLOGY are in the same context, is equal to:
C-1-N=10-1-7=2 Equation 1
The NDCM(ENGLISH, PHRASEOLOGY) is the same as NDCM(PHRASEOLOGY,ENGLISH) since direction does not matter for calculating the NDCM.
The RCM(ENGLISH, PHRASEOLOGY), or the measure of the contextual association of ENGLISH followed by PHRASEOLOGY, is equal to:
C-1-N=10-1-7=2 Equation 1.1
The LCM(ENGLISH, PHRASEOLOGY), or the measure of the contextual association of ENGLISH preceded by PHRASEOLOGY, is equal to 0 since there are no incidences of PHRASEOLOGY which precede an incidence of ENGLISH.
The RCM(PHRASEOLOGY, ENGLISH) or the measure of the contextual association of PHRASEOLOGY followed by ENGLISH, is equal to 0 since there are no incidences of ENGLISH which follow an incidence of PHRASEOLOGY.
The LCM(PHRASEOLOGY, ENGLISH), the measure of the contextual association of PHRASEOLOGY preceded by ENGLISH, is equal to:
C-1-N=10-1-7=2 Equation 1.2
The above example describes how to determine the types of contextual metrics for one instance of one term pair in a database of terms. Typically, a single term pair occurs multiple times throughout a database. One embodiment of a summation relation includes a summation of the corresponding types of contextual metrics for each one of several occurrences of a term pair throughout the database.
The following is an example of combining multiple relations for the same term pair across all of the shared contexts in a database to determine a single summation relation that represents that term pair in that database. Table 1.1 illustrates three schematic lines of text representing excerpts from a database being modeled, where the items "t" are terms that are not terms of interest and do not include term A or term B, and the contextual relationship between terms A and B is the relation of interest. No other instances of terms A and B occur within the database.
TABLE 1.1
1. . . . t t t A B t t t . . .
2. . . . t t A t B A t t . . .
3. . . . t t t B B A t t . . .
Table 1.2 illustrates the relations of each instance of the paired terms A and B, using a context window of C=3 terms. The line numbering indicates the line number containing the relation. For example, "2.1" is the first relation from line 2 above, and "2.2" is the second relation from that line. Each relation can take either of the two forms, as shown. The forms are equivalent.
TABLE 1.2
term_1 term_2 NDCM LCM RCM term_1 Term_2 NDCM
LCM RCM
1.0. A B 2 0 2 same as B A 2
2 0
2.1. A B 1 0 1 same as B A 1
1 0
2.2. A B 2 2 0 same as B A 2
0 2
3.1. A B 1 1 0 same as B A 1
0 1
3.2. A B 2 2 0 same as B A 2
0 2
RSM 8 5 3 8
3 5
If lines 1-3 were the only lines in the database containing terms A and B, the above relations would be summed to produce a summation relation (RS) having relational summation metrics (RSMs) representing the overall contextual association of terms A and B in the database. The summation relation can be expressed in either one of two equivalent forms shown in Table 1.3:
TABLE 1.3
term_1 term_2 NDCM LCM RCM term_1 term_2 NDCM
LCM RCM
RS A B 8 5 3 same as B A 8 3
5
Often the term pairs occur in varying orders. The first term in a term pair A, B is A in one occurrence, and B in another occurrence. Several of the relational metrics such as RCM and LCM, have a direction component, i.e. that the direction or order of the term pair is significant to the metric value as described above. Therefore, to create an accurate summation relation of A, B of all occurrences of the term pair A, B in the database, a direction or order of each occurrence of the term pair A, B must be adjusted to the same direction.
The order of term pairs in the relations of models is most preferably shown in the same order as the typical reading order in the database. That is:
If RCM(A, B)>LCM(A, B), then the summation relation is preferably expressed as: A, B, NDCM(A, B), LCM(A, B), RCM(A, B).
Conversely:
If RCM(B, A)>LCM(B, A) then the summation relation is preferably expressed as B, A, NDCM(B,A), LCM(B,A), RCM(B,A).
In this instance (Table 1.3) the RCM(B, A) is greater than the LCM(B, A) and therefore B followed by A is in the typical reading order (i.e. left to right). Therefore, Table 1.4 shows the form of the expressing relationship between terms A and B that would be used in the model representing the summation relation (RS) of the term pair (A, B) within the database:
TABLE 1.4
term_1 term_2 NDCM LCM RCM
B A 8 3 5
The above summation relation could also be interpreted as saying that when terms A and B are contextually associated, term A tends to follow term B and to a lesser extent A precedes B, with the degree of contextual association indicated by the metrics. This relationship can be observed in text lines 1-3 of Table 1.2. A model of a database consists of a collection of such relations for all term pairs of interest which exist within the database.
For one embodiment of a relation expressed in terms of A followed by B, the relation is preferably written in the form: A, B, NDCM(A,B), LCM(A,B), RCM(A,B). If for some reason the above relation must be expressed in terms of B followed by A, then the relation can be rewritten in the form of: B, A, NDCM(B,A), LCM(B,A), RCM(B,A), where NDCM(B, A)=NDCM(A, B), LCM(B, A)=RCM (A, B), and RCM(B, A)=LCM(A, B). Of course, if additional types of metrics were included in the relation and those additional types of metrics included a directional component, then those additional types of metrics would also have to be recalculated when the written expression of the relation is reversed.
The context window used to calculate the above-described metric values can have any one of a number of sizes. A context window can have a pre-selected number of terms. Typically, a context window is equal to a level of context desired by the user. Examples include: an average sentence length, or an average paragraph length, or an average phrase length, or a similar relationship to the text or the database. For an alternative embodiment, the context window can be entirely independent from the any relation to the database being analyzed such as a pre-selected number chosen by a user or a default process setting. Alternatively, the context window can vary as a function of the position of the context window within the text, or the contents of the context window.
A model of a database or subset includes summation relations and each summation relation includes several types of the relational summation metrics (RSMs) for each term pair. A model of a database or subset can be represented in a variety of forms including, but not limited to, a list of relations, a matrix of relations, and a network of relations. An example of a list representation of relations is shown in Table 1.5. An example of a matrix representation of the relations of Table 1.5 is shown in Table 1.6. An example of a network representation of the relations in Tables 1.5 and 1.6 is shown in FIG. 6A.
TABLE 1.5
term_1 term_2 NDCM
Flight 800 1725
TWA Flight 1486
TWA 800 1461
fuel tanks 849
Aviation Federal 693
Federal Administration 668
Aviation Administration 662
National Transportation 602
Safety Transportation 600
National Safety 589
Safety Board 580
TWA Explosion 554
Transportation Board 532
National Board 522
800 Explosion 415
Flight Explosion 408
Fuel Explosion 333
Recommendations Urgent 252
Tanks Heat 197
Fuel Heat 190
Aviation Safety 187
Fuel Federal 171
TABLE 1.6
R
A T
E
D R
C
M A
O
I N
M
N S
M
I P
E E
A S N O
X N
F V T A R
P D
F E I R T T
S L U A
L T D A A I A
A B O R T
I F A H E T T O T
F O S G I
T G 8 U N E R I I N I
E A I E O
W H 0 E K A A O O A O
T R O N N
A T 0 L S T L N N L N
Y D N T S
TWA 1486 1461
554
Flight 1725
408
800
415
Fuel 849 190 171
333
Tanks 197
Heat
Federal 668
Aviation 693 662
187
Administration
National 602
589 522
Transportation
532
Safety 600
580
Board
Explosion
Urgent
Recommendations
252
At the extreme, the contextual relations of all term pairs in a database could be determined, but this is not necessary because a database or subset can be effectively modeled by retaining only those relations having stronger contextual relations as indicated by larger values of the relational metrics. Thus, the potentially large number of relations can be reduced to a smaller and more manageable number of relations. Appropriate methods of reducing the number of relations in a model are preferably those that result in the more representative relations being retained and the less representative relations being eliminated.
A threshold value can be used to reduce the number of relations in a relational model eliminating those relations having a metric value below a certain threshold value. Alternatively, a specific type of metric or summation metric value can be selected as the metric to compare to the threshold value. Another method to reduce the number of relations in a relational model is by selecting a pre-selected number of the relations having the highest metric values. First, one of the types of metric values or summation metric values is selected. Then the pre-selected number of relations having a greatest value of the selected type of metric value is selected from the relations in the relational model.
Keyterm Search
Keyterm search is a method of retrieving from a database a number of subsets of the database that are most relevant to a criterion model derived from one or more keyterms. The retrieved subsets can also be ranked according to their corresponding relevance to the criterion model. One embodiment of a keyterm search is a method of searching a database. First, several relational models are provided. Each one of the relational models includes one relational model of at least one subset of the database. Next, a query is input. A criterion model is then created. The criterion model is a relational model that is based on the query. The criterion model is then compared to each one of the relational models of subsets. The identifiers of the subsets relevant to the query are then output.
FIGS. 7-10 show various embodiments of applying keyterm searching to several relational models of subsets of a database. FIG. 7 illustrates one embodiment of an overview of a keyterm search process 700. First, a number of relational models of subsets of a database are provided in block 702. The subsets can be any level of subset of the database from at least two terms to the entire database. Each one of the relational models includes one relational model of at least one subset of the database. A query is input in block 704 for comparing to the relational models of subsets of the database. The query can include one term or multiple terms. Next, the query is expanded and modeled to create a criterion model in block 708, as will be more fully described below. The criterion model is then compared to each one of the relational models of subsets of the database in block 710 that is also described in more detail below. The identifiers of the relevant subsets are then output in block 712.
As an alternative form of input to the keyterm search process, the input query can consist of a query model. A query model can provide detailed control of the relevance criteria embodied in an input query. As a further alternative, the input query can consist of a selected portion of a previously output query model. One alternative method of selecting a portion of an output query model includes selecting a number of relations whose term pairs contain any of a selected group of terms. Another alternative method of selecting a portion of an output query model includes selecting a number of relations having selected metrics greater than a selected threshold value. As another alternative, the input query model can be a model of a subset of a database. As another alternative, the input query model can be a model of a subset of a database having relational metrics that have been multiplied by one or more of a collection of scale factors. As a further alternative, the input query model can be created by manually creating term pairs and corresponding metric values. When a query model is used as an input query, the process of expanding the query and creating a relational model of the query shown in block 708 includes passing the input query model to the comparing process shown in block 710.
Many alternative forms of outputs of the keyterm search process are useful. Outputting the identifiers of the relevant subsets 712 can also include outputting the types of relevance metrics corresponding to each one of the subsets. It is also useful to select one of the types of relevance metrics, to sort the identifiers of subsets in order of magnitude of the selected type of relevance metric, and then to output the identifiers of subsets in order of magnitude of the selected type of relevance metric. For another alternative, the selected type of relevance metric can include a combination of types of relevance metrics. The selected type of relevance metric can also include a weighted sum of types of relevance metrics or a weighted product of the types of relevance metrics.
Outputting the identifiers of the relevant subsets in block 712 can also include normalizing each one of the corresponding intersection metrics of all intersection relations. Outputting the identifiers of the relevant subsets in block 712 can also include outputting the relational model of the query, i.e. the criterion model. Outputting the criterion model is useful to assist a user in directing and focusing additional keyterm searches. Outputting the identifiers of the relevant subsets can also include displaying a pre-selected number of subsets in order of magnitude of a selected type of relevance metric.
Another useful alternative output is displaying or highlighting the term pairs or term pair relations that indicate the relevance of a particular subset. For example, one or a selected number of the shared term pairs in each one of the subsets are highlighted, if the terms within each one of the shared term pairs occur within the context window. To reduce the number of displayed shared term pairs, only those shared term pairs that have the greatest magnitude of a selected type of relevance metric are displayed or highlighted. Still another useful output is displaying the shared term pairs that occur in the corresponding subsets. For example, outputting the identifiers of the relevant subsets in block 712 can also include displaying one or a selected number of shared term pairs that occur in each one of the subsets, wherein the terms within each one of the shared term pairs occur within a context window.
Displaying metric values associated with the displayed shared term pairs is also useful. For example, the output display can also include, for each one of the shared term pairs, displaying an NDCM.sub.Q1, and NDCM.sub.S1 and a product equal to [ln NDCM.sub.Q1 ]*[ln NDCM.sub.S1 ]. The NDCM.sub.Q1 is equal to a non-directional contextual metric of the shared term pair in the query, and the NDCM.sub.S1 is equal to a non-directional contextual metric of the shared term pair in the subset. The NDCM.sub.Q1 and the NDCM.sub.S1 must each be greater than 1.
As described above, the input query can include a single term or multiple terms. The query can also be transformed when first input. Transforming the query is useful for standardizing the language of a query to the terms used in the database, to which the query derived criterion model will be compared. For example, if an input query was "aircraft, pilot" and the database used only the corresponding abbreviations "ACFT, PLT", then applying a criterion model based on the input query "aircraft, pilot" would not be very useful. Therefore a transformed query, which transformed "aircraft, pilot" to "ACFT, PLT", would yield useful results in a keyterm search.
Transforming the query includes replacing a portion of the first query with an alternate portion. One embodiment of replacing a portion of the query with an alternate portion is a method of finding an alternate portion that is cross-referenced in a look-up table such as a hash table. A hash table includes a number of hash chains and each one of the hash chains corresponds to a first section of the portion of the query and includes several terms or phrases beginning with that first section of the query. The hash chain includes several alternative portions. Each of the alternative portions corresponds to one of the first portions of the query. The subsets of the database can also be transformed, as described above, with respect to the query.
Often a query is very short and concise, such as a single term. Another useful alternative is to expand the query to include terms related to the input query term or terms. Many approaches have attempted to expand the query through various methods that typically result in query drift, i.e. where the query begins to include very broad concepts and several unrelated meanings. A query expanded in such a manner is not very useful as the resulting searches produce subsets that are not directly related to the input query. The method of expanding the query described below, substantially maintains the focus and directness of the query while still expanding the query to obtain results including very closely related concepts.
Expanding the query is also referred to as creating a gleaning model of the query. FIG. 8 illustrates one embodiment of expanding the query 800 and includes a process of first comparing the query to each one of the models of the subsets of the database in block 802. The matching relations are extracted from the models of the subsets of the database. Each one of the matching relations has a term pair, including a term that matches at least one term in the query, and a related term, in block 804. The matching relation also includes a number of relational summation metrics.
In one embodiment, a matching term is identical to a query term. For example, the term "fatigue" matches the query term "fatigue". Alternatively, a term that contains a query term can also match that query term. For example, the terms "fatigued" and "fatigues" are matching terms to the query term "fatigue". In another alternative, a term that is either identical to a query term, or a term that contains a query term, matches that query term. For example, three terms that match the query term "fatigue" are "fatigue", "fatigues", and "fatigued". As a further example, four terms that match the query term "fatigu" are "fatigue", "fatigues", "fatigued", and "fatiguing". The matching relations found when expanding the query can also be reduced to only the unique relations, by eliminating any repeating relations from the matching relations.
FIG. 9 illustrates one process 900 of reducing the number of matching relations to a number of unique relations. The process 900 includes first, selecting one of the matching relations in block 902. The next step is determining if a term pair from the selected matching relation is included in one of the unique relations in block 906. If the selected term pair is not included in one of the unique relations, then the selected matching relation is included in the unique relations in block 910. If the selected term pair is included in one of the unique relations in block 906, then the order of the term pair in the matching relation must be compared to the order of the term pair in the unique relation in block 912. If the order is not the same in both the selected matching relation and the unique relation, then the order of the term pair in the selected matching relation is reversed in block 914 and the corresponding metrics containing directional elements are recalculated in block 916, as described above. For example, the values of the LCM and the RCM of the selected matching relation must be exchanged when the stated order of the term pair is reversed. Once the order of the term pair in the selected matching relation and the order of the term pair in the unique relation are the same, then the types of relational summation metrics (RSMs) for the unique relation are replaced with a summation of the corresponding types of RSMs of the selected matching relation and the previous corresponding types of RSMs of the unique relation in block 918. In short, the RSMs are accumulated in the unique relation having the same term pair. The process 900 then repeats for any subsequent matching relations in blocks 920, 922.
Another approach to reducing the number of matching relations can also include eliminating each one of the matching relations having a corresponding type of RSM less than a threshold value. Still another approach to reducing the number of matching relations can also include extracting matching relations from a pre-selected quantity of relational models. Each one of the matching relations that has a corresponding type of RSM less than a threshold value is then eliminated. Further, selecting a pre-selected number of matching relations that have the greatest value of the corresponding type of RSM can also reduce the number of matching relations.
Another aspect of expanding the query can also include determining a typical direction for each one of the matching relations. The typical direction is the most common direction or order of the term pair in the text represented by the relation. If the RCM is greater than the LCM, then the typical direction is the first term followed by the second term. If the LCM is greater than the RCM, then the typical direction is the second term followed by the first term. In one alternative of determining a typical direction, if the LCM is larger than the RCM, then the order of the term pair in the matching relation is reversed, and the value of the RCM is exchanged with the value of the LCM.
Expanding the query can also include sorting the unique relations in order of prominence. Prominence is equal to a magnitude of a selected metric.
FIG. 10 illustrates one embodiment of a process 1000 of comparing a relational model of the query to each one of the relational models of subsets. The process 1000 includes determining the relevance metrics for each one of the relational models of the subsets. This is initiated by determining an intersection model of the relational model of the query and the model of the first subset. Determining an intersection model can include determining a number of intersectional relations in block 1004. Each one of the intersectional relations has a shared term pair and the shared term pair is present in at least one relation in each of the query model and the first subset relational model. Each intersectional relation also has a number of intersection metrics (IM). Each IM is equal to a function of RSM.sub.Q1 and RSM.sub.S1. RSM.sub.Q1 is a type of relational summation metric in the relational model of the query and RSM.sub.S1 is a corresponding type of relational summation metric in the relational model of the first one of the relational models of the subsets. Next, a relevance metric for each one of the types of relational summation metrics is determined. Each one of the relevance metrics includes a function of the corresponding type of relational summation metrics of each one of the intersection relations in block 1006. The process repeats in blocks 1008 and 1010 for any additional models of subsets.
The function of RSM.sub.Q1 and RSM.sub.S1 could alternatively be equal to [ln RSM.sub.Q1 ]*[ln RSM.sub.S1 ], if RSM.sub.Q1 and RSM.sub.S1 are each greater than or equal to 1. For another alternative embodiment function of RSM.sub.Q1 and RSM.sub.S1 could equal [RSM.sub.Q1 ]*[RSM.sub.S1 ].
Determining an intersection model can also include applying a scaling factor to the summation of the corresponding IMs. One scaling factor is a subset emphasis factor (SEF)=S.sub.s /R, wherein S.sub.s is equal to a sum of a selected type of relational metrics from the subset for all shared relations and R is equal to a sum of the selected type of relational metric in the subset. Another scaling factor is a query emphasis factor (QEF)=S.sub.q /Q. S.sub.q is equal to a sum of a selected type of relational metrics from the query for all shared relations. Q is equal to a sum of the selected type of relational metric in the relevance model of the query. Another scaling factor is a length emphasis factor (LEF)=L.sub.s /T where, L.sub.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. Still another scaling factor is an alternate length emphasis factor (LEF.sub.alt)=L.sub.cap /T where, L.sub.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 subsets, and T is equal to a number greater than a number of terms in a largest subset of the database.
For another alternative output, a representation of the model of the query or a model of a subset can be output. Such representations can include table-formatted text, or a network diagram, or a graphical representation of the model.
For another alternative embodiment of keyterm search, multiple queries can be applied to the keyterm search processes described above. A first query is processed as described above. Next, a second query is input, and then a relational model of the second query is created. Then the relational model of the second query is compared to each one of the relational models of the subsets. A second set of identifiers of the subsets relevant to the second query is then output. Finally, the second set of relevance metrics for the second query is combined with the relevance metrics for the first query to create a combined output. An alternative embodiment can also include determining a third set of identifiers of the subsets consisting of identifiers of the subsets present in both the first and second sets of subsets. A selected combined relevance metric for each one of the identifiers of the subsets that is present in both the first set of identifiers of the subsets and the second set of identifiers of the subsets is greater than zero. Combining the sets of identifiers can also include calculating a product of a first type of first relevance metric and a first type of a second relevance metric.
Another alternative also includes determining a third set of identifiers of the subsets consisting of identifiers of the subsets present in either the first or second set of subsets. A selected combined relevance metric for each one of the identifiers of the subsets that is present in either the first set of identifiers of the subsets or the second set of identifiers of the subsets, or both, is greater than zero. In one embodiment, combining the sets of identifiers also includes calculating a summation of a first type of first relevance metric and a first type of a second relevance metric.
This application is intended to cover any adaptations or variations of the present invention. For example, those of ordinary skill within the art will appreciate that the keyterm search process can be executed in varying orders instead of being executed in the order as described above.
Using keyterm search is easy. All that is required is to provide the keyterm or keyterms of interest. Then the subsets of a database, such as the narratives of the Aviation Safety Reporting System (ASRS) database, are sorted according to their relevance to the query, the most relevant narratives are displayed with the relevant sections highlighted. Examples of keyterm search applied to the ASRS database are shown below to illustrate several important details.
Using a query term "engage" to find narratives relevant to "engage", the keyterm "engage" is input to the keyterm search and the most relevant narratives, with their relevant sections highlighted, are displayed. Additional outputs can include a complete list of relevant narratives, and the criterion model used to search the ASRS database. The following is an example of a relevant narrative:
ON FEBRUARY/XX/95 AT ABOUT XA00 PM SAN JUAN TIME WE DEPARTED RWY 8 ENRTE TO MIAMI. WE INTERCEPTED THE JAAWS 9 DEP, AND SHORTLY AFTER PASSING THROUGH 10000 FT WE WERE CLRED DIRECT (RNAV ) TO JUNUR, WHICH IS A POINT IN THE CLAMI 1 ARR INTO MIAMI. I THEN ENGAGED THE AUTOPLT AND TURNED THE ACFT IN THE DIRECTION OF THE WAYPOINT (JUNUR) WE WERE CLRED TO. AT THIS POINT I AM NOT SURE IF I ENGAGED THE AUX NAV PORTION OF THE AUTOPLT. THE REASON I SAY THIS IS BECAUSE APPROX 1 HR LATER WE DISCOVERED THAT THE AUX NAV PORTION OF THE AUTOPLT WAS NOT ENGAGED AND WE HAD DRIFTED ABOUT 45 NM OFF COURSE. IT IS UNKNOWN WHETHER THE AUX NAV WAS NEVER ENGAGED OR IF THE KNOB WAS SOMEHOW KNOCKED OFF DURING THE FLT. I DO REMEMBER PASSING ALMOST DIRECTLY OVER GTK VOR WHICH IS ALONG THE NORMAL RTE THE ACFT WOULD TAKE IF THE OMEGA WERE ENGAGED. 2 SCENARIOS ARE POSSIBLE. THE OMEGA WAS NEVER ENGAGED, AND DUE TO LIGHT HIGH ALT WINDS, THE ACFT AFTER INITIALLY BEING POINTED IN THE CORRECT DIRECTION, ONLY BEGAN TO DRIFT DRAMATICALLY AFTER PASSING GTK VOR. OR, THE AUX NAV KNOB WAS ACCIDENTLY DISENGAGED AND WAS NOT NOTICED. THERE IS NO AURAL OR OTHER TYPE WARNING WHEN THE OMEGA BECOMES DISENGAGED. THERE IS A GREEEN `AUX NAV` LIGHT THAT IS ILLUMINATED WHEN ENGAGED, BUT THE LIGHT IS NOT VERY OBVIOUS TO THE CREW. SOME TYPE OF OBVIOUS WARNING (HAD IT BEEN AVAILABLE ) WOULD HAVE ALERTED THE CREW IN THE EVENT OF AN INADVERTENT DISCONNECT. ONE THING WE FOUND UNUSUAL DURING OUR FLT WAS THAT ATC NEVER SAID A WORD TO US DURING OUR SMALL DETOUR. (300563)
The default pattern-matching behavior of keyterm search is a "contained match". This means that any term that contains the string of characters "engage" is considered to be a match. So, narratives containing the following terms are retrieved:
engage engaged disengage disengaged reengage
reengaged engagement disengagement
In the example narrative, the term "engaged" appears 7 times, "disengaged" appears twice, and "engage" does not appear. This shows the value of allowing the "contained match" as the default. A user need not know the various forms of the term that appear in the narratives, but can find the narratives that are clearly relevant to the input keyterm "engage."
Not only are the various forms of the term "engage" highlighted in the example narrative, but other terms are also highlighted. These other terms are often found in the context of "engage" in the ASRS database. Highlighting can be limited to a pre-selected number of the most prominent contextual associations of the keyterm in the database. The default number is 1000. Of course the keyterm search could limit highlighting to just the keyterm(s), or to contextual associations that have some fraction of the prominence of the most prominent association in the database or the particular narrative.
The display of the most relevant narratives can suffice, but a deeper understanding of which contextual associations contribute to the relevance of each narrative can also be presented. By referring to a data table that is displayed after each narrative, it is possible to identify the terms in the narrative that are most often found in the context of the query term(s). Table 2.1 shows a top portion of a data table for the example narrative:
TABLE 2.1
W1 W2 A B C
ENGAGED AUTOPLT 17905 70 41.6048
NOT ENGAGED 2484 72 33.4334
NAV ENGAGED 898 94 30.8952
ENGAGED ALT 6015 27 28.6804
ENGAGED LIGHT 508 74 26.8164
OMEGA ENGAGED 386 87 26.5982
DISENGAGED NOT 896 39 24.9047
ENGAGED BUT 984 24 21.902
NEVER ENGAGED 159 73 21.7479
AUX ENGAGED 117 94 21.636
CLRED ENGAGED 364 26 19.2135
ENGAGED COURSE 239 32 18.98
OMEGA DISENGAGED 202 34 18.7189
WARNING DISENGAGED 202 34 18.7189
Each line in Table 2.1 represents a contextual association between two terms (i.e., the terms in columns W1 and W2). Column A is a measure of the strength of the contextual association of the term pair in the whole ASRS database. Column B is a measure of the strength of the same contextual association in this narrative. Column C is a combination of these two metrics and represents a measure of the contextual association of the paired terms. In this table, C is the product of the natural logarithms of A and B. The value of C is large when the values of both A and B are large. The relations are sorted on column C.
Term pairs toward the top of the list have stronger contextual associations. The top relation, for example, is between ENGAGED and AUTOPLT (i.e., autopilot). This relation is at the top of the list because AUTOPLT is very often found in the context of ENGAGED in the ASRS database (as indicated by 17905 in column A) and that relationship is also relatively prominent in this narrative (as indicated by 70 in column B). The term ENGAGED is in column W1, and the term AUTOPLT is in W2 because ENGAGED tends to precede AUTOPLT in the narratives of the ASRS database. In general, each pair of terms appears in the more typical order.
The contextual relationship between ENGAGED and AUTOPLT can be seen in the following excerpts from the example narrative:
I THEN ENGAGED THE AUTOPLT
IF I ENGAGED THE AUX NAV PORTION OF THE AUTOPLT
THE AUX NAV PORTION OF THE AUTOPLT WAS NOT ENGAGED
An additional advantage of the contained match rule is that a term such as "engage" can be used as a query. This would match several forms of "engage", including not only those listed earlier, but also "engaging" and "disengaging". Alternatively, an exact match can also be required so that only narratives containing the term "engage" would be retrieved.
A search for narratives relevant to "rest" requires the use of the "exact match" option. That is because the default "contained match" option that worked so well in the previous example becomes a liability when the query is contained in too many terms. "Rest" is such a query, as indicated by the following long list of terms from the ASRS database that contain "rest":
RESTR REST RESTRICTION RESTRICTIONS
NEAREST RESTART RESTRS INTEREST
RESTARTED RESTORED INTERESTED INTERESTING
RESTATED ARRESTED RESTED ARREST
RESTORE UNRESTRICTED RESTRICT FOREST
RESTRICTING RESTRICTIVE UNRESTR RESTING
RESTAURANT ARRESTING RESTROOM RESTRICTED
RESTS CRESTVIEW RESTARTING CREST
INTERESTS RESTATE RESTRICTS PRESTART
INTERESTINGLY RESTORING RESTRAINT RESTRAINED
RESTRAINTS BREST OVERESTIMATED RESTATING
RESTORATION RESTRAINING ARMREST RESTLESS
UNDERESTIMATED
To find narratives relevant to "rest", input the keyterm "rest" to keyterm search and select the "exact match" option. The most relevant narratives are displayed, with their corresponding relevant sections highlighted. The following is one of the most relevant narratives:
CREW REST REGS: UNFORTUNATELY, EVERY ONCE IN A WHILE FOR A VARIETY OF REASONS, THIS REG (DESIGNED TO ENSURE PROPERLY RESTED PLTS) GETS FORGOTTEN! TRY AND FIGURE THIS ONE. 2 DAY PAIRING SCHEDULE FOR 10 PLUS 09, THE FIRST DAY SHOW TIME IS LATE EVENING AND FLT TIME IS SCHEDULED FOR 3 PLUS 44. DUE TO MECHANICAL PROBLEM WE PUSHED: 20 LATE, WX IN THE AREA DELAYED OUR TKOF. WITH AN UNSCHEDULED FUEL STOP WE LANDED AND PARKED AT THE DEST GATE 1 PLUS 51 LATE. ORIGINALLY WE WERE SCHEDULED FOR 10 PLUS 16 LAYOVER. OUR COMPANY'S STD RESPONSE WHEN CALLED TO CHK CREW REST IS 8 PLUS 44 BLOCK TO BLOCK (XX AND 8 PLUS 44=A PUSH TIME OF XXY) SINCE OUR PUSH TIME WAS SCHEDULED FOR XXY THERE WAS NOT A CONFLICT IN OUR THINKING. AT EARLY SCHEDULING AWOKE THE CAPT, INFORMING HIM THAT THE FO AND SO `REQUIRED 9 PLUS 45` BLOCK TO BLOCK CREW REST. WE ALL SHOWED AS PLANNED THE PREVIOUS EVENING FOR SCHEDULED VAN. THE CAPT INFORMED FO AND I ABOUT CALL FROM SCHEDULES, IT JUST DID NOT MAKE SENSE. WE FLEW 4 PLUS 13 THE NIGHT BEFORE AND WERE SCHEDULED TO FLY 6 PLUS 25 THIS DAY. WHAT WERE WE TO DO? GO BACK TO OUR ROOMS AND SLEEP FOR ANOTHER 45 MINS? WE SHOWED ON THE ACFT (8 PLUS 51 FROM BLOCK IN) ACFT WAS BOARDED NORMALLY AND WE SAT WITH THE PARKING BRAKE SET SO AS NOT TO TRIP ACARS UNTIL SCHEDULING GOT THEIR IMPOSED 9 PLUS 45 BLOCK TO BLOCK, HOWEVER, I SEE THAT 1) THEY INTERRUPTED CAPT CREW REST. 2) THEIR REST INTERPRETATION WAS SOMEHOW FLAWED (ALTHOUGH APPRECIATED WHEN WE GET `MORE` REST). 3) `MORE` REST I DO NOT NEED SPENT SITTING 54 MINS WITH PARKING BRAKE SET--WAITING TO BE LEGAL. MY AIRLINE USES FAR MIN REST AS NORMAL PRACTICE AND ROUTINELY VIOLATES CREW REST FOR PERHAPS MISINTERPRETED REST REGS REQUIRED. I FEEL 1) FAA MUST MAKE BOTH FLT TIME AND DUTY TIME HENCE REST TIMES EASIER TO UNDERSTAND (THROW OUT INTERPRETATIONS)! 2) HOLD CREW SCHEDULERS ACCOUNTABLE FOR VIOLATIONS OF CREW REST, A GOOD SCHEDULE PRACTICE WOULD HAVE BEEN TO INFORM US ON ARR THE PREVIOUS NIGHT OF REST REQUIRED. (183457)
The terms CREW, REQUIRED, BLOCK, NOT, DUTY, CAPT (i.e., captain), FAR (i.e., Federal Aviation Regulations), REGS (i.e., regulations), LEGAL, FAA (i.e., Federal Aviation Administration), NIGHT, FEEL, SCHEDULED, and others are highlighted in the narrative because they are often found in the context of REST in the narratives of the ASRS database.
The needs of many users will be satisfied by the display of the most relevant narratives, but others might wish to better understand the relevance of each narrative. The data table that is displayed after each narrative includes the relative association of REST with the terms found most often in the context of REST. The following Table 2.2 is a top portion of a data table for the example narrative:
TABLE 2.2
term1 term2 A B C
CREW REST 9241 264 50.9163
REST REQUIRED 2281 115 36.6896
BLOCK REST 1181 124 34.0992
REST NOT 4639 44 31.9471
DUTY REST 4595 43 31.7172
CAPT REST 1302 66 30.0468
FAR REST 1534 56 29.5285
REST REGS 643 93 29.3084
LEGAL REST 1606 47 28.4199
REST FAA 1207 54 28.3054
NIGHT REST 2375 34 27.4095
REST FEEL 462 60 25.1211
REST SCHEDULED 2372 24 24.6982
REST NEED 693 42 24.4482
REST SCHEDULE 852 35 23.99
The format of Table 2.2 was described in the previous example. In this case Table 2.2 indicates, for example, that CREW is often found in the context of REST in both the database and in this narrative, and CREW typically precedes REST in the database. Further, since the value in column C is greater than that for any of the other term pairs, the contextual association of CREW and REST is stronger than that of any of the other term pairs. The other contextual associations can be interpreted in a similar fashion.
To find narratives relevant to "emergency", the keyterm "emergency" is input to keyterm search and the most relevant narratives are retrieved and displayed, with the corresponding relevant sections highlighted. The following is an example narrative:
A FEW MINS AFTER REACHING FL350 CABIN RAPIDLY DEPRESSURIZED. COCKPIT CREW VERIFIED RAPID DECOMPRESSION, BEGAN EMER DSCNT, DECLARED AN EMER CONDITION WITH ARTCC AND SIMULTANEOUSLY REQUESTED A DIRECT VECTOR TO THE NEAREST SUITABLE ARPT WHICH WAS DETERMINED BY CAPT TO BE STL 110 MI AWAY. ALL EMER CHECKLISTS AND NORMAL CHECKLISTS COMPLETED AND AN UNEVENTFUL APCH AND LNDG WAS MADE. NO INJURIES. I HAVE UNFORTUNATELY DONE 2 EMER DSCNTS IN THE LAST 18 MONTHS DUE TO THE SAME COMPUTER FAILURE OF THE PRESSURIZATION SYS. THE ODDS AGAINST THAT ARE STAGGERING. I BELIEVE THIS ACFT'S AUTO CABIN CTLRS SHOULD BE LOOKED AT CAREFULLY. ALSO, EMER PROC TRAINING AT MY COMPANY FOR EMER DSCNTS NEEDS TO BE REVIEWED AND MODIFIED AS WELL AS THOUGHT GIVEN TO MANY FACTORS NEVER DISCUSSED DURING TRAINING. (110788)
The term "emergency" does not appear in the narrative because the ASRS abbreviates the term "emergency" as "emer". Keyterm search automatically maps or transforms the input keyterm to the ASRS abbreviations, as long as those transformations or mappings are contained in the mapping file used by keyterm search. The mapping file can also be updated or disabled. The highlighted terms include the keyterm (as abbreviated by the ASRS) and those terms that are often found in the context of the query in the narratives of the ASRS database.
A search for narratives relevant to "language", "English", or "phraseology" in a database can be initiated by inputting the keyterms "language", "English", and "phraseology" to keyterm search. Keyterm search then retrieves and ranks the narratives of the database according to their relevance to the typical or selected contexts of these terms in the database. The following is an example of one of the most relevant narratives retrieved and displayed by keyterm search of the ASRS database:
TKOF CLRNC WAS MISUNDERSTOOD BY CREW. TWR CTLR'S ENGLISH WAS NOT VERY CLR AND HE USED INCORRECT PHRASEOLOGY WHICH CAUSED AN APPARENT ALT `BUST.` ATC CLRNC WAS TO 9000 FT, WHICH IS NORMAL FOR THEM. WE WERE USING RWY 21. TKOF CLRNC WAS `CLRED FOR TKOF, RWY HDG 210 DEGS, CONTACT DEP.` DEP SAID WE WERE CLRED TO 2100 FT (AS WE WERE PASSING 3000 FT). EVIDENTLY THE `21` AFTER `RWY HDG` WAS MEANT AS AN AMENDED ALT CLRNC. IF PROPER PHRASEOLOGY HAD BEEN USED, I AM SURE WE WOULD HAVE EITHER UNDERSTOOD OR ASKED FOR A CLARIFICATION. PROPER PHRASEOLOGY IS EVEN MORE IMPORTANT WHEN SPEAKING TO PEOPLE WHOSE PRIMARY LANGUAGE IS NOT ENGLISH. PLTS SHOULD UNDERSTAND THIS BECAUSE OF TRYING TO GIVE POS RPTS, ETC, TO SO MANY DIFFERENT PEOPLE. (236336)
The following are some relevant sentences from other highly relevant narratives:
EXTREMELY DIFFICULT TO COPY CLRNC BECAUSE OF POOR ENGLISH OF CTLR AND NO SPANISH BY PLTS. (306637)
I THINK AN IMMEDIATE REVIEW OF RELATED FIX NAMES FOR SIMILAR SOUNDING NAMES AS PRONOUNCED BY THE LCL SPEAKER'S LANGUAGE IS ESSENTIAL. (242971)
THE COM BTWN THE FRENCH CTLRS AND ENGLISH SPEAKING PLTS HAS BEEN POOR FOR SOME TIME, AND IS GETTING WORSE. (301205)
FLYING A LOT OF TIME IN CENTRAL AND S AMERICA, I EXPERIENCE THAT ATC CTLRS DON'T HAVE FLUENT TALKING AND UNDERSTANDING OF THE ENGLISH LANGUAGE, AS THE WAY HAS TO BE CONSIDERING THAT ENGLISH IS THE UNIVERSAL AND INTL LANGUAGE IN AVIATION. (302310)
THE RPTR SAID THAT HE OFTEN HEARS IMPROPER PHRASEOLOGY DURING HIS FOREIGN OPS. (352400)
MAIQUETIA ATC IS MOST ASSUREDLY BELOW THE ICAO STD FOR ENGLISH SPEAKING CTLRS. (318067)
ALTHOUGH ENGLISH IS THE OFFICIAL LANGUAGE OF TRINIDAD, LCL DIALECT MAKES IT DIFFICULT TO UNDERSTAND CTLRS. (294060)
BETTER ENGLISH SPEAKING FOREIGN CTLRS AND USE OF STD PHRASEOLOGY IS NEEDED. (268223)
SITUATIONAL AWARENESS IS NONEXISTENT WHEN CTLRS SPEAK TO EVERYONE ELSE IN A FOREIGN LANGUAGE AND TO YOU IN BROKEN ENGLISH! (344832)
TWR PHRASEOLOGY WAS NON STD AND HIS COMMAND OF ENGLISH WAS LIMITED, BUT WE WERE CLRED TO LAND. (332620)
Given the keyterms used in this search, the top-ranked narratives typically describe incidents involving miscommunication between air traffic controllers and flight crews due to language barriers, including poor use of the English language and the use of non-standard phraseology. For each search keyterm, here are some of the typical contexts, as indicated by the query models and reflected in the excerpts above:
"Language" is often found in the context of barriers, English and Spanish, clearances, air traffic controllers, ATC, problems, differences, and difficulties.
"English" is often found in the context of speaking and understanding; these attributes of English: poor, broken, or limited; Spanish and French; air traffic controllers; and pilots.
"Phraseology" is often found in the context of standard or proper usage, ATC, air traffic controllers, towers, clearances, and runways.
While the top narratives retrieved in this search all involve "ATC language barrier factors" it should be noted that there was no requirement that the narratives should involve ATC. Since the typical contexts of language barrier factors do, in fact, involve ATC, the top narratives also involved ATC. As a consequence, however, as one goes further down the list of relevant narratives, at some point reports will be found that involve language barrier factors but not ATC.
Keyterm search will take any number of keyterms as queries, as in the above examples, but each term is treated individually. A search on the keyterms "frequency congestion" will return narratives that contain either one or both of these keyterms and their corresponding contexts. There is no guarantee, however, that both of the keyterms will appear in the top-ranked narratives because the search treats each query term as an independent item.
To address this kind of situation, keyterm search can also include a logical intersection of multiple searches. The query for each search can be specified by one or more keyterms. In this example, the "frequency" search uses the query "freq freqs" and requires an exact match. This query avoids matches on terms such as "frequently". The "congestion" search uses the query "congestion congested" and requires an exact match. This query avoids matches on "uncongested". Keyterm search then retrieves and relevance-ranks narratives that contain both "frequency" in context and "congestion" in context.
The following are excerpts from some of the most relevant narratives:
SEVERAL ATTEMPTS WERE MADE TO CONTACT TWR, BUT DUE TO EXTREME CONGESTION ON THIS FREQ NO LNDG CLRNC WAS OBTAINED . . . FREQ 124.15 WAS SO CONGESTED THAT NO ACFT COULD XMIT ON THIS REQ . . . CORRECTIVE ACTIONS: . . . NOTAM FREQ 124.75 AS AN ALTERNATE FREQ ON ATIS [.] DECREASE CONGESTION OF TWR FREQ. (151711)
I FINALLY SWITCHED BACK TO THE ORIGINAL CTLR FREQ BUT, DUE TO CONGESTED FREQ, I SWITCHED TO THE TWR FREQ TO GET THROUGH, WHICH I FINALLY DID . . . MAYBE ON SUBSEQUENT FLTS, IF THIS PROB SHOULD COME ABOUT, IT MIGHT BE A GOOD IDEA TO ALWAYS LEAVE ONE OF THE RADIOS SET TO THE LAST FREQ TO GO BACK TO WHEN THE FREQ GETS BUSY OR WHEN NOBODY SEEMS TO BE WORKING THAT FREQ. (237353)
AFTER CLRING RWY 33L, WE WERE UNABLE TO CONTACT GND CTL DUE TO FREQ CONGESTION . . . TAXIING INBND WITHOUT FIRST RECEIVING A CLRNC IS NOT AT ALL UNUSUAL AT FREQ CONGESTED ARPTS. IN SIMILAR SITS AT BWI AND ELSEWHERE, IF THE FREQ IS BLOCKED AND A CUSTOMARY TAXI RTE IS KNOWN AND CLR OF TFC, NEARLY AL[L] CAPTS I HAVE OBSERVED WOULD PROCEED SLOWLY, AS WE DID. WE PROGRESSED FARTHER THAN MOST ONLY BECAUSE THE FREQ WAS CONGESTED LONGER, IN PART BECAUSE THE CTLR WOULD NOT UNKEY HIS MIC WHILE MAKING MULTIPLE XMISSIONS. (173324)
BECAUSE OF EXTREME FREQ CONGESTION, ABBREVIATED TAXI INSTRUCTIONS ARE GIVEN AT ORD . . . THE FREQ CONGESTION AND CTLR WORKLOAD AT ORD MAKE IT HARD TO VERIFY INSTRUCTIONS THAT ARE UNCLR. WE ATTEMPTED CONTACT A FEW TIMES BEFORE BEING TOLD TO TURN NEAR THE BARRICADES, BUT WERE THEN GIVEN AN IMMEDIATE FREQ CHANGE WHICH PREVENTED PROMPT FEEDBACK FROM THE CTLR WHO GAVE US THE INSTRUCTIONS. TO THEIR CREDIT, THEY DID SPOT THE ERROR QUICKLY AND CALLED ON TWR FREQ WITH NEW INSTRUCTIONS. (WE MAY NOT HAVE HEARD SOME CALLS DUE TO RECEPTION PROBS.) THE CONGESTION AT ORD WOULD BE TOUGH TO FIX, BUT BETTER ARPT SIGNS SHOWING TAXI RTES THROUGH THE CONSTRUCTION AREAS WILL DEFINITELY CUT DOWN ON FUTURE PROBS. (252779)
These and other relevant narratives indicate that the topics "frequency" and "congestion" are often found in the same contexts, but that the exact phrase "frequency congestion" is not always present. Instead, many forms are found, such as:
CONGESTION ON THIS FREQ
FREQ 124.15 WAS SO CONGESTED
CONGESTION OF TWR FREQ
CONGESTED FREQ
FREQ CONGESTION
FREQ CONGESTED
FREQ WAS CONGESTED
A phrase search would also be useful for finding narratives relevant to "frequency congestion". The preceding phrases suggest that an effective search would use a variety of phrase forms as queries, including:
FREQ CONGESTION
FREQ CONGESTED
CONGESTION FREQ
CONGESTED FREQ
Additional phrases include the plural form, "freqs".
FREQS CONGESTION
FREQS CONGESTED
CONGESTION FREQS
CONGESTED
Most keyword search methods use term indexing such as used by Salton, 1981, where a word list represents each document and internal query. As a consequence, given a keyword as a user query, these methods use the presence of the keyword in documents as the main criterion of relevance. In contrast, keyterm search described herein uses indexing by term association, where a list of contextually associated term pairs represents each document and internal query. Given a keyterm as a user query, keyterm search uses not only the presence of the keyterm in the database being searched but also the contexts of the keyterm as the criteria of relevance. This allows retrieved documents to be sorted on their relevance to the keyterm in context.
Some methods such as Jing and Croft (1994), Gauch and Wang (1996), Xu and Croft (1996), and McDonald, Ogden, and Foltz (1997), utilize term associations to identify or display additional query keywords that are associated with the user-input keywords. These methods do not use term association to represent documents and queries, however, and instead rely on term indexing. As a consequence, "query drift" occurs when the additional query keywords retrieve documents that are poorly related or unrelated to the original keywords. Further, term index methods are ineffective in ranking documents on the basis of keyterms in context.
Unlike the keyterm search method described herein, the proximity indexing method of Hawking and Thistlewaite (1996, 1996) does not create a model of the query or models of the documents of the database. In the Hawking and Thistlewaite (1996, 1996) method, a query consists of a user-identified collection of words. These query words are compared with the words in the documents of the database. This search method of Hawking and Thistlewaite (1996, 1996) seeks documents containing length-limited sequences of words that contain subsets of the query words. Documents containing greater numbers of query words in shorter sequences of words are considered to have greater relevance. This is substantially different from the method of keyterm search describ |
