Pipelined architecture for global analysis and index building

• US 20050165718A1
• Filed: 01/26/2004
• Published: 07/28/2005
• 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.
• Granted Patent: US 7,293,005 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 in which global analysis computations and index creation are pipelined, wherein the global analysis computations share intermediate results.

Claims

1. A method for building an index, comprising:

pipelining global analysis computations and index creation, wherein the global analysis computations share intermediate results.

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

creating an index using lagging global analysis information.

3. The method of claim 1, further comprising:

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

4. The method of claim 3, 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.

5. The method of claim 3, 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.

6. The method of claim 3, wherein creating the delta index further comprises:

merging a delta store and new documents.

7. The method of claim 3, further comprising:

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

8. The method of claim 1, further comprising:

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

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

merging a store and a delta store.

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

11. An article of manufacture including a program 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.

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

creating an index using lagging global analysis information.

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

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

14. The article of manufacture of claim 13, 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.

15. The article of manufacture of claim 13, 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.

16. The article of manufacture of claim 13, wherein the operations for creating the delta index further comprise:

merging a delta store and new documents.

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

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

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

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

19. The article of manufacture of claim 11, wherein index creation further comprises:

merging a store and a delta store.

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

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

pipelining global analysis computations and index creation, wherein the global analysis computations share intermediate results.

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

creating an index using lagging global analysis information.

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

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

24. The computer system of claim 23, 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.

25. The computer system of claim 23, 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.

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

merging a delta store and new documents.

27. The computer system of claim 23, wherein the logic further comprises:

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

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

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

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

merging a store and a delta store.

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