EFFICIENT MULTIFACETED SEARCH IN INFORMATION RETRIEVAL SYSTEMS

• US 20080133473A1
• Filed: 11/30/2006
• Published: 06/05/2008
• Est. Priority Date: 11/30/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McPherson, John Ai, Li, Ning, Neumann, Andreas, Ofek-Koifman, Shila, Lempel, Ronny, Shekita, Eugene J., Broder, Andrei Z., Fontoura, Felipe Marcus, Eiron, Nadav, Qi, Runping
• Granted Patent: US 7,496,568 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 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. Constructing the inverted index includes generating a full path token and an associated full path token posting list. 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, wherein said constructing said inverted index includes;

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 Dewey labeling scheme that uniquely labels each sibling node of said tree structure;

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, wherein said plurality of constraints includes one or more facet constraints and one or more free-text constraints; and

executing said query by said JR 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,

wherein said identifying said multiple posting lists includes;

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.

2-20. -20. (canceled)