PIPELINED ARCHITECTURE FOR GLOBAL ANALYSIS AND INDEX BUILDING

• US 20070282829A1
• Filed: 08/17/2007
• Published: 12/06/2007
• Est. Priority Date: 01/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kraft, Reiner, Neumann, Andreas, Qi, Runping, Rajagopalan, Sridhar, McPherson, John, Leung, Tony, Fontoura, Marcus, Zien, Jason, Shekita, Eugene
• Granted Patent: US 7,783,626 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Disclosed is a technique for building an index. A new index_i+1 is built and an anchor text table_i+1 and a duplicates tablet_i+1 are output using a stores_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 table_i+1, the duplicates table_i+1, and the previously generated global analysis computations_i.

Claims

1. A method for building an index, comprising:

building a new index_i+1 and outputting an anchor text table_i+1 and a duplicates table_i+1 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; and

generating new global analysis computations_i+1 using the anchor text table_i+1, the duplicates table_i+1, and the previously generated global analysis computations_i.

2. The method of claim 1, further comprising:

building a delta store_j+1 using the previously generated global analysis computations_i, a delta store_j, and newly crawled documents.

3. The method of claim 1, further comprising:

building a delta index_j+1 using the previously generated global analysis computations_i, a delta store_j, and newly crawled documents.

4. The method of claim 3, wherein the creation of the delta index_j+1 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 index_i+1 and the delta index_j+1 to retrieve one or more documents.

6. The method of claim 3, wherein generating the new global analysis computations_i+1 is performed in parallel with creation of the delta index_j+1.

7. The method of claim 1, wherein the new global analysis computations_i+1 are generated using lagging per-document analysis information.

8. An article of manufacture including a program for building an index, wherein the program causes operations to be performed, the operations comprising:

building a new index_i+1 and outputting an anchor text table_i+1 and a duplicates table_i+1 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; and

generating new global analysis computations_i+1 using the anchor text table_i+1, the duplicates table_i+1, and previously generated global analysis computations_i.

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

building a delta store_j+1 using the previously generated global analysis computations_i, a delta store_j, and newly crawled documents.

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

building a delta index_j+1 using the previously generated global analysis computations, a delta store_j, and newly crawled documents.

11. The article of manufacture of claim 10, wherein the creation of the delta index_j+1 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 index_i+1 and the delta index_j+1 to retrieve one or more documents.

13. The article of manufacture of claim 10, wherein generating the new global analysis computations_i+1 is performed in parallel with creation of the new delta index_j+1.

14. The article of manufacture of claim 8, wherein the new global analysis computations_i+1 are generated using lagging per-document analysis information.

15. A computer system including logic for building an index, comprising:

building a new index_i+1 and outputting an anchor text table_i+1 and a duplicates table_i+1 using a store_i, a delta store, and previously generated global analysis computations_i, wherein the previously generated global analysis computations include an anchor text table_i, a rank table_i, and a duplicates table_i; and

generating new global analysis computations_i+1 using the anchor text table_i+1, the duplicates table_i+1, and previously generated global analysis computations_i.

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

building a delta store_j+1 using the previously generated global analysis computations_i, a delta store_j, and newly crawled documents.

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

building a delta index_j+1 using the previously generated global analysis computations_i, a delta store_j, and newly crawled documents.

18. The computer system of claim 17, wherein the creation of the delta index_j+1 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 index_i+1 and the delta index_j+1 to retrieve one or more documents.

20. The computer system of claim 17, wherein generating the new global analysis computations_i+1 is performed in parallel with creation of the new delta index_j+1.

21. The computer system of claim 15, wherein the new global analysis computations_i+1 are generated using lagging per-document analysis information.