METHOD AND SYSTEM FOR ENHANCED DATA SEARCHING

• US 20040221235A1
• Filed: 11/08/2001
• Published: 11/04/2004
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: Fiver LLC
• Original Assignee: Insightful Corporation (Cloud Software Group)
• Inventors: Liang, Jisheng, Nguyen, Thien, Koperski, Krzysztof, Marchisio, Giovanni B., Murua, Alejandro
• Granted Patent: US 7,283,951 B2
• Time in Patent Office: Days
• US Class Current: 715/261
• 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

Abstract of Disclosure

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. 2.(New)A method in a computer system for transforming a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

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

10. 11.(New)The method of claim 2 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. 12. (New)The method of claim 2 wherein heuristics are used to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

12. 13.(New)The method of claim 2 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. 14.(New)The method of claim 2 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, and verb modifier.

14. 15.(New)The method of claim 2 wherein the document is part of a corpus of heterogeneous documents.

15. 16.(New)The method of claim 2 wherein the enhanced data representation data structure is used to index a corpus of documents.

16. 17.(New)The method of claim 2 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

3. 4.(New)The method of claim 3 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. 5.(New)The method of claim 3 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. 6.(New)The method of claim 3 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. 7.(New)The method of claim 3 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. 8.(New)The method of claim 3 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. 9.(New)The method of claim 3 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. 10.(New)The method of claim 3 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.

17. 18.(New)The method of claim 17 wherein 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.

21. 22.(New)The method of claim 17 wherein 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.

22. 23. (New)The method of claim 17 further comprising adding additional grammatical relationships to the enhanced data representation data structure to be used to execute a query against objects in a corpus of documents.

24. 25.(New)The method of claim 17 wherein weighted results are returned that satisfy the query.

18. 19.(New)The method of claim 18 wherein the objects in the corpus are sentences and indications of sentences that satisfy the query are returned.

19. 20.(New)The method of claim 18, further comprising returning indications of documents that contain similar terms to those found in at least one indicated sentence.

20. 21.(New)The method of claim 18, further comprising returning indications of documents that contain similar terms to those found in at least one indicated document.

23. 24.(New)The method of claim 23 wherein at least one of entailed verbs and related verbs are used to add additional grammatical relationships.

25. 26.(New)A computer-readable memory medium containing instructions for controlling a computer processor to transform a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, by:

26. 27. (New)A syntactic query engine for transforming a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

27. 28.(New)The query engine of claim 27 wherein the postprocessor uses heuristics to determine the additional grammatical role for the at least one of the meaningful terms.

35. 36.(New)The query engine of claim 27 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.

36. 37. (New)The query engine of claim 27 wherein the postprocessor uses heuristics to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

37. 38.(New)The query engine of claim 27 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.

38. 39.(New)The query engine of claim 27 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, and verb modifier.

39. 40.(New)The query engine of claim 27 wherein the document is part of a corpus of heterogeneous documents.

40. 41.(New)The query engine of claim 27 wherein the enhanced data representation data structure is used to index a corpus of documents.

41. 42.(New)The query engine of claim 27, further comprising a query processor that uses the enhanced data representation data structure to execute a query against objects in a corpus of documents.

28. 29.(New)The query engine of claim 28 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.

29. 30.(New)The query engine of claim 28 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.

30. 31.(New)The query engine of claim 28 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.

31. 32.(New)The query engine of claim 28 wherein the postprocessor associates a meaningful term with a subject as the determined grammatical role and with an object as the additional grammatical role.

32. 33.(New)The query engine of claim 28 wherein the postprocessor associates a meaningful term with a object as the determined grammatical role and with a subject as the additional grammatical role.

33. 34.(New)The query engine of claim 28 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.

34. 35.(New)The query engine of claim 28 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.

42. 43.(New)The query engine of claim 42 wherein 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.

46. 47.(New)The query engine of claim 42 wherein 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.

47. 48. (New)The query engine of claim 42 wherein the query processor adds additional grammatical relationships to the enhanced data representation data structure to be used to execute a query against objects in a corpus of documents.

48. 49.(New)The query engine of claim 42 wherein the query processor returns weighted results that satisfy the query.

43. 44.(New)The query engine of claim 43 wherein the objects in the corpus are sentences and the query processor returns indications of sentences that satisfy the query.

44. 45.(New)The query engine of claim 43 wherein the query processor returns indications of documents that contain similar terms to those found in at least one indicated sentence.

45. 46.(New)The query engine of claim 43 wherein the query processor returns indications of documents that contain similar terms to those found in at least one indicated document.

49. 50.(New)A method in a computer system for transforming a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

50. 51.(New)The method of claim 50, further comprising storing the full grammar of the sentence.

51. 52.(New)The method of claim 50, further comprising, when it is determined that a noun modifier grammatical role is associated with one of the meaningful terms, associating the one of the meaningful terms with a subject grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as a subject of the sentence.

52. 53.(New)The method of claim 50, further comprising, when it is determined that a noun modifier grammatical role is associated with one of the meaningful terms, associating the one of the meaningful terms with an object grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as an object of the sentence.

53. 54.(New)The method of claim 50, further comprising, when it is determined that a verb modifier of a prepositional phrase is a grammatical role associated with one of the meaningful terms, associating the one of the meaningful terms with an object grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as an object of the sentence.

54. 55. (New)The method of claim 50 wherein heuristics are used to determine which grammatical relationships are to be stored in the enhanced data representation data structure.

55. 56. (New)The method of claim 50 wherein a plurality of grammatical relationships between meaningful terms that are identical are stored in the enhanced data representation data structure.

56. 57.(New)The method of claim 50 wherein the document is part of a corpus of heterogeneous documents.

57. 58.(New)The method of claim 50 wherein the enhanced data representation data structure is used to index a corpus of documents.

58. 59.(New)The method of claim 50 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

59. 60.(New)The method of claim 59 wherein 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.

63. 64.(New)The method of claim 59 wherein 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.

64. 65.(New)The method of claim 59 further comprising adding additional grammatical relationships to the enhanced data representation data structure to be used to execute a query against objects in a corpus of documents.

66. 67.(New)The method of claim 59 wherein weighted results are returned that satisfy the query.

60. 61.(New)The method of claim 60 wherein the objects in the corpus are sentences and indications of sentences that satisfy the query are returned.

61. 62.(New)The method of claim 60, further comprising returning indications of documents that contain similar terms to those found in at least one indicated sentence.

62. 63.(New)The method of claim 60, further comprising returning indications of documents that contain similar terms to those found in at least one indicated document.

65. 66.(New)The method of claim 65 wherein at least one of entailed verbs and related verbs are used to add additional grammatical relationships.

67. 68. (New)A computer-readable memory medium containing instructions for controlling a computer processor to transform a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, by:

68. 69. (New)A syntactic query engine for transforming a document of a data set into a canonical representation, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

69. 70.(New)The query engine of claim 69 wherein the postprocessor stores the full grammar of the sentence.

70. 71.(New)The query engine of claim 69 wherein the postprocessor, when it is determined that a noun modifier grammatical role is associated with one of the meaningful terms, is further structured to associate the one of the meaningful terms with a subject grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as a subject of the sentence.

71. 72.(New)The query engine of claim 69 wherein the postprocessor, when it is determined that a noun modifier grammatical role is associated with one of the meaningful terms, is further structured to associate the one of the meaningful terms with an object grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as an object of the sentence.

72. 73.(New)The query engine of claim 69 wherein the postprocessor, when it is determined that a verb modifier of a prepositional phrase is a grammatical role associated with one of the meaningful terms, is further structured to associate the one of the meaningful terms with an object grammatical role, thereby indicating that the one of the meaningful terms is to be stored also as an object of the sentence.

73. 74.(New)The query engine of claim 69 wherein the document is part of a corpus of heterogeneous documents.

74. 75.(New)The query engine of claim 69 wherein the enhanced data representation data structure is used to index a corpus of documents.

75. 76.(New)The query engine of claim 69 wherein the enhanced data representation data structure is used to execute a query against objects in a corpus of documents.

76. 77.(New)The query engine of claim 76 wherein the objects in the corpus are sentences and the query processor returns indications of sentences that satisfy the query.

77. 78.(New)The query engine of claim 76 wherein the query processor returns indications of documents that contain similar terms to those found in at least one indicated sentence.

78. 79.(New)The query engine of claim 76 wherein the query processor returns indications of documents that contain similar terms to those found in at least one indicated document.

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

80. 81.(New)A method in a computer system for storing a normalized data structure representing a document of a data set, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

81. 82.(New)The method of claim 81, further comprising storing meaningful terms that correspond to a designated attribute.

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

83. 84.(New)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:

84. 85.(New)A computer-readable memory medium containing instructions for controlling a computer processor to store a normalized data structure representing a document of a data set, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

85. 86.(New)A computer system for storing a normalized data structure representing a document of a data set, the document having a plurality of sentences, each sentence having a plurality of terms, comprising:

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

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

88. 89.(New)A method in a computer system for transforming an object of a data set into a canonical representation for use in indexing the objects of the data set and in querying the data set, the object being other than a text-only document and having a plurality of units that are specified according to an object-specific grammar, comprising:

89. 90.(New)The method of claim 89 wherein the objects are audio data and the units of objects are portions of audio data.

90. 91.(New)The method of claim 89 wherein the objects are video data and the units of objects are portions of video data.

91. 92.(New)The method of claim 89 wherein the objects are images and the units of objects are graphical data.

92. 93. (New)A computer-readable memory medium containing instructions for controlling a computer processor to transform an object of a data set into a canonical representation for use in indexing the objects of the data set and in querying the data set, the object being other than a text-only document and having a plurality of units that are specified according to an object-specific grammar, by:

93. 94.(New)A query engine in a computer system for transforming an object of a data set into a canonical representation for use in indexing the objects of the data set and in querying the data set, the object being other than a text-only document and having a plurality of units that are specified according to an object-specific grammar, comprising: