Method and system for extending keyword searching to syntactically and semantically annotated data

• US 7,953,593 B2
• Filed: 03/10/2009
• Issued: 05/31/2011
• Est. Priority Date: 08/14/2001
• Status: Expired due to Term

• Current Assignee: Fiver LLC
• Original Assignee: EVRI Incorporated
• Inventors: Brown, Matthew E., Pochman, Lubos, Dhillon, Navdeep S., Tusk, Carsten, Nguyen, Thien, Liang, Jisheng, Koperski, Krzysztof, Marchisio, Giovanni B.
• Primary Examiner(s): Sked, Matthew J
• Application Number:
  US12/401,386
• Publication Number:
  US 20090182738A1
• Time in Patent Office: 812 Days
• Field of Search: None
• 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 computer-readable memory medium containing structured data that stores a relationship query, the query configured to be executed by a computer processor under control of a search engine to search a corpus of objects for objects that match the query, comprising:

a base component that specifies one or more values for desired relationship parameters, the relationship parameters comprising one or more entity parameters, at least one action parameter, and at least one directional operator parameter that specifies a direction of relationship between one of the one or more entity parameters and the at least one action parameter;

a prepositional constraint component that specifies a desired value for a prepositional phrase;

a keyword constraint component that specifies one or more desired keyword values separately from and in addition to the values for the desired relationship parameters; and

a metadata constraint component that specifies one or more desired values of metadata associated with each matching object;

whereby, when the search engine causes the search to be executed, objects that match constraints specified by the base component, the prepositional constraint component, the keyword constraint component, and the metadata constraint component are determined to satisfy the query.

2. The memory medium of claim 1 wherein the corpus of objects is a corpus of documents.

3. The memory medium of claim 1 wherein one or more of the components of the relationship query are optional.

4. The memory medium of claim 1 wherein at least one of the components of the relationship query is specified.

5. The memory medium of claim 1 wherein at least one of the components of the relationship query contains a Boolean expression.

6. The memory medium of claim 1 wherein the base component specifies values for the desired relationship parameters in a general relationship form of:

Entity1 Directional-operator 1 Action Directional-operator2 Entity2

wherein at least one of Entity1, Entity2, and Action parameters contains a non null value that indicates a search term, the Directional-operator1 parameter specifies the direction of the relationship between the Entity1 and the Action parameters, and the Directional-operator2 parameter specifies the direction of the relationship between the Entity2 and the Action parameters.

7. The memory medium of claim 6 wherein a value of the Directional-operator1 and Directional-operator2 parameters is one of a greater-than symbol (“

>

”

), a right arrow symbol (“

->

”

), a less-than symbol (“

<

”

), a left arrow symbol (“

<

-”

) or a combination indicating a bi-directional relationship (“

<

>

”

or “

<

->

”

).

8. The memory medium of claim 6 wherein a specification of a value of “

>

”

or “

->

”

for the Directional-operator1 parameter indicates that the value indicated by the Entity1 parameter is a subject of the value indicated by the Action parameter.

9. The memory medium of claim 6 wherein a specification of a value of “

<

”

or “

<

-”

for Directional-operator1 parameter indicates that the value indicated by the Entity1 parameter is an object of the value indicated by the Action parameter.

10. The memory medium of claim 6 wherein a specification of a value of “

>

”

or “

->

”

for Directional-operator2 parameter indicates that the value indicated by the Entity2 parameter is an object of the value indicated by the Action parameter.

11. The memory medium of claim 6 wherein a specification of a value of “

<

”

or “

<

-”

for Directional-operator2 parameter indicates that that the value indicated by the Entity2 parameter is a subject of the value indicated by the Action parameter.

12. The memory medium of claim 6 wherein a value for the Action parameter indicates a search term that represents at least one of a particular verb, similar verbs, or an action type.

13. The memory medium of claim 6 wherein a value for the Action parameter that is in the form of a quoted verb indicates a particular verb;

a value for the Action parameter that in the form of an unquoted verb indicates similar verbs to that which is specified; and

a value for the Action parameter that is in the form of a bracketed verb indicates an action type.

14. The memory medium of claim 6 wherein a value for the Entity1 or the Entity2 parameter is a noun or noun phrase.

15. The memory medium of claim 6 wherein a value for the Entity1 or the Entity2 parameter is a modifier.

16. The memory medium of claim 1 wherein the prepositional constraint component comprises a word or a symbol followed by at least one search term.

17. The memory medium of claim 16 wherein the word is the phrase “

PREP CONTAINS”

or the symbol is the character “

^”

followed by the at least one search term.

18. The memory medium of claim 1 wherein the keyword constraint component comprises a word or a symbol followed by at least one search term.

19. The memory medium of claim 18 wherein the word is the phrase “

DOCUMENT CONTAINS”

or the symbol is the character “

;

”

followed by the at least one search term.

20. The memory medium of claim 1 wherein the metadata constraint component comprises a word or a symbol followed by at least one value.

21. The memory medium of claim 20 wherein the word is the phrase “

METADATA CONTAINS”

or the symbol is the character “

#”

followed by at least one expression that specifies a desired value for a metadata variable.

22. The memory medium of claim 1 wherein a wildcard can be specified as the value of a search term of a prepositional constraint component, a keyword constraint component, or a metadata constraint component or as a parameter of the base component.

23. The memory medium of claim 22 wherein the wildcard is at least one of a single character wildcard operator, the characters “

*”

or “

?”

, a multi-character wildcard operator, or a word wildcard operator.

24. The memory medium of claim 1 wherein square brackets are used to indicate an action type, an entity type, or an entity classification.

25. A computer-based search engine programmed and configured to process relationship queries that are stored in the structured data contained in the computer readable memory medium and configured according to claim 1.

26. A method in a computer system comprising storing relationship queries as data in the structured data contained in the computer readable memory medium and configured according to claim 1.

27. The memory medium of claim 1 wherein the direction of directional operator parameter indicates a grammatical role of the one of the one or more entity parameters.