SUPPORTING SUB-DOCUMENT UPDATES AND QUERIES IN AN INVERTED INDEX

• US 20090228528A1
• Filed: 03/06/2008
• Published: 09/10/2009
• Est. Priority Date: 03/06/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ercegovac, Vuk, Josifovski, Vanja, Li, Ning, Shekita, Eugene J., Mediano, Mauricio
• Application Number:
  US12/043,858
• Publication Number:
  US 20090228528A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

A system, method, and computer program product for updating a partitioned index of a dataset. A document is indexed by separating it into indexable sections, such that different ones of the indexable sections may be contained in different partitions of the partitioned index. The partitioned index is updated using an updated version of the document by updating only those sections of the index corresponding to sections of the document that have been updated in the updated version.

Claims

1. A method of updating a partitioned index of a dataset comprising:

indexing a document by separating a document into sections, wherein at least one of said sections is contained in at least one partition of said partitioned index; and

updating said partitioned index using an updated version of said document by updating only those sections of said index corresponding to sections of said document that have been updated in said updated version of said document.

2. The method of claim 1 wherein each section is fully contained in only one partition and wherein different ones of said sections are contained in different partitions of said partitioned index.

3. The method of claim 1 wherein said index is an inverted index.

4. The method of claim 1 further comprising generating a posting list comprising, a document identifier, and a section identifier for each occurrence of a term in said dataset.

5. The method of claim 4 wherein said generating further comprises generating a payload storing additional information about each occurrence of said term.

6. The method of claim 4 further comprising indexing said posting lists in a tree representation.

7. The method of claim 6 further comprising accessing one of said posting lists for one of said terms using an index cursor.

8. The method of claim 1, wherein said document includes metadata and content, and wherein said indexing further comprises indexing said metadata in a first section and indexing said content in a second section.

9. A method of searching a dataset having a plurality of documents comprising:

indexing said dataset using a partitioned inverted index, each document having a plurality of document sections, each document section indexed by at most one partition; and

searching said index by searching across said document sections.

10. The method of claim 9, wherein said searching comprises receiving a query and evaluating said query across partitions.

11. The method of claim 10 further comprising minimizing the number of index cursor moves using information regarding said sections and partitions.

12. The method of claim 9 further comprising updating said partitioned inverted index in response to an updated version of said document by updating those sections of said index corresponding to sections of said document that have been updated in said updated version, and not updating those sections that have not been updated in said updated version.

13. A partitioned inverted index comprising:

an ingestion thread receiving a work item and placing it in a queue;

a sort-write thread for dequeuing said work item, sorting said work item to create a new index partition and writing said new index partition to disk;

a merge manager thread for determining when to merge partitions;

a merge thread for merging partitions in response to an instruction from said merge manager; and

a state manager thread for receiving a notification from said sort-write thread of said new index partition and for updating an index state, wherein said sort-write thread, said merge manager thread, said merge thread, and said state manager threads operate in parallel.

14. The partitioned inverted index of claim 13 wherein said work item is an updated document.

15. The partitioned inverted index of claim 13 wherein said work item is an index section, said index section being created by separating a document into indexable sections, such that different ones of said indexable sections are contained in different partitions of said partitioned index.

16. A computer program product comprising a computer usable medium having a computer readable program, wherein said computer readable program when executed on a computer causes said computer to:

index a document by separating a document into sections, wherein at least one of said sections is contained in at least one partition of a partitioned index; and

update said partitioned index using an updated version of said document by updating only those sections of said index corresponding to sections of said document that have been updated in said updated version of said document.

17. The computer program product of claim 16 wherein said computer readable program further causes said computer to minimize the number of index cursor moves.

18. The computer program product of claim 17 wherein said computer readable program further causes said computer to minimize the number of index cursor moves by determining which cursor move is the best next cursor move.

19. The computer program product of claim 18 wherein said computer readable program further causes said computer to minimize the number of index cursor moves by determining how far to move said cursor.

20. The computer program product of claim 16 wherein said computer readable program further causes said computer to search said index by searching across said sections.