Method and system for incremental web crawling

• US 6,631,369 B1
• Filed: 06/30/1999
• Issued: 10/07/2003
• Est. Priority Date: 06/30/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meyerzon, Dmitriy, Terek, F. Soner, Shoroff, Srikanth, Sanu, Sankrant
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/345,040
• Time in Patent Office: 1,560 Days
• Field of Search: 707/5, 707/10, 707/200, 707/511, 707/4, 709/218-219, 709/203, 709/313, 709/229, 370/410
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A Web crawler creates an index of documents in a document store on a computer network. In an initial crawl, the crawler creates a first full index for the document store. The first full crawl is based on a set of predefined “seed” URLs and crawl restrictions, and involves recursively retrieving each folder/document directly or indirectly linked to the seed URLs. In the process of creating the first full index, the crawler creates a History Table containing a list of URLs for each folder and document found in the first full crawl. The History Table also includes a local commit time (LCT) for each document and a deleted documents count (DDC) and LCT or maximum LCT (MLCT) for each folder (this assumes that the store supports a folder hierarchy and the MLCT, LCT and DDC properties). Thereafter, in an incremental crawl, the crawler determines, for each folder, (1) whether the DDC for that folder has changed and (2) whether the MLCT is more recent than the corresponding value in the History Table. If the DDC has changed, the crawler obtains a full list of items (URLs) in that folder, and compares the list with the URLs in the History Table to identify the deleted documents. The deleted documents are then deleted from the History Table and index. If the MLCT is more recent, the crawler queries the document store for the URLs of linked documents having a LCT more recent than the MLCT in the History Table for the folder. The History Table and index are then updated accordingly to reflect the changes to the document store.

Claims

1. A computer-based method for performing an incremental crawl of a computer-readable document store in a manner that facilitates an efficient determination of whether and how the document store has been incremented from a prior state, comprising the following acts:

(a) determining from the document store whether a deleted documents count (DDC) for a first folder has changed from a value of the DDC as determined during a previous crawl of the document store;

(b) if the DDC has changed, identifying the documents that have been deleted from the first folder subsequent to the previous crawl; and

(c) if the DDC has not changed, determining whether a maximum local commit time (MLCT) associated with the first folder is later than a value of the MLCT as determined during the previous crawl, and, if it is later, identifying the documents that have been added to the folder or modified subsequent to the previous crawl.

2. A method as recited in claim 1, further comprising maintaining a History Table in which the DDC and MLCT are stored in association with address specifiers for folders in the document store.

3. A method as recited in claim 2, wherein the document store provides the DDC and MLCT as well as a local commit time (LCT) for documents in the document store, and wherein, in the History Table, an LCT is stored for documents, and max(LCT, MLCT) and a DDC are stored for folders.

4. A method as recited in claim 3, wherein the History Table also includes a flag to indicate which address specifiers correspond to folders having a DDC value stored in the History Table, and which address specifiers correspond to documents associated with a folder having a DDC value stored in the History Table.

5. A method as recited in claim 2, comprising, for each folder, storing in the History Table the LCT or MLCT of the folder, whichever is greater.

6. A method as recited in claim 1, wherein the method is executed by a server computer coupled by a network to the document store.

7. A method as recited in claim 1, further comprising providing an index of the documents in the document store, and updating the index to reflect any deleted, modified, or new documents that are identified during the incremental crawl of the document store.

8. A method as recited in claim 1, wherein, during the incremental crawl, documents or folders that are determined, through the DDC, MLCT and LCT, not to have been added or changed since the previous crawl are not fetched from the document store.

9. A method as recited in claim 1, wherein, during the incremental crawl, timestamps for documents that are determined, through the MLCT of the associated folder for each document, not to have been added or changed since the previous crawl are not fetched from the document store.

10. A method as recited in claim 1, wherein the method is employed in connection with a Web crawler application.

11. A method as recited in claim 1, wherein the method is employed in connection with a mail server application.

12. A method as recited in claim 1, wherein the method is employed in connection with a directory service.

13. A method as recited in claim 1, wherein the method is employed in connection with a system requiring indexing or one-way replication of a document store.

14. A computer-executable crawler application stored on a computer readable storage medium that is accessible to a server computer coupled by a network to a document store, wherein the document store contains a plurality of electronic documents and folders containing references to one or more documents, and wherein the document store provides local commit times (LCTs) and maximum LCTs (MLCTs) for documents and folders in the document store and deleted documents counts (DDCs) for folders in the document store, comprising:

(a) executable code for determining whether the DDC for a first folder has changed from a value of the DDC as determined during a previous crawl of the document store, and, if the DDC has changed, identifying the documents that have been deleted from the first folder since the previous crawl; and

(b) executable code for determining whether the MLCT associated with the first folder is later than a value of the MLCT as determined during the previous crawl, and, if it is later, identifying the documents that have been added to the folder or modified subsequent to the previous crawl.

15. A crawler application as recited in claim 14, wherein the DDC and MLCT provided by the document store are stored by the crawler application in a History Table in association with address specifiers for folders in the document store.

16. A crawler application as recited in claim 15, wherein, in the History Table, an LCT is stored for documents, and max(LCT, MLCT) and a DDC are stored for folders.

17. A crawler application as recited in claim 16, wherein the History Table also includes a flag to indicate which address specifiers correspond to folders having a DDC value stored in the History Table, and which address specifiers correspond to documents associated with a folder having a DDC value stored in the History Table.

18. A crawler application as recited in claim 15, wherein, for folders, the crawler stores in the History Table the LCT or MLCT of the folder, whichever is greater.

19. A computer system comprising:

a server computer; and

a document store operatively coupled to the server computer, wherein the document store contains a plurality of electronic documents and folders containing references to one or more documents, and wherein the document store provides properties including local commit times (LCTs) and maximum LCTs (MLCTs) for documents and folders in the document store and deleted documents counts (DDCs) for folders in the document store;

wherein the LCT, MLCT and DDC properties are provided for each folder, and a LCT is provided for each document;

wherein the LCT for a folder changes whenever a folder specific property is modified;

wherein the MLCT for the folder changes whenever any contained document'"'"'s LCT changes; and

wherein the LCT of a document changes when a document is modified.

20. A system as recited in claim 19 and further comprising:

a computer readable storage medium operatively coupled to the server computer; and

a computer-executable crawler application stored on the computer readable storage medium.

21. A computer system comprising:

a server computer;

a document store operatively coupled to the server computer, wherein the document store contains a plurality of electronic documents and folders containing references to one or more documents, and wherein the document store provides local commit times (LCTs) and maximum LCTs (MLCTs) for documents and folders in the document store and deleted documents counts (DDCs) for folders in the document store;

a computer readable storage medium operatively coupled to the server computer; and

a computer-executable crawler application stored on the computer readable storage medium;

wherein the crawler application, when executed by the server, causes the following acts to be carried out by the server;

determining whether the DDC for a first folder has changed from a value of the DDC as determined during a previous crawl of the document store, and, if the DDC has changed, identifying the documents that have been deleted from the first folder since the previous crawl; and

determining whether the MLCT associated with the first folder is later than a value of the MLCT as determined during the previous crawl, and, if it is later, identifying the documents that have been added to the folder or modified subsequent to the previous crawl.

22. A system as recited in claim 21, wherein the server computer comprises a member of a group consisting of a Web server, a mail server, a file server and a database server.

23. A computer-readable document store, comprising a plurality of electronic documents and folders containing references to one or more documents, wherein the document store includes properties including local commit times (LCTs) and maximum LCTs (MLCTs) for documents and folders in the document store and deleted documents counts (DDCs) for folders in the document store;

wherein the LCT, MLCT and DDC properties are provided for each folder, and a LCT is provided for each document;

wherein the LCT for a folder changes whenever a folder specific property is modified;

wherein the MLCT for the folder changes whenever any contained document'"'"'s LCT changes; and

wherein the LCT of a document changes when a document is modified.