Efficient multifaceted search in information retrieval systems

• US 8,032,532 B2
• Filed: 05/21/2008
• Issued: 10/04/2011
• Est. Priority Date: 11/30/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Li, Ning, Broder, Andrei Z., Fontoura, Felipe Marcus, Eiron, Nadav, McPherson, John Ai Jr., Qi, Runping, Neumann, Andreas, Ofek-Koifman, Shila, Lempel, Ronny, Shekita, Eugene J.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Uddin; Mohammed R
• Application Number:
  US12/124,272
• Publication Number:
  US 20080222117A1
• Time in Patent Office: 1,231 Days
• Field of Search: 707/742, 707/999.003
• US Class Current: 707/742
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method and system for querying multifaceted information. An inverted index is constructed to include unique indexed tokens associated with posting lists of one or more documents. An indexed token is either a facet token included in a document as an annotation or a path prefix of the facet token. The annotation indicates a path within a tree structure representing a facet that includes the document. The tree structure includes nodes representing categories of documents. A query is received that includes constraints on documents. The constraints are associated with indexed tokens and corresponding posting lists. An execution of the query includes identifying the corresponding posting lists by utilizing the constraints and the inverted index and intersecting the posting lists to obtain a query result.

Claims

1. A computer-implemented method of querying multifaceted information in an information retrieval system, comprising:

constructing, by said information retrieval (IR) system, an inverted index having a plurality of unique indexed tokens associated with a plurality of posting lists in a one-to-one correspondence, each posting list including one or more documents of a plurality of documents, wherein an indexed token of said plurality of unique indexed tokens is one of a facet token included as an annotation in a document of said plurality of documents and a path prefix of said facet token, wherein said annotation indicates a path within a tree structure representing a facet that includes said document, said tree structure including a plurality of nodes representing a category and one or more sub-categories that categorize said document;

receiving, by said IR system, a query that includes a plurality of constraints on said plurality of documents, said plurality of constraints being associated with multiple indexed tokens of said plurality of unique indexed tokens and multiple posting lists corresponding to said multiple indexed tokens; and

executing said query by said IR system, said executing including;

identifying said multiple posting lists via a utilization of said plurality of constraints and said inverted index, and

intersecting said multiple posting lists to obtain a result of said query.

2. The method of claim 1, wherein said plurality of constraints includes one or more facet constraints and one or more free-text constraints, and wherein said identifying said multiple posting lists comprises:

identifying, via said inverted index, a first set of one or more indexed tokens associated with said one or more facet constraints in a one-to-one correspondence and a second set of one or more indexed tokens associated with said one or more free-text constraints in a one-to-one correspondence, said first set and said second set of one or more indexed tokens included in said plurality of unique indexed tokens; and

identifying, via said inverted index, a first group of one or more posting lists and a second group of one or more posting lists, said one or more posting lists of said first group associated with said one or more indexed tokens of said first set in a one-to-one correspondence and said one or more posting lists of said second group associated with said one or more indexed tokens of said second set in a one-to-one correspondence.

3. The method of claim 1, wherein said constructing said inverted index comprises:

generating a full path token and a full path token posting list associated therewith by said inverted index, said full path token posting list including a plurality of identifiers representing said plurality of documents, wherein an identifier of said plurality of identifiers represents said document and includes a payload value, said payload value identifying a full path of said document in said tree structure, and said payload value including a set of full path indicators provided by a scheme that uniquely labels each sibling node of said tree structure.

4. The method of claim 3, further comprising:

building a hierarchy of a plurality of counters, each counter being associated with a node of said plurality of nodes of said tree structure, wherein a counter of said plurality of counters is indexed by said set of full path indicators; and

updating a value stored in said counter, said value indicating a count of one or more documents of said plurality of documents, said one or more documents categorized by a sub-category of a category or sub-category indicated by a constraint of said plurality of constraints.

5. The method of claim 3, wherein said scheme is a Dewey labeling scheme.

6. The method of claim 1, further comprising:

receiving, by said IR system, an arithmetic expression included in said query, said arithmetic expression associated with at least one numeric field included in one or more documents of said plurality of documents; and

computing an evaluation of said arithmetic expression, said computing performed per sub-category of a category indicated by a constraint of said plurality of constraints.

7. The method of claim 6, wherein said arithmetic expression includes at least one of an aggregate function and a basic formula,

wherein said aggregate function includes at least one of a sum, a product, a maxima, a minima, and an average, and

wherein said basic formula includes any combination of one or more numeric fields, one or more numeric constants, one or more arithmetic operators, and parentheses that indicate a parenthetical expression.

8. The method of claim 1, wherein said constructing said inverted index comprises:

designating, for each document of said plurality of documents, a set of one or more indexed tokens of said plurality of unique indexed tokens as a set of one or more exact tokens, each exact token indicating a final sub-category categorizing one or more documents of said plurality of documents, wherein each document categorized by said final sub-category is not categorized by a child sub-category of said final sub-category; and

identifying, via said query utilizing said set of one or more exact tokens, said document as residing in said final sub-category, but not in any child sub-category of said final sub-category.

9. A computer system comprising:

a central processing unit (CPU);

a memory coupled to said CPU;

a computer-readable, tangible storage device coupled to said CPU, said storage device containing instructions that are carried out by said CPU via said memory to implement a method of querying multifaceted information, said method comprising;

constructing an inverted index having a plurality of unique indexed tokens associated with a plurality of posting lists in a one-to-one correspondence, each posting list including one or more documents of a plurality of documents, wherein an indexed token of said plurality of unique indexed tokens is one of a facet token included as an annotation in a document of said plurality of documents and a path prefix of said facet token, wherein said annotation indicates a path within a tree structure representing a facet that includes said document, said tree structure including a plurality of nodes representing a category and one or more sub-categories that categorize said document;

receiving a query that includes a plurality of constraints on said plurality of documents, said plurality of constraints being associated with multiple indexed tokens of said plurality of unique indexed tokens and multiple posting lists corresponding to said multiple indexed tokens; and

executing said query by

identifying said multiple posting lists via a utilization of said plurality of constraints and said inverted index, and

intersecting said multiple posting lists to obtain a result of said query.

10. The system of claim 9, wherein said plurality of constraints includes one or more facet constraints and one or more free-text constraints, and wherein said identifying said multiple posting lists comprises:

identifying, via said inverted index, a first set of one or more indexed tokens associated with said one or more facet constraints in a one-to-one correspondence and a second set of one or more indexed tokens associated with said one or more free-text constraints in a one-to-one correspondence, said first set and said second set of one or more indexed tokens included in said plurality of unique indexed tokens; and

identifying, via said inverted index, a first group of one or more posting lists and a second group of one or more posting lists, said one or more posting lists of said first group associated with said one or more indexed tokens of said first set in a one-to-one correspondence and said one or more posting lists of said second group associated with said one or more indexed tokens of said second set in a one-to-one correspondence.

11. The system of claim 9, wherein said constructing said inverted index comprises:

generating a full path token and a full path token posting list associated therewith by said inverted index, said full path token posting list including a plurality of identifiers representing said plurality of documents, wherein an identifier of said plurality of identifiers represents said document and includes a payload value, said payload value identifying a full path of said document in said tree structure, and said payload value including a set of full path indicators provided by a scheme that uniquely labels each sibling node of said tree structure.

12. The system of claim 11, further comprising:

building a hierarchy of a plurality of counters, each counter being associated with a node of said plurality of nodes of said tree structure, wherein a counter of said plurality of counters is indexed by said set of full path indicators; and

updating a value stored in said counter, said value indicating a count of one or more documents of said plurality of documents, said one or more documents categorized by a sub-category of a category or sub-category indicated by a constraint of said plurality of constraints.

13. The system of claim 11, wherein said scheme is a Dewey labeling scheme.

14. The system of claim 9, further comprising:

receiving, by said IR system, an arithmetic expression included in said query, said arithmetic expression associated with at least one numeric field included in one or more documents of said plurality of documents; and

computing an evaluation of said arithmetic expression, said computing performed per sub-category of a category indicated by a constraint of said plurality of constraints.

15. The system of claim 14, wherein said arithmetic expression includes at least one of an aggregate function and a basic formula,

wherein said aggregate function includes at least one of a sum, a product, a maxima, a minima, and an average, and

wherein said basic formula includes any combination of one or more numeric fields, one or more numeric constants, one or more arithmetic operators, and one or more sets of parentheses that indicate parenthetical expressions.

16. The system of claim 9, wherein said constructing said inverted index comprises:

designating, for each document of said plurality of documents, a set of one or more indexed tokens of said plurality of unique indexed tokens as a set of one or more exact tokens, each exact token indicating a final sub-category categorizing one or more documents of said plurality of documents, wherein each document categorized by said final sub-category is not categorized by a child sub-category of said final sub-category; and

identifying, via said query utilizing said set of one or more exact tokens, said document as residing in said final sub-category, but not in any child sub-category of said final sub-category.

17. A computer program product comprising a computer-readable, tangible storage device having a computer-readable program code stored therein, said computer-readable program code containing instructions that are carried out by a processor of a computer system to implement a method of querying multifaceted information in an information retrieval system, said method comprising:

constructing, by said information retrieval (IR) system, an inverted index having a plurality of unique indexed tokens associated with a plurality of posting lists in a one-to-one correspondence, each posting list including one or more documents of a plurality of documents, wherein an indexed token of said plurality of unique indexed tokens is one of a facet token included as an annotation in a document of said plurality of documents and a path prefix of said facet token, wherein said annotation indicates a path within a tree structure representing a facet that includes said document, said tree structure including a plurality of nodes representing a category and one or more sub-categories that categorize said document;

receiving, by said IR system, a query that includes a plurality of constraints on said plurality of documents, said plurality of constraints being associated with multiple indexed tokens of said plurality of unique indexed tokens and multiple posting lists corresponding to said multiple indexed tokens; and

executing said query by said IR system by;

identifying said multiple posting lists via a utilization of said plurality of constraints and said inverted index, and

intersecting said multiple posting lists to obtain a result of said query.

18. The program product of claim 17, wherein said plurality of constraints includes one or more facet constraints and one or more free-text constraints, and wherein said identifying said multiple posting lists comprises:

identifying, via said inverted index, a first set of one or more indexed tokens associated with said one or more facet constraints in a one-to-one correspondence and a second set of one or more indexed tokens associated with said one or more free-text constraints in a one-to-one correspondence, said first set and said second set of one or more indexed tokens included in said plurality of unique indexed tokens; and

identifying, via said inverted index, a first group of one or more posting lists and a second group of one or more posting lists, said one or more posting lists of said first group associated with said one or more indexed tokens of said first set in a one-to-one correspondence and said one or more posting lists of said second group associated with said one or more indexed tokens of said second set in a one-to-one correspondence.

19. The program product of claim 17, wherein said constructing said inverted index comprises:

generating a full path token and a full path token posting list associated therewith by said inverted index, said full path token posting list including a plurality of identifiers representing said plurality of documents, wherein an identifier of said plurality of identifiers represents said document and includes a payload value, said payload value identifying a full path of said document in said tree structure, and said payload value including a set of full path indicators provided by a scheme that uniquely labels each sibling node of said tree structure.

20. The program product of claim 19, wherein said method further comprises:

building a hierarchy of a plurality of counters, each counter being associated with a node of said plurality of nodes of said tree structure, wherein a counter of said plurality of counters is indexed by said set of full path indicators; and

updating a value stored in said counter, said value indicating a count of one or more documents of said plurality of documents, said one or more documents categorized by a sub-category of a category or sub-category indicated by a constraint of said plurality of constraints.