Real-time search of vertically partitioned, inverted indexes

• US 9,171,062 B2
• Filed: 09/13/2012
• Issued: 10/27/2015
• Est. Priority Date: 07/13/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Busch, Michael, Desai, Rajesh M., Foyle, Robert A., Jayapandian, Magesh
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US13/614,970
• Publication Number:
  US 20130018891A1
• Time in Patent Office: 1,139 Days
• Field of Search: 707/1, 707/10, 707/100, 707/102, 707/771, 707/776, 707/779, 707/759, 707/763, 707/736, 707/741, 707/742, 707/704
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Provided are techniques for processing a query. A query including constraints for at least two vertically partitioned, inverted indexes is received. The constraints in the query are separated based on the vertically partitioned, inverted indexes. A document identifier iterator is obtained for each of the constraints, wherein each document identifier iterator is associated with a posting list, and wherein each posting list is ordered by document identifier order. A run-time join of the posting lists is performed to obtain a final result set.

Claims

1. A method for processing a query, comprising:

receiving, using a processor of a computer, the query that includes a document constraint and an annotation constraint;

parsing, using the processor of the computer, the query to separate the document constraint from the annotation constraint and to create a query parse tree with a primary query processor at a lowest level of the query parse tree and with an auxiliary query processor at the lowest level of the query parse tree;

processing, using the processor of the computer, the document constraint with the primary query processor to generate a first posting list that is ordered by document identifier;

processing, using the processor of the computer, the annotation constraint with the auxiliary query processor to generate a second posting list that is ordered by annotation identifier and that includes the document identifier associated with each annotation that is identified by the annotation identifier and that is re-ordered by the document identifier;

evaluating, using the processor of the computer, the query parse tree with the primary query processor and with the auxiliary query processor by iterating through the first posting list and the second posting list; and

performing, using the processor of the computer, a run-time join of the first posting list and the second posting list to obtain a final result set that combines documents and annotations that have a same document identifier with a union operation.

2. The method of claim 1, further comprising:

mapping the document constraint to the primary query processor and mapping the annotation constraint to the auxiliary query processor.

3. The method of claim 1, further comprising:

storing document identifiers in the primary index; and

at index construction time, storing the document identifiers in the auxiliary index, wherein the document identifiers comprise foreign keys.

4. The method of claim 1, further comprising:

returning the final result set in response to the received query that includes the document constraint and the annotation constraint.

5. The method of claim 1, wherein a text document is categorized in a category, and wherein the category is stored in the auxiliary index for search and analysis in real-time.

6. The method of claim 1, further comprising:

creating vertically partitioned, inverted indexes, with each of the vertically partitioned, inverted indexes associated with one or more constraints.