UPDATING AN INVERTED INDEX

• US 20080307013A1
• Filed: 06/08/2007
• Published: 12/11/2008
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Loofbourrow, Wayne, Hoernkvist, John Martin, Li, Yun-chih S., Koebler, Eric Richard
• Granted Patent: US 7,917,516 B2
• Time in Patent Office: Days
• US Class Current: 707/203
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

Systems and methods for processing an index are described. To insure that the most updated index is available without having to update the index after every change (which can consume enormous resources), a specially marked postings list is generated for a changed item. During retrieval, the specially marked postings list supplements the existing content of an inverted index referencing the changed item. In this manner, the retrieval result for items containing the term under which the changed item was originally indexed is updated in accordance with the specially marked postings list to insure the most accurate retrieval result.

Claims

1. A machine implemented method of updating an inverted index, the method comprising:

determining that a change to an item has occurred;

supplementing an existing content of an inverted index to reflect the change to the item; and

retrieving the item in accordance with the supplemented existing content of the inverted index.

2. The method of claim 1, wherein the existing content contains a list of items containing a term, and supplementing the existing content comprises adding a delta list of items containing the term to an existing list of items containing the term.

3. The method of claim 2, wherein adding the delta list of items containing the term comprises:

generating a posting of the change to the item; and

applying the posting of the change to the item to the list of items containing the term prior to retrieving the item.

4. The method of claim 3, wherein the change to the item comprises a term deleted from the item, and generating the posting of the change to the item comprises posting data representing:

the item that changed; and

the term deleted from the item.

5. The method of claim 3, wherein the change to the item comprises a term added to the item, and generating the posting of the change to the item comprises posting data representing:

the item that changed; and

the term added to the item.