Method and system for enhanced data searching

• US 7,398,201 B2
• Filed: 02/19/2003
• Issued: 07/08/2008
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: Fiver LLC
• Original Assignee: EVRI Incorporated
• Inventors: Marchisio, Giovanni B., Pochman, Lubos, Dhillon, Navdeep S., Tusk, Carsten, Nguyen, Thien, Murua, Alejandro, Liang, Jisheng, Koperski, Krzysztof
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Sked, Matthew J.
• Application Number:
  US10/371,399
• Publication Number:
  US 20030233224A1
• Time in Patent Office: 1,966 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
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and systems for syntactically indexing and searching data sets to achieve more accurate search results and for indexing and searching data sets using entity tags alone or in combination therewith 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 according to a variety of levels of parsing and determines as appropriate the entity tags and 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 also using a variety of parsing levels and searches the indexed stored data set to locate data that contains similar terms used in similar grammatical roles and/or with similar entity tag types as indicated by the query. 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 using entity tags, comprising:

receiving a designation of a plurality of entity tags, each entity tag having a type and a value, wherein the type of each entity tag is a possible attribute of a sentence that does not represent a part-of-speech and does not represent a grammatical role; and

for each sentence,

parsing the sentence to generate a parse structure having a plurality of syntactic elements that correspond to parts-of-speech;

determining from the syntactic elements of the parse structure a set of terms that correspond to one or more of the designated entity tags; and

for each term of one or more terms of the determined set of terms, storing in an enhanced data representation data structure a representation of an association between the term and a corresponding entity tag, the representation including the term and an indication of the type of the corresponding entity tag, wherein the term is the value of the corresponding entity tag, such that the sentence is represented in the data structure by at least one entity tag.

2. The method of claim 1 wherein the enhanced data representation stores a plurality of entity tags to represent a sentence without needing to store parts-of-speech information.

3. The method of claim 1 wherein, in each stored representation, the type of the corresponding entity tag indicates at least one of a name, a date, a location, a gene, a content identifier, a chemical, or a compound.

4. The method of claim 1, each sentence having a plurality of clauses, wherein each clause of a parsed sentence is represented in the enhanced data representation data structure by at least one entity tag.

5. The method of claim 1 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a name.

6. The method of claim 5 wherein the name is at least one of a person name, a company name, an organization name, a genetic name, a pharmaceutical name, a compound name, a chemical name or a document name.

7. The method of claim 1 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a location.

8. The method of claim 7 wherein the location indicates at least one of a physical location, a geographic location, a country, a city, a region, a state, a locality, a phone number, or an address.

9. The method of claim 1 wherein the stored indication of the type of the corresponding entity tag is a date specification.

10. The method of claim 1 wherein the determining from the parse structure the set of terms that correspond to one or more of the designated entity tags is performed by evaluating a tag value specification associated with each designated entity tag type.

11. The method of claim 1 wherein the designated entity tags are stored in a look-up table and wherein the determining from the parse structure the set of terms is performed by looking up terms associated with the syntactic elements of the parse structure in the stored look-up table.

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

13. The method of claim 12 wherein the enhanced data representation data structure is used to index the corpus of documents.

14. 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.

15. The method of claim 14 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains the same entity tag values and corresponding entity tag types as those stored in the enhanced data representation.

16. The method of claim 14 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains a similar entity tag type to an entity tag type stored in the enhanced data representation.

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 indicate paragraphs.

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

20. The method of claim 16, further comprising:

receiving an indication of at least one sentence of the document; and

returning indications of documents in the corpus that contain similar terms to terms of the indicated at least one sentence.

21. The method of claim 20 wherein the determination of indications of documents that contain similar terms is performed by determining the documents in the corpus that contain similar entity tag values and corresponding entity tag types to those found in the enhanced data representation that corresponds to the at least one indicated sentence.

22. The method of claim 20 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

23. The method of claim 20 wherein the at least one indicated sentence is at least one of an indicated paragraph and an indicated document.

24. The method of claim 23 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

25. A computer-readable memory medium containing content that, when executed, cause a computing system to transform at least one sentence of a document or a query into a canonical representation using entity tags by performing a method comprising:

receiving a designation of a plurality of entity tags, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of a sentence that does not represent a part-of-speech and does not represent a grammatical role; and

for each sentence,

parsing the sentence to generate a parse structure having a plurality of syntactic elements that represent syntactical attributes of the sentence;

determining from the syntactic elements of the parse structure a set of meaningful terms that correspond to one or more of the designated entity tags; and

for each of one or more of the meaningful terms, storing in an enhanced data representation data structure a representation of an association between the term and a corresponding entity tag, the representation including the term and an indication of the type of the corresponding entity tag, wherein the term is the value of the corresponding entity tag, such that the sentence is represented in the data structure by at least one entity tag.

26. The computer-readable memory medium of claim 25 wherein the enhanced data representation stores a plurality of entity tags to represent a sentence.

27. The computer-readable memory medium of claim 25 wherein, in each stored representation, the type of the corresponding entity tag indicates at least one of a name, a date, a location, a gene, a content identifier, a chemical, or a compound.

28. The computer-readable memory medium of claim 25, each sentence having a plurality of clauses, wherein each clause of a parsed sentence is represented in the enhanced data representation data structure by at least one entity tag.

29. The computer-readable memory medium of claim 25 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a name.

30. The computer-readable memory medium of claim 29 wherein the name is at least one of a person name, a company name, an organization name, a genetic name, a pharmaceutical name, a compound name, a chemical name, or a document name.

31. The computer-readable memory medium of claim 25 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a location.

32. The computer-readable memory medium of claim 31 wherein the location indicates at least one of a physical location, a geographic location, a country, a city, a region, a state, a locality, a phone number, or an address.

33. The computer-readable memory medium of claim 25 wherein the stored indication of the type of the corresponding entity tag is a date specification.

34. The computer-readable memory medium of claim 25 wherein the determining from the parse structure the set of meaningful terms that correspond to the one or more of the designated entity tags is performed by evaluating a tag value specification associated with each designated entity tag type.

35. The computer-readable memory medium of claim 25 wherein the designated entity tags are stored in a look-up table and wherein the determining from the parse structure the set of meaningful terms is performed by using the stored look-up table.

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

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

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

39. The computer-readable memory medium of claim 38 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains the same entity tag values and corresponding entity tag types as those stored in the enhanced data representation.

40. The computer-readable memory medium of claim 38 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains a similar entity tag type to an entity tag type stored in the enhanced data representation.

41. The computer-readable memory medium of claim 40 wherein the objects in the corpus are sentences and indications of sentences that satisfy the query are returned.

42. The computer-readable memory medium of claim 41 wherein the returned indications of sentences indicate paragraphs.

43. The computer-readable memory medium of claim 41 wherein the returned indications of sentences indicate documents.

44. The computer-readable memory medium of claim 40, wherein the instructions further control the computer processor by:

receiving an indication of at least one sentence of the document; and

returning indications of documents in the corpus that contain similar terms to terms of the indicated at least one sentence.

45. The computer-readable memory medium of claim 44 wherein the determination of indications of documents that contain similar terms is performed by determining the documents in the corpus that contain similar entity tag values and corresponding entity tag types to those found in the enhanced data representation that corresponds to the at least one indicated sentence.

46. The computer-readable memory medium of claim 44 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

47. The computer-readable memory medium of claim 44 wherein the at least one indicated sentence is at least one of an indicated paragraph and an indicated document.

48. The computer-readable memory medium of claim 47 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

49. The computer-readable memory medium of claim 25 wherein the contents are instructions that, when executed, cause the computing system to perform the method.

50. A syntactic query engine for transforming at least one sentence of a document or a query into a canonical representation using entity tags, comprising:

a memory medium containing a parser that is configured to, when executed on a computer processor,

receive a designation of a plurality of entity tags, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of a sentence that does not represent a part-of-speech and does not represent a grammatical role; and

decompose the at least one sentence to generate a parse structure for the sentence having a plurality of syntactic elements that correspond to parts-of-speech;

determine from the syntactic elements of the parse structure a set of meaningful terms that correspond to one or more of the designated entity tags; and

for each of one or more of the meaningful terms, store, in an enhanced data representation data structure, a representation of an association between the term and the corresponding entity tag, the representation including the term and an indication of the type of the corresponding entity tag, wherein the term is the value of the corresponding entity tag, such that the at least one sentence is represented in the data structure by at least one entity tag.

51. The query engine of claim 50 wherein the enhanced data representation stores a plurality of entity tags to represent a sentence.

52. The query engine of claim 50 wherein, in each stored representation, the type of the corresponding entity tag indicates at least one of a name, a date, a location, a gene, a content identifier, a chemical, or a compound.

53. The query engine of claim 50, the at least one sentence having a plurality of clauses, wherein each clause of the decomposed sentence is represented in the enhanced data representation data structure by at least one entity tag.

54. The query engine of claim 50 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a name.

55. The query engine of claim 54 wherein the name is at least one of a person name, a company name, an organization name, a genetic name, a pharmaceutical name, a compound name, a chemical name, or a document name.

56. The query engine of claim 50 wherein the stored indication of the type of the corresponding entity tag indicates that the sentence specifies a location.

57. The query engine of claim 56 wherein the location indicates at least one of a physical location, a geographic location, a country, a city, a region, a state, a locality, a phone number, or an address.

58. The query engine of claim 50 wherein the stored indication of the type of the corresponding entity tag is a date specification.

59. The query engine of claim 50 wherein the determining from the parse structure the set of meaningful terms that correspond to the one or more of the designated entity tags is performed by evaluating a tag value specification associated with each designated entity tag type.

60. The query engine of claim 50 wherein the designated entity tags are stored in a look-up table and wherein the determining from the parse structure the set of meaningful terms is performed using the stored look-up table.

61. The query engine of claim 50 wherein the document is part of a corpus of heterogeneous documents.

62. The query engine of claim 61 wherein the enhanced data representation data structure is used to index the corpus of documents.

63. The query engine of claim 50 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

64. The query engine of claim 63 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains the same entity tag values and corresponding entity tag types as those stored in the enhanced data representation.

65. The query engine of claim 63 wherein the enhanced data representation corresponds to the query and results are returned that satisfy the query when an object in the corpus contains a similar entity tag type to an entity tag type stored in the enhanced data representation.

66. The query engine of claim 65 wherein the objects in the corpus are sentences and indications of sentences that satisfy the query are returned.

67. The query engine of claim 66 wherein the returned indications of sentences indicate paragraphs.

68. The query engine of claim 66 wherein the returned indications of sentences indicate documents.

69. The query engine of claim 65, the memory further comprising:

search mechanism that is configured to, when executed,

receive an indication of at least one sentence of the document; and

return indications of documents in the corpus that contain similar terms to terms of the indicated at least one sentence.

70. The query engine of claim 68 wherein the determination of indications of documents that contain similar terms is performed by determining the documents in the corpus that contain similar entity tag values and corresponding entity tag types to those found in the enhanced data representation that corresponds to the at least one indicated sentence.

71. The query engine of claim 69 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

72. The query engine of claim 69 wherein the at least one indicated sentence is at least one of an indicated paragraph and an indicated document.

73. The query engine of claim 72 wherein the determination of indications of documents that contain similar terms is performed using latent semantic regression techniques.

74. A method in a computer system for transforming at least one sentence of a document or a query into a canonical representation using entity tags, comprising:

receiving a designation of a plurality of entity tags and a designation of at least one grammatical role, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of a sentence that does not represent a part-of-speech and does not represent a grammatical role; and

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 of the parse structure;

determining from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term;

determining from the set of meaningful terms a first set of terms that corresponds to one or more of the designated entity tags and a second set of terms that corresponds to the designated grammatical role; and

storing in an enhanced data representation data structure a representation of an association between a term of the first set, a designated entity tag that corresponds to the term of the first set, and a term of the second set that corresponds to the designated grammatical role, the representation including the term of the first set, an indication of the type of the corresponding entity tag, wherein the term of the first set is the value of the corresponding entity tag, and the term of the second set, such that the sentence is represented by at least one entity tag and one meaningful term having a grammatical role.

75. The method of claim 74 wherein the designated grammatical role is a governing verb and the enhanced data representation stores a meaningful term that corresponds to a governing verb of the sentence and at least one entity tag.

76. The method of claim 75, each sentence comprising at least one clause, wherein there is a governing verb associated with each clause of each sentence and the stored enhanced data representation, for each clause of each sentence, stores the meaningful term that corresponds to the associated governing verb.

77. The method of claim 74 wherein the enhanced data representation for each sentence stores a plurality of meaningful terms and their corresponding grammatical roles and at least one entity tag.

78. The method of claim 74 wherein the enhanced data representation for each sentence stores a representation of an association between each meaningful term of the second set of the meaningful terms and its corresponding grammatical role and an association between each meaningful term of the first set of the meaningful terms and its corresponding designated entity tag.

79. The method of claim 74 wherein the term of the first set that is associated with the corresponding designated entity tag is the same as the term of the second set that corresponds to the designated grammatical role.

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

81. The method of claim 74 wherein the determining of a grammatical role for each meaningful term includes determining whether the term is at least one of a subject, object, verb, part of a prepositional phrase, noun modifier, or verb modifier.

82. The method of claim 74 wherein the document is part of a corpus of heterogeneous documents.

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

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

85. The method of claim 84 wherein the enhanced data representation data structure corresponds to the query and wherein results are returned that satisfy the query when an object in the corpus contains a term associated with similar grammatical role to the term and its associated role as stored in the enhanced data representation and contains a similar entity tag type to an entity tag type stored in the enhanced data representation.

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

87. A computer-readable medium containing content that, when executed, controls a computing system to transform at least one sentence of a document or a query into a canonical representation using entity tags, by performing a method comprising:

receiving a designation of a plurality of entity tags and a designation of at least one grammatical role, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of a sentence that does not represent a part-of-speech and does not represent a grammatical role; and

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 these syntactic elements;

determining from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term;

determining from the set of meaningful terms a first set of terms that corresponds to one or more of the designated entity tags and a second set of terms that corresponds to the designated grammatical role; and

storing in an enhanced data representation data structure a representation of an association between a term of the first set, a designated entity tag that corresponds to the term of the first set, and a term of the second set that corresponds to the designated grammatical role, the representation including the term of the first set, an indication of the type of the corresponding entity tag, wherein the term of the first set is the value of the corresponding entity tag, and the term of the second set, such that the sentence is represented by at least one entity tag and one meaningful term having a grammatical role.

88. The computer-readable medium of claim 87 wherein the contents are instructions that, when executed, cause the computing system to perform the method.

89. A syntactic query engine for transforming at least one sentence of a document or query into a canonical representation using entity tags, comprising:

a memory containing a parser that is configured to, when executed,

receive a designation of a plurality of entity tags and a designation of at least one grammatical role, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of the at least one sentence that does not represent a part-of-speech and does not represent a grammatical role;

decompose the at least one sentence to generate a parse structure for the sentence having a plurality of syntactic elements that correspond to parts-of-speech;

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

determine from the structure of the parse structure and the syntactic elements a grammatical role for each meaningful term;

determine from the set of meaningful terms a first set of terms that corresponds to one or more of the designated entity tags and a second set of terms that corresponds to the designated grammatical role; and

store, in an enhanced data representation data structure a representation of an association between a term of the first set, a designated entity tag that corresponds to the term of the first set, and a term of the second set that corresponds to the designated grammatical role, the representation including the term of the first set, an indication of the type of the corresponding entity tag, wherein the term of the first set is the value of the corresponding entity tag, and the term of the second set, such that the sentence is represented by at least one entity tag and one meaningful term having a grammatical role.

90. The query engine of claim 89 wherein the designated grammatical role is a governing verb and the enhanced data representation stores a meaningful term that corresponds to a governing verb of the sentence and at least one entity tag.

91. 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:

an entity table having a set of entity tag pairs, each pair having a term of a sentence that is also a value of a corresponding entity tag and an indication of an entity tag type of the corresponding entity tag, wherein the entity tag type is a possible attribute of the sentence that does not represent a part-of-speech and does not represent a grammatical role.

92. A computer-readable memory medium containing instructions that, when executed, control a computing system to store a normalized data structure representing at least one sentence of a document of a data set or a query, by performing a method comprising:

for each sentence,

determining a set of terms of the sentence that correspond to a designated set of entity tags, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of the sentence that does not represent a part-of-speech and does not represent a grammatical role; and

storing sets of relationships between each determined term and its corresponding entity tag type in the normalized data structure, wherein each determined term is the value of its corresponding entity tag, so as to represent the entire sentence as entity tags.

93. A computing system for storing a normalized data structure representing a document of a data set or a query having at least one sentence with a plurality of terms, comprising:

enhanced parsing mechanism that determines a set of terms of the sentence that correspond to a designated set of entity tags, each entity tag having a type and a value, and wherein the type of each entity tag is a possible attribute of the sentence that does not represent a part-of-speech and does not represent a grammatical role; and

storage mechanism structured to store sets of relationships between each determined term and its corresponding entity tag type in the normalized data structure, wherein each determined term is the value of its corresponding entity tag, so as to represent the entire at least one sentence as entity tags.

94. The system of claim 93, the storage mechanism further structured to store terms that correspond to a document level attribute.