Iterators for Applying Term Occurrence-Level Constraints in Natural Language Searching

• US 20090070298A1
• Filed: 08/29/2008
• Published: 03/12/2009
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Powerset Inc (Microsoft Corporation)
• Inventors: Thione, Giovanni Lorenzo, Crouch, Richard, Pell, Barney, Walters, Chad
• Granted Patent: US 7,984,032 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

Tools and techniques are described that relate to iterators for applying term occurrence-level constraints in natural language searching. These tools may receive a natural language input query, and define term occurrence-level constraints applicable to the input query. The methods may also identify facts requested in the input query, and may instantiate an iterator to traverse a fact index to identify candidate facts responsive to the input query. This iterator may traverse through at least a portion of the fact index. The methods may receive candidate facts from this iterator, with these candidate facts including terms, referred to as term-level occurrences. The methods may apply the term occurrence-level constraints to the term-level occurrences. The methods may select the candidate fact for inclusion in search results for the input query, based at least in part on applying the term occurrence-level constraint.

Claims

1. At least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

receiving at least one natural language input query;

defining at least one term occurrence-level constraint applicable to the input query;

identifying at least one fact requested in the input query;

instantiating at least one iterator to traverse at least one fact index to identify at least one candidate fact that is responsive to the input query;

traversing the iterator through at least a portion of the fact index;

receiving at least one candidate fact from the iterator, wherein the candidate fact includes at least one term occurrence;

applying the term occurrence-level constraint to the term occurrence; and

selecting the candidate fact for inclusion in search results for the input query, based at least in part on applying the term occurrence-level constraint to the term occurrence.

2. The storage medium of claim 1, further comprising instructions for defining at least a further term occurrence-level constraints applicable to the input query.

3. The storage medium of claim 2, further comprising instructions for applying the further term occurrence-level constraint to at least the term occurrence.

4. The storage medium of claim 3, wherein the instructions for selecting the candidate fact include instructions for selecting the candidate fact based at least in part on applying at least the further term occurrence-level constraint to the term occurrence.

5. The storage medium of claim 1, further comprising instructions for identifying at least a further fact requested in the input query.

6. The storage medium of claim 5, further comprising instructions for instantiating at least a further iterator to locate at least one candidate corresponding to the further fact, in response to the input query.

7. The storage medium of claim 6, further comprising instructions for receiving at least one further candidate fact from the further iterator.

8. The storage medium of claim 7, further comprising instructions for applying at least one fact-level operation to the candidate fact and to at least the further candidate fact.

9. The storage medium of claim 8, wherein the instructions for applying at least one fact-level operation include instructions for performing a Boolean operation involving the candidate fact and at least the further candidate fact.

10. The storage medium of claim 1, further comprising instructions for instantiating at least a further iterator to perform at least one fact-level operation on the candidate fact and at least a second candidate fact, wherein the further iterator is for communicating with the iterator.

11. The storage medium of claim 1, further comprising instructions for instantiating at least a further iterator to apply the term occurrence-level constraint to the term occurrence, wherein the further iterator is for communicating with the iterator.

12. At least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

receiving at least one natural language input query;

defining a plurality of term occurrence-level constraints applicable to the input query;

decomposing the input query into a plurality of sub-queries, wherein a first sub-query relates to a first fact requested in the input query, and wherein at least a second sub-query relates to a second fact requested in the input query;

instantiating a first iterator to identify at least a first candidate fact that is responsive to the input query and that relates to the first fact;

instantiating at least a second iterator to identify at least a first candidate fact that is responsive to the input query and that relates to the second fact;

traversing the first and second iterators through at least a portion of a fact index;

receiving the first candidate fact from the first iterator, wherein the first candidate fact includes at least a first term occurrence;

receiving the second candidate fact from the second iterator, wherein the second candidate fact includes at least a second term occurrence;

performing at least one fact-level operation on at least the first and second candidate facts; and

selecting search results for the input query, based at least in part on performing the fact-level operation on the candidate facts.

13. The storage medium of claim 12, further comprising instructions for applying the term occurrence-level constraints to the first and second term-level occurrences, further comprising instructions for selecting search results for the input query, based at least in part on applying the term occurrence-level constraints to the term occurrences.

14. The storage medium of claim 12, further comprising instructions for instantiating at least a third iterator to perform the at least one fact-level operation on at least the first and second candidate facts, wherein the third iterator is for communicating with the first and second iterators.

15. The storage medium of claim 14, wherein the instructions for instantiating at least a third iterator include instructions for instantiating an iterator for performing a Boolean operation on the first and second candidate facts.

16. The storage medium of claim 14, wherein the instructions for instantiating at least a third iterator include instructions for instantiating an iterator for performing a union or intersection operation on the first and second candidate facts.

17. The storage medium of claim 14, further comprising instructions for instantiating at least a fourth iterator to apply the term occurrence-level constraints to the first and second term occurrences, wherein the fourth iterator is for communicating with the third iterator.

18. At least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

receiving at least one natural language input query;

defining a plurality of term occurrence-level constraints applicable to the input query;

decomposing the input query into a plurality of sub-queries, wherein a first sub-query relates to a first fact requested in the input query, and wherein at least a second sub-query relates to a second fact requested in the input query;

instantiating a first iterator to identify at least a first candidate fact that is responsive to the input query and that relates to the first fact;

instantiating at least a second iterator to identify at least a first candidate fact that is responsive to the input query and that relates to the second fact;

traversing the first and second iterators through at least a portion of a fact index;

receiving the first candidate fact from the first iterator, wherein the first candidate fact includes at least a first term occurrence;

receiving the second candidate fact from the second iterator, wherein the second candidate fact includes at least a second term occurrence;

applying the term occurrence-level constraints to the first and second term occurrences; and

selecting search results for the input query, based at least in part on applying the term occurrence-level constraints to the term occurrences.

19. The storage medium of claim 18, wherein the instructions for applying the term occurrence-level constraints include instructions for analyzing respective skolem identifiers associated with the first and second term occurrences, and further comprising instructions for performing at least one fact-level operation on at least the first and second candidate facts and for selecting search results for the input query, based at least in part on performing the fact-level operation on the candidate facts.

20. The storage medium of claim 18, wherein the instructions for applying the term occurrence-level constraints include instructions for applying a semantic constraint to the first and second term occurrences, and further comprising instructions for associating respective representations of contexts with the candidate facts, wherein the representations of context as associated with the candidate facts indicate whether the candidate fact is true within that the contexts.