METHOD AND SYSTEM FOR EXTENDING KEYWORD SEARCHING TO SYNTACTICALLY AND SEMANTICALLY ANNOTATED DATA

• US 20090271179A1
• Filed: 03/10/2009
• Published: 10/29/2009
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: Fiver LLC
• Original Assignee: EVRI Incorporated
• Inventors: Liang, Jisheng, Brown, Matthew E., Dhillon, Navdeep S., Pochman, Lubos, Nguyen, Thien, Koperski, Krzysztof, Marchisio, Giovanni B., Tusk, Carsten
• Granted Patent: US 8,131,540 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and systems for extending keyword searching techniques to syntactically and semantically annotated data are provided. Example embodiments provide a Syntactic Query Engine (“SQE”) that parses, indexes, and stores a data set as an enhanced document index with document terms as well as information pertaining to the grammatical roles of the terms and ontological and other semantic information. In one embodiment, the enhanced document index is a form of term-clause index, that indexes terms and syntactic and semantic annotations at the clause level. The enhanced document index permits the use of a traditional keyword search engine to process relationship queries as well as to process standard document level keyword searches. In one embodiment, the SQE comprises a Query Processor, a Data Set Preprocessor, a Keyword Search Engine, a Data Set Indexer, an Enhanced Natural Language Parser (“ENLP”), a data set repository, and, in some embodiments, a user interface or an application programming interface.

Claims

1. A method in a computer system for performing a relationship search of a corpus of documents, each document having at least one sentence, comprising:

receiving a relationship search query that designates a desired grammatical relationship between a first entity and at least one of a second entity or an action;

transforming the search query into a Boolean expression;

under control of the computer system, automatically determining a set of data objects that match the Boolean expression using a keyword-style search of a data structure that indexes terms of the documents in a memory of the computer system by including, for at least one of a plurality of terms, grammatical relationship information that specifies that the term is a subject, object, or modifier of another term, and including for at least one of the plurality of terms, semantic information that specifies an entity type that identifies the term as a type of person, location, or thing; and

returning an indication of a plurality of matching objects in the corpus that encompass the desired grammatical relationship.

2. The method of claim 1 wherein the automatically determining the set of data objects determines objects that are at least one of clauses, sentences, paragraphs, or documents.

3. The method of claim 1 wherein the data structure stores the grammatical relationship information and semantic information as additional terms of the documents.

4. The method of claim 1 wherein the designated at least one second entity or the action indicates a desire to match any second entity.

5. The method of claim 4, each sentence of each document comprising at least one clause, wherein the any second entity is any term used as a subject of a clause of a sentence.

6. The method of claim 4, each sentence of each document comprising at least one clause, wherein the any second entity is any term used as an object of a clause of a sentence.

7. The method of claim 1 wherein the first entity is any term that matches a specified entity type or ontology path specification.

8. The method of claim 1 wherein the designated at least one second entity or the action indicates a desire to match any action.

9. The method of claim 1 wherein the designated at least one second entity or the action is a verb and wherein the returning the indication of the plurality of matching objects that encompasses the desired relationship returns indications to objects that contain similar verbs to the designated verb.

10. The method of claim 1 wherein the designated at least one second entity or the action indicates a desire to match any action and a desire to match any second entity.

11. The method of claim 1 wherein the receiving the relationship search query that designates the desired grammatical relationship between the first entity and at least one of the second entity or the action specifies at least one of a prepositional constraint, a document keyword constraint, or a document metadata constraint.

12. The method of claim 1 wherein the relationship search query includes a Boolean operation.

13. The method of claim 1 wherein the relationship search query includes an operator that specifies at least one of a proximity, a range, a wildcard, a weighted search based upon frequency, or a weighted keyword search operation.

14. The method of claim 1 wherein the relationship search query includes a designation of at least one entity type or a path specification in a classification system.

15. The method of claim 1 wherein the relationship search query includes a wildcard specification in the designation of the desired grammatical relationship.

16. The method of claim 1 wherein the transforming the search query to generate a Boolean expression incorporates transformational grammar rules to generate related grammatical relationships to search for.

17. The method of claim 1, the returning the indication of the plurality of matching objects in the corpus that encompass the desired relationship comprising:

in response to receiving a search query that designates a desired grammatical relationship between a first entity and any action, returning an indication of each matching object in the corpus that encompasses the first entity along with an indication of a corresponding action encompassed in the matching object.

18. A computer-readable memory medium containing instructions that control a computer processor to search a corpus of documents, each document having at least one sentence, by performing a method comprising:

receiving a relationship search query that designates a desired grammatical relationship between a first entity and at least one of a second entity or an action;

transforming the search query into a Boolean expression;

determining a set of data objects that match the Boolean expression using a keyword-style search of a data structure that indexes terms of the documents by including, for at least one of a plurality of the terms, grammatical relationship information that specifies that the term is a subject, object, or modifier of another term, and including for at least one of the plurality of terms, semantic information that specifies an entity type that identifies the term as a type of person, location, or thing; and

returning an indication of a plurality of matching objects in the corpus that encompass the desired relationship.

19. The memory medium of claim 18 wherein the determined data objects are at least one of clauses, sentences, paragraphs, or documents.

20. The memory medium of claim 18 wherein the data structure stores the grammatical relationship information and the semantic information as additional terms of the documents.

21. The memory medium of claim 18 wherein the designated at least one second entity or the action indicates a desire to match any second entity.

22. The memory medium of claim 18 wherein the first entity is any term that matches a specified entity type or ontology path specification.

23. The memory medium of claim 18 wherein the designated at least one second entity or the action indicates a desire to match any action.

24. The memory medium of claim 18 wherein the designated at least one second entity or the action is a verb and the returning the indication of the plurality of matching objects that encompass the desired relationship returns indications to objects that contain similar verbs to the designated verb.

25. The memory medium of claim 18 wherein the designated desired grammatical relationship specifies at least one of a prepositional constraint, a document keyword constraint, or a document metadata constraint.

26. The memory medium of claim 18 wherein the search query includes an operator that specifies at least one of a proximity, a range, a wildcard, a weighted search based upon frequency, or a weighted keyword search operation.

27. The memory medium of claim 18 wherein the data structure is a reverse index of terms that indexes at least one of documents, sentences, or clauses.

28. The memory medium of claim 18, the returning the indication of the plurality of objects in the corpus that encompass the desired relationship comprising:

in response to receiving a search query that designates a desired grammatical relationship between a first entity and any action, returning an indication of a plurality of objects in the corpus that encompass the first entity along with an indication of a corresponding action encompassed in the matching object.

29. A relationship search engine that searches a corpus of documents, each document having at least one sentence, comprising:

a memory;

a data structure that is configured to index and store in the memory terms of the documents along with annotations that include relationship information, each annotation associated with at least one term, wherein the relationship information stored with at least a corresponding one of the terms specifies an entity type that identifies the corresponding term as a type of person, place, or thing;

a keyword search engine that is configured, when executed on a computer processor, to perform pattern matches of an input string against the data structure and return an indication of a plurality of matching objects of the corpus; and

a query processor that is configured, when executed on a computer processor, to

receive a relationship search query that is indicative of at least one syntactically or semantically annotated term;

transform the relationship search query into at least one Boolean expression; and

invoke the keyword search engine to determine and return indications to objects that match the at least one Boolean expression by pattern matching the at least one annotated term indicated by the search query to the data structure, such that each matching object encompasses the relationship specified by the relationship search.

30. The relationship search engine of claim 29 wherein the returned indications indicate at least one of clauses, sentences, paragraphs, or documents.

31. The relationship search engine of claim 29 wherein the data structure stores the relationship information as additional terms of the documents.

32. The relationship search engine of claim 29 wherein the annotations that include relationship information denote a grammatical role of each associated term.

33. The relationship search engine of claim 29 wherein the annotations denote semantic tags associated with the terms.

34. The relationship search engine of claim 29 wherein the data structure is a reverse index of terms that indexes at least one of documents, sentences, or clauses.

35. The relationship search engine of claim 34 wherein the reverse index of terms comprises a plurality of reverse indices of terms.

36. The relationship search engine of claim 29 wherein the data structure is at least one of a term-document matrix, a term-sentence matrix, or a term-clause matrix.

37. The relationship search engine of claim 29, the data structure further configured to store and index the terms if the documents with the annotations across a plurality of storage repositories, and wherein the keyword search engine is further configured to perform pattern match searches of the input string against each storage repository that contains a portion of the index and merge the results of the pattern match searches to return an indication to each matching object in the corpus that encompasses the desired relationship.

38. The relationship search engine of claim 37 wherein the pattern match searches of the input string against each storage repository that contains the portion of the index are performed using parallel processing techniques.