Method and system for enhanced data searching

• US 7,283,951 B2
• Filed: 11/08/2001
• Issued: 10/16/2007
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: Fiver LLC
• Original Assignee: Insightful Corporation (Cloud Software Group)
• Inventors: Nguyen, Thien, Murua, Alejandro, Liang, Jisheng, Koperski, Krzysztof, Marchisio, Giovanni B.
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): Sked, Matthew J.
• Application Number:
  US10/007,299
• Publication Number:
  US 20040221235A1
• Time in Patent Office: 2,168 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Methods and systems for syntactically indexing and searching data sets to achieve more accurate search results are provided. Example embodiments provide a Syntactic Query Engine (“SQE”) that parses, indexes, and stores a data set, as well as processes natural language queries subsequently submitted against the data set. The SQE comprises a Query Preprocessor, a Data Set Preprocessor, a Query Builder, a Data Set Indexer, an Enhanced Natural Language Parser (“ENLP”), a data set repository, and, in some embodiments, a user interface. After preprocessing the data set, the SQE parses the data set and determines the syntactic and grammatical roles of each term to generate enhanced data representations for each object in the data set. The SQE indexes and stores these enhanced data representations in the data set repository. Upon subsequently receiving a query, the SQE parses the query similarly and searches the indexed stored data set to locate data that contains similar terms used in similar grammatical roles. In this manner, the SQE is able to achieve more contextually accurate search results more frequently than using traditional search engines.

Claims

1. A method in a computer system for transforming at least one sentence of a document or a query into a canonical representation, each sentence having a plurality of terms, comprising:

for each sentence,

parsing the sentence to generate a parse structure having a plurality of syntactic elements;

determining a set of meaningful terms of the sentence from the syntactic elements;

determining from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term in the set of meaningful terms, wherein the grammatical role is at least one of a subject, object, verb, part of a prepositional phrase, noun modifier, or verb modifier;

determining an additional grammatical role for at least one of the meaningful terms, such that the at least one meaningful term is associated with at least two different grammatical roles, wherein the additional grammatical role is not determined from the parse structure and the additional grammatical role indicates that the at least one of the meaningful terms is a subject or an object in addition to the grammatical role determined from the parse structure; and

storing in an enhanced data representation data structure a representation of each association between a meaningful term and its determined grammatical roles, in a manner that indicates a grammatical relationship between a plurality of the meaningful terms and such that the at least one meaningful term is associated with a plurality of grammatical relationships.

2. The method of claim 1 wherein heuristics are used to determine the additional grammatical role for the at least one of the meaningful terms.

3. The method of claim 2 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with an object as the additional grammatical role.

4. The method of claim 2 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with a subject as the additional grammatical role.

5. The method of claim 2 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with a verb as the additional grammatical role.

6. The method of claim 2 wherein a meaningful term is associated with a subject as the determined grammatical role and is associated with an object as the additional grammatical role.

7. The method of claim 2 wherein a meaningful term is associated with a object as the determined grammatical role and is associated with a subject as the additional grammatical role.

8. The method of claim 2 wherein a meaningful term is associated with a noun modifier as the determined grammatical role and is associated with a subject as the additional grammatical role.

9. The method of claim 2 wherein a meaningful term is associated with a noun modifier as the determined grammatical role and is associated with an object as the additional grammatical role.

10. The method of claim 1 wherein the determined additional grammatical role is a part of grammar that is not implied by the position of the at least one meaningful term relative to the structure of the sentence.

11. The method of claim 1 wherein heuristics are used to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

12. The method of claim 1 wherein the determining the grammatical role for each meaningful term and the determining of the additional grammatical role for at least one of the meaningful terms yields a plurality of grammatical relationships between meaningful terms that are identical.

13. The method of claim 1 wherein the document is part of a corpus of heterogeneous documents.

14. The method of claim 1 wherein the enhanced data representation data structure is used to index a corpus of documents.

15. The method of claim 1 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

16. The method of claim 15 wherein the enhanced data representation data structure corresponds to the query and results are returned that satisfy the query when an object in the corpus contains similar terms associated with similar grammatical roles to the terms and their associated roles as stored in the enhanced data representation that corresponds to the query.

17. The method of claim 16 wherein the objects in the corpus are sentences and indications of sentences that satisfy the query are returned.

18. The method of claim 17 wherein the returned indications of sentences are indications of paragraphs.

19. The method of claim 17 wherein the returned indications of sentences are indications of documents.

20. The method of claim 16, further comprising returning indications of documents that contain similar terms to those found in at least one sentence that was indicated in the results returned that satisfied the query.

21. The method of claim 20 wherein the at least one sentence that was indicated in the results is a paragraph.

22. The method of claim 21 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

23. The method of claim 20 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

24. The method of claim 16, further comprising returning indications of documents that contain similar terms to those found in at least one document that was indicated in the results returned that satisfied the query.

25. The method of claim 24 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

26. The method of claim 15 wherein the enhanced data representation data structure corresponds to the query and terms that are associated with designated grammatical roles are returned for each object in the corpus that contains similar terms associated with similar grammatical roles to the terms and associated roles of designated relationships from the enhanced data representation data structure that corresponds to the query.

27. The method of claim 15 further comprising adding additional grammatical relationships to the enhanced data representation data structure to be used to execute the query against objects in a corpus of documents.

28. The method of claim 27 wherein at least one of entailed verbs or related verbs are used to add additional grammatical relationships.

29. The method of claim 15 wherein weighted results that satisfy the query are returned.

30. The method of claim 1 wherein an enhanced data representation data structure is generated for a plurality of sentences of each document in a corpus of documents as part of indexing the corpus, and further comprising:

receiving a query that specifies only a portion of a grammatical relationship between two terms, the portion being a specification of the relationship or a specification of one of the two terms but not both terms;

transforming the query into an enhanced data representation data structure; and

comparing the enhanced data representation data structure of the query against the enhanced data representation data structures of each indexed sentence such that indications of sentences are returned as matches when the enhanced data representation data structure of the query matches at least one of enhanced data representation data structures of the indexed sentence by using a wildcard to match unspecified information in the grammatical relationship indicated by the enhanced data representation data structure of the query.

31. The method of claim 30 wherein the query specifies only an action.

32. The method of claim 30 wherein the query specifies a single term as either a subject or an object, and further comprising:

when the query specifies the subject, the method returns a matching result when the term appears in an enhanced data representation data structure of an indexed sentence as an object; and

when the query specifies the object, the method returns a matching result when the term appears in an enhanced data representation data structure of an indexed sentence as a subject.

33. A computer-readable memory medium containing instructions for controlling a computer processor to transform at least one sentence of a document or a query into a canonical representation, each sentence having a plurality of terms, by performing a method comprising:

for each sentence,

parsing the sentence to generate a parse structure having a plurality of syntactic elements;

determining a set of meaningful terms of the sentence from the syntactic elements;

determining from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term in the set of meaningful terms, wherein the grammatical role is at least one of a subject, object, verb, part of a prepositional phrase, noun modifier, or verb modifier;

determining an additional grammatical role for at least one of the meaningful terms, such that the at least one meaningful term is associated with at least two different grammatical roles, wherein the additional grammatical role is not determined from the parse structure and the additional grammatical role indicates that the at least one of the meaningful terms is a subject or an object in addition to the grammatical role determined from the parse structure; and

storing in an enhanced data representation data structure a representation of each association between a meaningful term and its determined grammatical roles, in a manner that indicates a grammatical relationship between a plurality of the meaningful terms and such that the at least one meaningful term is associated with a plurality of grammatical relationships.

34. The computer-readable memory medium of claim 33 wherein heuristics are used to determine the additional grammatical role for the at least one of the meaningful terms.

35. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with an object as the additional grammatical role.

36. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with a subject as the additional grammatical role.

37. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a verb modifier as the determined grammatical role and is associated with a verb as the additional grammatical role.

38. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a subject as the determined grammatical role and is associated with an object as the additional grammatical role.

39. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a object as the determined grammatical role and is associated with a subject as the additional grammatical role.

40. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a noun modifier as the determined grammatical role and is associated with a subject as the additional grammatical role.

41. The computer-readable memory medium of claim 33 wherein a meaningful term is associated with a noun modifier as the determined grammatical role and is associated with an object as the additional grammatical role.

42. The computer-readable memory medium of claim 33 wherein the determined additional grammatical role is a part of grammar that is not implied by the position of the at least one meaningful term relative to the structure of the sentence.

43. The computer-readable memory medium of claim 33 wherein heuristics are used to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

44. The computer-readable memory medium of claim 33 wherein the determining the grammatical role for each meaningful term and the determining of the additional grammatical role for at least one of the meaningful terms yields a plurality of grammatical relationships between meaningful terms that are duplicative.

45. The computer-readable memory medium of claim 33 wherein the document is part of a corpus of heterogeneous documents.

46. The computer-readable memory medium of claim 33 wherein the enhanced data representation data structure is used to index a corpus of documents.

47. The computer-readable memory medium of claim 33 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

48. The computer-readable memory medium of claim 47 wherein the enhanced data representation data structure corresponds to the query and results are returned that satisfy the query when an object in the corpus contains similar terms associated with similar grammatical roles to the terms and their associated roles as stored in the enhanced data representation that corresponds to the query.

49. The computer-readable memory medium of claim 48 wherein weighted results that satisfy the query are returned.

50. The computer-readable memory medium of claim 48 wherein a wildcard is used to generate results that satisfy the query.

51. The computer-readable memory medium of claim 47 further comprising adding additional grammatical relationships to the enhanced data representation data structure to be used to execute the query against objects in a corpus of documents.

52. The computer-readable memory medium of claim 51 wherein at least one of entailed verbs or related verbs are used to add additional grammatical relationships.

53. A syntactic query engine for transforming at least one sentence of a document or a query into a canonical representation, each sentence having a plurality of terms, comprising:

parser residing in a memory medium that is configured to, when executed, decompose each sentence to generate a parse structure for the sentence having a plurality of syntactic elements; and

postprocessor residing in a memory medium that is configured to, when executed

receive from the parser the parse structure of the sentence;

determine a set of meaningful terms of the sentence from the syntactic elements;

determine from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term in the set of meaningful terms, wherein the grammatical role is at least one of a subject, object, verb, part of a prepositional phrase, noun modifier, or verb modifier;

determine an additional grammatical role for at least one of the meaningful terms, such that the at least one meaningful term is associated with at least two different grammatical roles, wherein the additional grammatical role is not determined from the parse structure and the additional grammatical role indicates that the at least one of the meaningful terms is a subject or an object in addition to the grammatical role determined from the parse structure; and

store, in an enhanced data representation data structure, a representation of each association between a meaningful term and its determined grammatical roles, in a manner that indicates a grammatical relationship between a plurality of the meaningful terms and such that the at least one meaningful term is associated with a plurality of grammatical relationships.

54. The query engine of claim 53 wherein the postprocessor uses heuristics to determine the additional grammatical role for the at least one of the meaningful terms.

55. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a verb modifier as the determined grammatical role and with an object as the additional grammatical role.

56. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a verb modifier as the determined grammatical role and with a subject as the additional grammatical role.

57. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a verb modifier as the determined grammatical role and with a verb as the additional grammatical role.

58. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a subject as the determined grammatical role and with an object as the additional grammatical role.

59. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a object as the determined grammatical role and with a subject as the additional grammatical role.

60. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a noun modifier as the determined grammatical role and with a subject as the additional grammatical role.

61. The query engine of claim 54 wherein the postprocessor associates a meaningful term with a noun modifier as the determined grammatical role and with an object as the additional grammatical role.

62. The query engine of claim 53 wherein the determined additional grammatical role is a part of grammar that is not implied by the position of the at least one meaningful term relative to the structure of the sentence.

63. The query engine of claim 53 wherein the postprocessor uses heuristics to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

64. The query engine of claim 53 wherein the determining the grammatical role for each meaningful term and the determining of the additional grammatical role for at least one of the meaningful terms yields a plurality of grammatical relationships between meaningful terms that are identical.

65. The query engine of claim 53 wherein the document is part of a corpus of heterogeneous documents.

66. The query engine of claim 53 wherein the enhanced data representation data structure is used to index a corpus of documents.

67. The query engine of claim 53, further comprising a query processor that uses the enhanced data representation data structure to execute a query against objects in a corpus of documents.

68. The query engine of claim 67 wherein the enhanced data representation data structure corresponds to the query and the query processor returns results that satisfy the query when an object in the corpus contains similar terms associated with similar grammatical roles to the terms and their associated roles as stored in the enhanced data representation.

69. The query engine of claim 68 wherein the objects in the corpus are sentences and the query processor returns indications of sentences that satisfy the query.

70. The query engine of claim 69 wherein the returned indications of sentences are indications of paragraphs.

71. The query engine of claim 69 wherein the returned indications of sentences are indications of documents.

72. The query engine of claim 68 wherein the enhanced data representation data structure corresponds to the query and the query processor returns indications of documents that contain similar terms to those found in at least one sentence that was indicated in the results that satisfied the query.

73. The query engine of claim 72 wherein the at least one sentence that was indicated in the results is a paragraph.

74. The query engine of claim 73 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

75. The query engine of claim 72 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

76. The query engine of claim 68 wherein the enhanced data representation data structure corresponds to the query and the query processor returns indications of documents that contain similar terms to those found in at least one document that was indicated in the results that satisfied the query.

77. The query engine of claim 76 wherein the indications of documents that contain similar terms are determined using latent semantic regression techniques.

78. The query engine of claim 67 wherein the enhanced data representation data structure corresponds to the query and the query processor returns terms that are associated with designated grammatical roles for each object in the corpus that contains similar terms associated with similar grammatical roles to the terms and associated roles of designated relationships from the enhanced data representation data structure.

79. The query engine of claim 67 wherein the query processor adds additional grammatical relationships to the enhanced data representation data structure to be used to execute the query against objects in a corpus of documents.

80. The query engine of claim 67 wherein the query processor returns weighted results that satisfy the query.

81. The query engine of claim 67 wherein the query processor associates a wildcard with the query to generate results that satisfy the query.

82. A method in a computer system for storing a normalized data structure representing at least one sentence of a document or a query, each sentence having a plurality of terms, comprising:

determining a set of meaningful terms of each sentence and at least one grammatical role for each meaningful term, wherein the grammatical role is at least one of a subject, object, verb, part of a prepositional phrase, noun modifier, or verb modifier; and

storing sets of grammatical relationships between a plurality of meaningful terms based upon the determined grammatical role of each meaningful term relative to a meaningful term that is being used as a governing verb, wherein, for each meaningful term that is being used as a governing verb, the normalized data structure contains a subject table having a set of meaningful term pairs that are subjects relative to the governing verb, an object table having a set of meaningful term pairs that are objects relative to the governing verb, a subject-object table representing an association between the subject table and the object table, a preposition table having a set of meaningful terms that are verb modifiers of prepositional phrases that relate to the governing verb, and a noun modifier table having a set of meaningful term pairs that are noun modifiers of noun phrases that relate to the governing verb.

83. The method of claim 82, further comprising storing meaningful terms that correspond to a designated attribute.

84. The method of claim 83 wherein the designated attribute is at least one of country name, date, money, amount, number, location, person, corporate name, and organization.

85. A data processing system comprising a computer processor and a memory, the memory containing structured data that stores a normalized representation of sentence data, the structured data being manipulated by the computer processor under the control of program code and stored in the memory as:

a subject table having a set of meaningful term pairs, each pair having a meaningful term that is associated with a grammatical role of a verb and a meaningful term that is associated with a grammatical role of a subject relative to the verb;

an object table having a set of meaningful term pairs, each pair having a meaningful term that is associate with a grammatical role of a verb and a meaningful term that is associated with a grammatical role of an object relative to the verb;

a representation of associations between the subject table and the object table, the representation indicating, for each meaningful term associated with the grammatical role of the verb, the meaningful terms that are associated with the grammatical role of subject relative to the verb and the meaningful terms that are associated with the grammatical role of object relative to the verb;

a preposition table having a set of meaningful term groups, each group having a meaningful term that is associated with a grammatical role of a verb, a meaningful term that is associated with a grammatical role of a preposition relative to the verb, and a meaningful term that is associated with a grammatical role of a verb modifier relative to the verb; and

a noun modifier table having a set of meaningful term pairs, each pair having a meaningful term that is associated with a grammatical role of a noun and a meaningful term that is associated with a grammatical role of an noun modifier relative to the noun.

86. A computer-readable memory medium containing instructions for controlling a computer processor to store in a data repository a normalized data structure representing at least one sentence of a document or a query, each sentence having a plurality of terms, by:

determining a set of meaningful terms of each sentence and at least one grammatical role for each meaningful term; and

storing sets of grammatical relationships between a plurality of meaningful terms based upon the determined grammatical role of each meaningful term relative to a meaningful term that is being used as a governing verb, wherein, for each meaningful term that is being used as a governing verb, the normalized data structure contains a subject table having a set of meaningful term pairs that are subjects relative to the governing verb, an object table having a set of meaningful term pairs that are objects relative to the governing verb, a subject-object table representing an association between the subject table and the object table, a preposition table having a set of meaningful terms that are verb modifiers of prepositional phrases that contain the governing verb, and a noun modifier table having a set of meaningful terms that are noun modifiers of noun phrases that relate to the governing verb.

87. A computer system for storing a normalized data structure representing at least one sentence of a document or a query, each sentence having a plurality of terms, comprising:

enhanced parsing mechanism that determines a set of meaningful terms for each sentence and at least one grammatical role for each meaningful term;

a data repository; and

storage mechanism structured to store in the data repository sets of grammatical relationships between a plurality of the determined meaningful terms based upon the determined grammatical role of each meaningful term relative to a meaningful term that is being used as a governing verb, wherein, for each meaningful term that is being used as a governing verb, the normalized data structure contains entries in a subject table having a set of meaningful term pairs that are subjects relative to the governing verb, an object table having a set of meaningful term pairs that are objects relative to the governing verb, a subject-object table representing a set of associations between the subject table and the object table, a preposition table having a set of meaningful term groups, each group having verb modifiers of prepositional phrases that contain the governing verb, and a noun modifier table having a set of meaningful term pairs that are noun modifiers of noun phrases that relate to the governing verb.

88. The system of claim 87, the storage mechanism further structured to store meaningful terms that correspond to a designated attribute.

89. The system of claim 88 wherein the designated attribute is at least one of country name, date, money, amount, number, location, person, corporate name, and organization.