ARCHITECTURE FOR AN INDEXER

• US 20070271268A1
• Filed: 08/06/2007
• Published: 11/22/2007
• Est. Priority Date: 01/26/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zien, Jason, NEUMANN, Andreas, FONTOURA, Marcus, RAJAGOPALAN, Sridhar, SHEKITA, Eugene
• Granted Patent: US 7,743,060 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Disclosed is a technique for indexing data. For each token in a set of documents, a sort key is generated that includes a document identifier that indicates whether a section of a document associated with the sort key is an anchor text section or a context section, wherein the anchor text section and the context text section have a same document identifier; it is determined whether a data field associated with the token is a fixed width; when the data field is a fixed width, the token is designated as one for which fixed width sort is to be performed; and, when the data field is a variable length, the token is designated as one for which a variable width sort is to be performed. The fixed width sort and the variable width sort are performed. For each document, the sort keys are used to bring together the anchor text section and the context section of that document.

Claims

1. A method for indexing data, comprising:

for each token in a set of documents, generating a sort key that includes a document identifier that indicates whether a section of a document associated with the sort key is an anchor text section or a context section, wherein the anchor text section and the context text section have a same document identifier;

determining whether a data field associated with the token is a fixed width;

when the data field is a fixed width, designating the token as one for which fixed width sort is to be performed; and

when the data field is a variable length, designating the token as one for which a variable width sort is to be performed;

performing the fixed width sort and the variable width sort; and

for each document, using the sort keys to bring together the anchor text section and the context section of that document.

2. The method of claim 1, wherein the token is variable width and further comprising:

transforming the variable width token into a fixed width token.

3. The method of claim 1, further comprising:

performing the fixed width sort on one of dual code paths and the variable width sort on the other of dual code paths.

4. The method of claim 1, wherein the sort key includes a token type, a token, a document section, and an offset in a document.

5. The method of claim 1, further comprising:

receiving the context section and the anchor text section of a document at different times.

6. The method of claim 1, further comprising:

using the sort keys generated for each token to create posting lists that simultaneously are ordered by token and by document identifier for each token.

7. The method of claim 1, further comprising:

sorting on certain bits of a sort key containing multiple bits.

8. The method of claim 7, further comprising:

sorting on uppermost bits of the sort key.

9. A computer system including logic for indexing data, comprising:

for each token in a set of documents,

generating a sort key that includes a document identifier that indicates whether a section of a document associated with the sort key is an anchor text section or a context section, wherein the anchor text section and the context text section have a same document identifier;

determining whether a data field associated with the token is a fixed width;

when the data field is a fixed width, designating the token as one for which fixed width sort is to be performed; and

when the data field is a variable length, designating the token as one for which a variable width sort is to be performed;

performing the fixed width sort and the variable width sort; and

for each document, using the sort keys to bring together the anchor text section and the context section of that document.

10. The computer system of claim 9, wherein the token is variable width and wherein the logic further comprises:

transforming the variable width token into a fixed width token.

11. The computer system of claim 9, wherein the logic further comprises:

performing the fixed width sort on one of dual code paths and the variable width sort on the other of dual code paths.

12. The computer system of claim 9, wherein the sort key includes a token type, a token, a document section, and an offset in a document.

13. The computer system of claim 9, wherein the logic further comprises:

receiving the context section and the anchor text section of a document at different times.

14. The computer system of claim 9, wherein the logic further comprises:

using the sort keys generated for each token to create posting lists that simultaneously are ordered by token and by document identifier for each token.

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

sorting on certain bits of a sort key containing multiple bits.

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

sorting on uppermost bits of the sort key.

17. An article of manufacture comprising one of hardware logic and a computer readable medium including a program for indexing data, wherein the hardware logic or program causes operations to be performed, the operations comprising:

for each token in a set of documents,

generating a sort key that includes a document identifier that indicates whether a section of a document associated with the sort key is an anchor text section or a context section, wherein the anchor text section and the context text section have a same document identifier;

determining whether a data field associated with the token is a fixed width;

when the data field is a fixed width, designating the token as one for which fixed width sort is to be performed; and

when the data field is a variable length, designating the token as one for which a variable width sort is to be performed;

performing the fixed width sort and the variable width sort; and

for each document, using the sort keys to bring together the anchor text section and the context section of that document.

18. The article of manufacture of claim 17, wherein the token is variable width and wherein the operations further comprise:

transforming the variable width token into a fixed width token.

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

performing the fixed width sort on one of dual code paths and the variable width sort on the other of dual code paths.

20. The article of manufacture of claim 17, wherein the sort key includes a token type, a token, a document section, and an offset in a document.

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

receiving the context section and the anchor text section of a document at different times.

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

using the sort keys generated for each token to create posting lists that simultaneously are ordered by token and by document identifier for each token.

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

sorting on certain bits of a sort key containing multiple bits.

24. The article of manufacture of claim 23, wherein the operations further comprise:

sorting on uppermost bits of the sort key.