Pipelined architecture for global analysis and index building

• US 7,783,626 B2
• Filed: 08/17/2007
• Issued: 08/24/2010
• Est. Priority Date: 01/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Zien, Jason Yeong, McPherson, John A. Jr., Kraft, Reiner, Neumann, Andreas, Leung, Tony Kai-Chi, Fontoura, Marcus Felipe, Rajagopalan, Sridhar, Shekita, Eugene J., Qi, Runping
• Primary Examiner(s): Lee; Wilson
• Application Number:
  US11/840,881
• Publication Number:
  US 20070282829A1
• Time in Patent Office: 1,103 Days
• Field of Search: 707 1- 10, 707/100, 707713-723, 707726-728, 707741-754
• US Class Current: 707/716
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Provided is a technique for building an index. A new index_i+1 is built and an anchor text table_i+1 and a duplicates table_i+1 are output using a store_i, a delta store, and previously generated global analysis computations_i, wherein the previously generated global analysis computations_i include an anchor text table_i, a rank table_i, and a duplicates table_i. New global analysis computations_i+1 are generated using the anchor text tablei+1, the duplicates table_i+1, and the previously generated global analysis computations_i.

Claims

1. A method for building an index, comprising:

storing, using a computer with a processor, a current version of a store having a tokenized version of each document in a corpus of documents, a delta store accumulating changes to the current version of the store, and previously generated global analysis computations, wherein the previously generated global analysis computations include an anchor text table, a rank table, and a duplicates table;

building a new version of the index and outputting a raw anchor text table and a raw duplicates table a by accessing the current version of the store, the delta store, and the previously generated global analysis, computations; and

generating new global analysis computations by accessing the raw anchor text table, the raw duplicates table, and the previously generated global analysis computations, wherein the new global analysis computations include a new anchor text table, a new rank table, and a new duplicates table.

2. The method of claim 1, further comprising:

building a new version of a delta store using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

3. The method of claim 1, further comprising:

building a new version of a delta index using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

4. The method of claim 3, wherein the creation of the new delta index allows new documents to be indexed and retrieved before global analysis computations for the new documents are performed.

5. The method of claim 3, further comprising:

receiving a query requesting retrieval of one or more documents; and

accessing the new version of the index and the new version of the delta index to retrieve one or more documents.

6. The method of claim 3, wherein generating the new global analysis computations is performed in parallel with creation of the new version of the delta index.

7. The method of claim 1, wherein the new global analysis computations are generated using results of recent processing of documents existing at a certain point in time.

8. An article of manufacture comprising a tangible computer readable storage medium storing a program for building an index, wherein the program, when executed by a processor of a computer, causes operations to be performed, the operations comprising:

storing a current version of a store having a tokenized version of each document in a corpus of documents, a delta store accumulating changes to the current version of the store, and previously generated global analysis computations, wherein the previously generated global analysis computations include an anchor text table, a rank table, and a duplicates table;

building a new version of the index and outputting a raw anchor text table and a raw duplicates table by accessing the current version of the store store_i, the delta store, and the previously generated global analysis computations; and

generating new global analysis computations by accessing the raw anchor text table, the raw duplicates table, and the previously generated global analysis computations, wherein the new global analysis computations include a new anchor text table, a new rank table, and a new duplicates table.

9. The article of manufacture of claim 8, wherein the operations for index creation further comprise:

building a new version of a delta store using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

10. The article of manufacture of claim 8, wherein the operations further comprise:

building a new version of a delta index using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

11. The article of manufacture of claim 10, wherein the creation of the new delta index allows new documents to be indexed and retrieved before global analysis computations for the new documents are performed.

12. The article of manufacture of claim 10, wherein the operations further comprise:

receiving a query requesting retrieval of one or more documents; and

accessing the new version of the index and the new version of the delta index to retrieve one or more documents.

13. The article of manufacture of claim 10, wherein generating the new global analysis computations is performed in parallel with creation of the new version of the delta index.

14. The article of manufacture of claim 8, wherein the new global analysis computations are generated using results of recent processing of documents existing at a certain point in time.

15. A computer system, comprising:

a processor; and

hardware logic for;

storing a current version of a store having a tokenized version of each document in a corpus of documents, a delta store accumulating changes to the current version of the store, and previously generated global analysis computations, wherein the previously generated global analysis computations include an anchor text table, a rank table, and a duplicates table;

building a new version of the index and outputting a raw anchor text table and a raw duplicates table by accessing the current version of the store, the delta store, and the previously generated global analysis computations; and

generating new global analysis computations by accessing the raw anchor text table, the raw duplicates table, and the previously generated global analysis computations, wherein the new global analysis computations include a new anchor text table, a new rank table, and a new duplicates table.

16. The computer system of claim 15, wherein the logic for index creation further comprises:

building a new version of a delta store using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

17. The computer system of claim 15, wherein the logic further comprises:

building a new version of a delta index using the previously generated global analysis computations, a current version of a delta store, and newly crawled documents.

18. The computer system of claim 17, wherein the creation of the new delta index allows new documents to be indexed and retrieved before global analysis computations for the new documents are performed.

19. The computer system of claim 17, wherein the logic further comprises:

receiving a query requesting retrieval of one or more documents; and

accessing the new version of the index and the new version of the delta index to retrieve one or more documents.

20. The computer system of claim 17, wherein generating the new global analysis computations is performed in parallel with creation of the new version of the delta index.

21. The computer system of claim 15, wherein the new global analysis computations are generated using results of recent processing of documents existing at a certain point in time.