Updating an inverted index
First Claim
Patent Images
1. A machine implemented method of updating an inverted index, 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 the 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 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
retrieving the item 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 and wherein the retrieved item is presented on a display device or the machine.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 Claims
-
1. A machine implemented method of updating an inverted index, 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 the 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 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 retrieving the item 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 and wherein the retrieved item is presented on a display device or the machine. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A machine implemented method of updating an inverted index, 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 the 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 retrieving the item in accordance with the query result reflecting the change of the item, wherein the retrieved item is presented on a display device of the machine. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A 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 the 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 retrieving the item 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. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A 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 retrieving the item in accordance with the query result reflecting the change of the item. - View Dependent Claims (17, 18)
-
-
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 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 retrieve the file 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. - View Dependent Claims (20, 21)
-
Specification