Updating an inverted index

• US 8,122,029 B2
• Filed: 03/28/2011
• Issued: 02/21/2012
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Loofbourrow, Wayne, Hornkvist, John Martin, Koebler, Eric Richard, Li, Yun-chih S.
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US13/073,898
• Publication Number:
  US 20110289093A1
• Time in Patent Office: 330 Days
• Field of Search: 707/705, 707/741, 707/742
• US Class Current: 707/742
• 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, the method comprising:

receiving a notification of a changed item and in response to receiving the notification, updating a list of postings to reflect the changed item, wherein a posting of a change to the item is generated in the list of postings;

in response to receiving a query for an item indexed in an inverted index, generating a query result of the query from the inverted index, wherein an existing content for the item in the inverted index does not accurately represent the item;

interrogating the list of postings which is separate from the inverted index to determine if the change to the item indexed in the inverted index has occurred, the list of postings to represent changes having occurred to items indexed in the inverted index without having to immediately update the inverted index after the changes;

if the change has occurred, applying the list of postings to the query result to reflect the change to the item, the list of postings supplementing the inverted index for the query result; and

generating, in a data processing system, a query result in accordance with the existing content of the inverted index supplemented with the posting of the change to the item, wherein the change to the item is applied prior to the retrieval.

2. The method of claim 1, wherein the existing content contains a term under which the item was originally indexed, and wherein the posting of the change includes the term under which the item was originally indexed and wherein the term is a word and the item is a file.

3. The method of claim 2, wherein the posting of the change includes a new term under which the item should now be indexed.

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.

6. A machine implemented method, the method comprising:

receiving a notification of a changed item;

generating, in response to the notification, a posting representing a change of an item, the posting being separate from the inverted index which indexed the item prior to the change, wherein an existing content for the item in the inverted index does not accurately represent the item with the change, the posting to allow accurate retrieval for the item without updating immediately the inverted index with the change;

storing the posting in a delta list associated with items no longer accurately represented in the inverted index;

in response to receiving a query, generating a query result against the inverted index including the existing content for the item;

interrogating the delta list to determine if an update of the inverted index is available;

applying the posting to the generated query result for a query result reflecting the change of the item based on the interrogation which determines the update of the inverted index is available; and

presenting the query result in accordance with the change of the item, wherein the query result is presented on a display device of the machine.

7. The method of claim 6, wherein the inverted index includes a two-level table that separates more frequently occurring terms from less frequently occurring terms.

8. The method of claim 7, wherein the inverted index includes a live index for a most current index.

9. The method of claim 6, wherein an old term of the item is changed to a new term, wherein the posting indicates the item is indexed under the old term in the inverted index.

10. The method of claim 9, wherein the posting indicates the item should be indexed under the new term.

11. A non-transitory machine-readable storage medium having instructions, when executed by a machine, cause the machine to perform a method comprising:

receiving a notification of a changed item and in response to the receiving the notification, updating a list of postings to reflect the changed item, wherein a posting of a change to the item is generated in the list of postings;

in response to receiving a query for an item indexed in an inverted index, generating a query result of the query from the inverted index, wherein an existing content for the item in the inverted index does not accurately represent the item;

interrogating the list of postings to determine if the change to the item indexed in an inverted index has occurred, the list of postings to represent changes having occurred to items indexed in the inverted index without having to immediately update the inverted index after the changes;

if the change has occurred, applying the list of postings to the query result to reflect the change to the item, the list of postings supplementing the inverted index for the query result; and

generating a query result in accordance with the existing content of the inverted index supplemented with the posting of the change to the item, wherein the change to the item is applied prior to the retrieval.

12. The storage medium of claim 11, wherein the existing content contains a term under which the item was originally indexed, and wherein the posting of the change includes the term under which the item was originally indexed and wherein the term is a word and the item is a file.

13. The storage medium of claim 12, wherein the posting of the change includes a new term under which the should now be indexed.

14. The storage medium of claim 13, 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.

15. The storage medium of claim 13, 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.

16. A non-transitory machine-readable storage medium having instructions, when executed by a machine, cause the machine to perform a method comprising:

receiving a notification of a changed item;

generating, in response to the notification, a posting representing a change of an item, the posting being separate from an inverted index which indexed the item prior to the change, wherein an existing content for the item in the inverted index does not accurately represent the item with the change, the posting in a storage device to allow accurate retrieval for the item without updating immediately the inverted index with the change;

storing the posting in a delta list associated with items no longer accurately represented in the inverted list;

in response to receiving a query, generating a query result against the inverted index including the existing content for the item;

interrogating the delta list to determine if an update of the inverted index is available;

applying the posting to the generated query result for a query result reflecting the change of the item based on the interrogation which determines the update of the inverted index is available; and

presenting the query result in accordance with the change of the item.

17. The storage medium of claim 16, wherein the inverted index includes a two-level table that separates more frequently occurring terms from less frequently occurring terms.

18. The storage medium of claim 17, wherein the inverted index includes a live index for a most current index.

19. A data processing system, comprising:

a memory storing executable instructions including an indexing software and a retrieval software;

a storage device storing data files indexed by an inverted index; and

a processor coupled to the memory and the storage device, the processor being configured to execute the executable instructions from the memory to;

receive a notification of a changed file and in response to the notification, update a list of postings to reflect the changed file, wherein a posting of a change to the file is generated in the list of postings;

in response to receiving a query for a file indexed in the inverted index, generate a query result of the query from the inverted index, wherein an existing content for the file in the inverted index does not accurately represent the file,

interrogate the list of postings which is separate from the inverted index to determine if a change to the file indexed in the inverted index has occurred, the list of postings to represent changes having occurred to the data files indexed in the inverted index without having to update immediately the inverted index after the changes,

if the change has occurred, apply the list of postings to the query result to reflect the change to the file, the list of postings supplementing the inverted index for the query result; and

generate a query result in accordance with the existing content of the inverted index supplemented with the posting of the change to the file, wherein the change to the file is applied prior to the retrieval.

20. The data processing system of claim 19, wherein the existing content contains a term under which the file was originally indexed, and wherein the posting of the change includes the term under which the file was originally indexed and a new term under which the item should now be indexed.

21. The data processing system of claim 20, wherein the processor is further configured to execute the executables to:

store the list of postings.