Pipelined architecture for global analysis and index building

• US 7,293,005 B2
• Filed: 01/26/2004
• Issued: 11/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, Leung, Tony K., Rajagopalan, Sridhar, Shekita, Eugene J., Zien, Jason Yeong, McPherson, John Ai Jr., Qi, Runping, Fontoura, Marcus F.
• Primary Examiner(s): Lee; Wilson
• Application Number:
  US10/764,772
• Publication Number:
  US 20050165718A1
• Time in Patent Office: 1,380 Days
• Field of Search: 707 1- 10, 707/100, 707/104.1, 707/102
• US Class Current: 707/741
• 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 in which global analysis computations and index creation are pipelined, wherein the global analysis computations share intermediate results.

Claims

1. A method being executable in a computer for building an index, comprising:

pipelining global analysis computations and index creation, wherein the global analysis computations share intermediate results, wherein the global analysis computations extract properties from a global view of documents in a corpus, and wherein index creation builds the index with results of recent global analysis computations for processing of documents existing at a certain point in time, wherein the intermediate results comprise the output of one of the global analysis computations that is input into another one of the global analysis computations; and

creating a delta index for documents for which no global analysis computations have been performed.

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

3. The method of claim 1, further comprising:

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

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

4. The method of claim 1, wherein creating the delta index further comprises:

merging a delta store and new documents.

5. The method of claim 1, further comprising:

merging the delta index with the index to create a new version of the index.

6. The method of claim 1, further comprising:

performing the global analysis computations using lagging per-document analysis information.

7. The method of claim 1, wherein index creation further comprises:

merging a store and a delta store.

8. The method of claim 1, wherein the global analysis computations are performed in parallel with creation of a new delta index.

9. An article of manufacture comprising a computer readable medium including a program being executable in a computer for building an index, wherein the program causes operations to be performed, the operations comprising:

pipelining global analysis computations and index creation, wherein the global analysis computations share intermediate results, wherein the global analysis computations extract properties from a global view of documents in a corpus, and wherein index creation builds the index with results of recent global analysis computations for processing of documents existing at a certain point in time, wherein the intermediate results comprise the output of one of the global analysis computations that is input into another one of the global analysis computations; and

creating a delta index for documents for which no global analysis computations have been performed.

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

11. The article of manufacture of claim 9 wherein the operations further comprise:

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

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

12. The article of manufacture of claim 9 wherein the operations for creating the delta index further comprise:

merging a delta store and new documents.

13. The article of manufacture of claim 9, wherein the operations further comprise:

merging the delta index with the index to create a new version of the index.

14. The article of manufacture of claim 9, wherein the operations further comprise:

performing the global analysis computations using lagging per-document analysis information.

15. The article of manufacture of claim 9, wherein index creation further comprises:

merging a store and a delta store.

16. The article of manufacture of claim 9, wherein the global analysis computations are performed in parallel with creation of a new delta index.

17. A computer system, comprising:

a processor;

storage coupled to the processor; and

hardware logic to pipeline global analysis computations and index creation, wherein the global analysis computations share intermediate results, wherein the global analysis computations extract properties from a global view of documents in a corpus, and wherein index creation builds the index with results of recent global analysis computations for processing of documents existing at a certain point in time, wherein the intermediate results comprise the output of one of the global analysis computations that is input into another one of the global analysis computations and to create a delta index for documents for which no global analysis computations have been performed.

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

20. The computer system of claim 17, wherein the logic for creating the delta index further comprises:

merging a delta store and new documents.

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

merging the delta index with the index to create a new version of the index.

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

performing the global analysis computations using lagging per-document analysis information.

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

merging a store and a delta store.

24. The computer system of claim 17, wherein the global analysis computations are performed in parallel with creation of a new delta index.