Object-oriented twig query evaluation

• US 7,895,232 B2
• Filed: 12/25/2007
• Issued: 02/22/2011
• Est. Priority Date: 12/25/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sheinwald, Dafna, Yogev, Sivan, Sznajder, Benjamin
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US11/964,017
• Publication Number:
  US 20090164424A1
• Time in Patent Office: 1,155 Days
• Field of Search: 707/718, 707/775
• US Class Current: 707/775
• CPC Class Codes: G06F 16/8373 Query execution

Abstract

A computer-implemented method for searching a corpus of documents includes defining a query as a twig including a root annotation operator having an associated tag specifying a span and having an associated expression indicative of one or more terms whose occurrence within the span will satisfy the query. An object is recursively selected from a group of objects that consists of the tag and the expression, and is used in advancing through the corpus until a candidate document is found that contains the tag and satisfies the expression. The candidate document is evaluated to determine whether the one or more terms indicated by the expression occur within the span in the candidate document so as to satisfy the annotation operator.

Claims

1. A computer-implemented method for searching a corpus of documents, the method comprising:

defining a query as a twig comprising a root annotation operator having an associated tag specifying a span and having an associated expression indicative of one or more terms whose occurrence within the span will satisfy the query;

recursively selecting an object from a group of objects that consists of the tag and the expression, and advancing through the corpus using the selected object until a candidate document is found that contains the tag and satisfies the expression;

evaluating the candidate document to determine whether the one or more terms indicated by the expression occur within the span in the candidate document so as to satisfy the annotation operator; and

retrieving the candidate document from the corpus upon determining that the annotation operator is satisfied.

2. The method according to claim 1, wherein the one or more terms comprise at least two terms, and wherein the expression comprises an intermediate operator that defines a relation between the terms.

3. The method according to claim 2, wherein the tag associated with the root annotation operator is a first tag, which specifies a first span, and wherein the intermediate operator comprises a intermediate annotation operator with which a second tag, specifying a second span, is associated.

4. The method according to claim 3, wherein evaluating the candidate document comprises determining the root annotation operator to be satisfied when the intermediate annotation operator is satisfied with respect to the second span, while the second span overlaps the first span but is not nested within the first span.

5. The method according to claim 3, wherein evaluating the candidate document comprises finding multiple occurrences of the second span that overlap the first span at least partially and in which the first annotation operator is satisfied.

6. The method according to claim 1, wherein advancing through the corpus comprises creating an index of tags and words occurring in the documents in the corpus, and using the index to find the candidate documents.

7. The method according to claim 6, wherein creating the index comprises annotating the documents with the tags so as to define respective spans of the tags, wherein the respective spans comprise at least first and second spans having an overlap therebetween, while neither of the first and second spans is nested within the other of the first and second spans, and wherein evaluating the candidate document comprises determining that the annotation operator is satisfied by overlap of the first and second spans.

8. Apparatus for searching a corpus of documents, the apparatus comprising:

an interface, for receiving a query that is defined as a twig comprising a root annotation operator having an associated tag specifying a span and having an associated expression indicative of one or more terms whose occurrence within the span will satisfy the query; and

a processor, which is configured to process the query by recursively selecting an object from a group of objects that consists of the tag and the expression, and advancing through the corpus using the selected object until a candidate document is found that contains the tag and satisfies the expression, and evaluating the candidate document to determine whether the one or more terms indicated by the expression occur within the span in the candidate document so as to satisfy the annotation operator, and to retrieve the candidate document from the corpus upon determining that the annotation operator is satisfied.

9. The apparatus according to claim 8, wherein the one or more terms comprise at least two terms, and wherein the expression comprises an intermediate operator that defines a relation between the terms.

10. The apparatus according to claim 9, wherein the tag associated with the root annotation operator is a first tag, which specifies a first span, and wherein the intermediate operator comprises a intermediate annotation operator with which a second tag, specifying a second span, is associated.

11. The apparatus according to claim 10, wherein the processor is configured to determine the root annotation operator to be satisfied when the intermediate annotation operator is satisfied with respect to the second span, while the second span overlaps the first span but is not nested within the first span.

12. The apparatus according to claim 10, wherein the processor is configured to find multiple occurrences of the second span that overlap the first span at least partially and in which the first annotation operator is satisfied.

13. The apparatus according to claim 8, wherein the processor is configured to use an index of tags and words occurring in the documents in the corpus in order to find the candidate documents, wherein the documents are annotated with the tags so as to define respective spans of the tags, wherein the respective spans comprise at least first and second spans having an overlap therebetween, while neither of the first and second spans is nested within the other of the first and second spans, and wherein the processor is configured to determine that the annotation operator is satisfied by overlap of the first and second spans.

14. A computer software product for searching a corpus of documents, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a query that is defined as a twig comprising a root annotation operator having an associated tag specifying a span and having an associated expression indicative of one or more terms whose occurrence within the span will satisfy the query, and to process the query by recursively selecting an object from a group of objects that consists of the tag and the expression, and advancing through the corpus using the selected object until a candidate document is found that contains the tag and satisfies the expression, and evaluating the candidate document to determine whether the one or more terms indicated by the expression occur within the span in the candidate document so as to satisfy the annotation operator, and to retrieve the candidate document from the corpus upon determining that the annotation operator is satisfied.

15. The product according to claim 14, wherein the one or more terms comprise at least two terms, and wherein the expression comprises an intermediate operator that defines a relation between the terms.

16. The product according to claim 15, wherein the tag associated with the root annotation operator is a first tag, which specifies a first span, and wherein the intermediate operator comprises a intermediate annotation operator with which a second tag, specifying a second span, is associated.

17. The product according to claim 16, wherein the instructions cause the computer to determine the root annotation operator to be satisfied when the intermediate annotation operator is satisfied with respect to the second span, while the second span overlaps the first span but is not nested within the first span.

18. The product according to claim 16, wherein the instructions cause the computer to find multiple occurrences of the second span that overlap the first span at least partially and in which the first annotation operator is satisfied.

19. The product according to claim 14, wherein the instructions cause the computer to use an index of tags and words occurring in the documents in the corpus in order to find the candidate documents.

20. The product according to claim 19, wherein the documents are annotated with the tags so as to define respective spans of the tags, wherein the respective spans comprise at least first and second spans having an overlap therebetween, while neither of the first and second spans is nested within the other of the first and second spans, and wherein the instructions cause the computer to determine that the annotation operator is satisfied by overlap of the first and second spans.