METHOD FOR DYNAMIC UPDATING OF AN INDEX, AND A SEARCH ENGINE IMPLEMENTING THE SAME

• US 20090164437A1
• Filed: 12/18/2008
• Published: 06/25/2009
• Est. Priority Date: 12/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Corporation
• Original Assignee: Microsoft International Holdings BV (Microsoft Corporation)
• Inventors: TORBJORNSEN, Oystein
• Granted Patent: US 8,949,247 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

In a method for a dynamic updating of an index of a search engine, wherein the index is an inverted index comprising a dictionary, a posting file with a posting list for each keyword of the index and a database log, the documents are inserted in the index in small batches called update generations, a list of all occurrences of keywords in the documents of each update generation is generated, the occurrence list is inserted in the database log, and for each keyword entered in the database a reference to a previous entry of the same keyword is created. This previous entry has a reference stored in the mass storage device as the last added entry of all recently keywords.—A search engine performing the method may be implemented on one or more servers with a mass storage device, and comprises a core search engine with a search subsystem and an indexing subsystem for creating a keyword index stored on the mass storage device and with the index realized as a dynamically updateable index.

Claims

1. A method for dynamic updating of an index of a search engine, wherein the search engine is implemented on one or more servers comprising a mass storage device and wherein the index is an inverted index comprising a dictionary, a posting file with posting lists for each keyword of the index and a database log, and wherein the method is characterized by steps for inserting documents in the index in small batches, each batch constituting an update generation of the index;

generating a list of all occurrences of keywords in the documents of each update generation;

inserting the occurrence list in the database log; and

creating for each keyword entered in the database log a reference to a previous entry of the same keyword in the database log, said previous entry having a reference stored in the mass storage device as the last added entry of all recently added keywords.

2. A method according to claim 1,

characterized by grouping all updates of the database log together at specified intervals moving the grouped updates to the posting file;

and

storing each keyword respectively in an occurrence list in the form of occurrences of the keyword older than a determined update generation and in a delta list in the form of a set of smaller updates more recent than the same update generation, such that the dictionary contains one entry for each keyword in the posting file and a reference to the occurrence list and the delta list.

3. A method according to claim 2,

characterized by storing the occurrence list and the delta list in the posting file.

4. A method according to claim 2,

characterized by implementing the dictionary as a B-tree.

5. A method according to claim 4,

characterized by storing the occurrence list and the delta list below a specific size in the B-tree.

6. A method according to claim 2,

characterized by forcing the database log to the mass storage device at the end of each update generation, whereby the index can be recovered in case of an abrupt failure or stoppage of the search engine by replaying the database log and recreating the keyword entries in the main memory up to the last update in the database log for each keyword.

7. A method according to claim 2,

characterized by organizing the posting file as a circular file such that unused space are reclaimed at the tail thereof and existing keyword entries moved to the head thereof.

8. A method according to claim 7,

characterized by adding a keyword entry to the end of the posting file if no space to move an existing entry or to add a new keyword entry is present.

9. A method according to claim 2,

characterized by processing a search query by performing a keyword lookup by retrieving the dictionary entry, reading the main occurrence list and the delta list from the posting file by means of the dictionary entry, and merging the occurrence list and the delta list together with any entries of the keyword in the database log into a single occurrence list such that this single occurrence list can be used for further processing of a search query.

10. A method according to claim 9,

characterized by performing the merging of the occurrence list and the delta list without including any update generation more recent than a specified generation, such that the search query can be processed for occurrences of the keyword existing at the end of the specific generation.

11. A search engine (100) implementing a method for dynamic updating of an index of a search engine, wherein the search engine is implemented on one or more servers comprising a mass storage device, wherein the search engine comprises core search engine (101) with search sub-system (101b) and an indexing sub-system (101a) for creating a keyword index stored on a mass storage device, and wherein the index is an inverted index comprising a dictionary, a posting file with posting lists for each keyword of the index and a database log,

characterized in that the index is a dynamically up-dateable index.