Method and system for rapid retrieval in a full text indexing system

• US 6,216,123 B1
• Filed: 06/24/1998
• Issued: 04/10/2001
• Est. Priority Date: 06/24/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Tietjen, Bruce, Pratt, John P., Millett, Ronald P., Robertson, David O.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/103,702
• Time in Patent Office: 1,021 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/6, 707/101, 707/102, 707/103, 707/519, 271/263, 304/900, 395/759, 709/224, 704/231, 704/251, 400/70
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method and system for generating and searching a full text index. The fill text index includes the use of word numbers and a minimum delta which minimizes the need to access document level information during the application of search operators. Word registers having coordinated document level and word level information, as well as relevance information are used in search operations. Word numbers are clustered together during sub-operations in preparation for the next operation in a search query. The fill text index according to the present invention is extremely efficient and greatly reduces table accesses and/or disk I/Os.

Claims

1. A method for generating a full text index of a plurality of documents comprising:

associating at least one group of word numbers with the words of an indexed document, the indexed document having an initial word number and a final word number associated therewith, the group having a predetermined group size greater than one, the initial word number associated with any indexed document being at least a group size distance from an initial word number associated with another indexed document;

ensuring that a minimum delta value exists between a final word number associated with one indexed document and an initial word number associated with another indexed document;

generating a word list having a plurality of word entries, each word entry comprising a word and a list of word numbers associated with the word; and

generating a cross-reference table containing a cross-reference entry for each group, each cross reference entry containing a reference to an indexed document with which the group has been associated.

2. A method according to claim 1, further comprising determining that a first word and a second word are contained in a same indexed document by passing the word number associated with the first word through a hash to generate a first hash value and passing the word number associated with the second word through the hash to generate a second hash value, and determining that the first hash value and the second hash value are equivalent.

3. A method according to claim 1, further comprising determining that a first word and a second word are contained in a same indexed document by determining that a numeric difference between the word number associated with the first word and the word number associated with the second word is less than the minimum delta.

4. A method according to claim 1, wherein the cross-reference table includes one or more entries for each indexed document, further comprising generating a boundary table containing a boundary entry for each entry in the cross-reference table, each said boundary entry indicating whether a corresponding entry in the cross-reference table is a first entry associated with a respective indexed document, or a subsequent entry associated with a respective indexed document.

5. A method according to claim 1, further comprising using a word register to maintain word information about a search word in a search request, the word register including a register document list and a register word list, the register word list being operative to contain a list of word numbers associated with the search word in the indexed documents, and the register document list being operative to contain a list of references to the indexed documents containing the search word and a lowest and highest word number contained in the register word list for each respective reference.

6. A method according to claim 5, wherein the word register further comprises a word number relevance list that is operative to contain a list of relevance numbers, each relevance number corresponding to a respective word number in the register word list.

7. A method according to claim 6, wherein the word register further comprises a document relevance list, the document relevance list being operative to contain a list of relevance numbers, each relevance number corresponding to a respective reference in the register document list.

8. A method according to claim 7, wherein a relevance number contained in the document relevance list corresponds to a respective reference in the register document list and is created as a function of the relevance numbers in the word number relevance list that are associated with word numbers associated with the respective reference.

9. A method according to claim 6, further comprising generating a result word register as a function of a first and second word register, the word number relevance list of the result word register being derived as a function of the relevance numbers in the first and second word registers, each relevance number in the word number relevance list of the result word register corresponding to a respective word number in the register word list of the result word register.

10. A method according to claim 9, further comprising delaying the generation of the register document list of the result register until after the generation of the register word list of the result register.

11. A method according to claim 10, wherein the generation of the register document list is delayed until a document level operation must be carried out.

12. A method according to claim 5, further comprising maintaining a plurality of word numbers in a word cluster, each word cluster being derived from a plurality of word numbers, and having a word cluster relevance number associated therewith, the word cluster relevance number being derived as a function of the individual relevance numbers associated with the words in the cluster.

13. A method according to claim 5, wherein each word cluster relevance number is in a range of about 0 to about 100.

14. A method for generating a full text index of a plurality of documents, comprising:

associating a word number with each word in a plurality of documents, each document having associated therewith an initial word number and a final word number, the initial word number associated with each document being at least a predetermined increment from an initial word number associated with another document, the predetermined increment being greater than one;

providing a minimum inter-document word number delta between a word number in one document and a word number in another document;

generating a word list containing words and the word numbers associated with the respective word; and

generating a document cross-reference table associating word numbers with a respective document.

15. A method according to claim 14, further comprising determining if a first word and a second word are located in a same document by determining that an absolute difference between the word number associated with the first word and the word number associated with the second word is less than the minimum inter-document word number delta.

16. A method according to claim 14, further comprising generating a boundary table having a boundary entry corresponding to each cross reference entry, each boundary entry indicating whether the corresponding cross reference entry is the first cross reference entry associated with a document.

17. A full text index, comprising:

a word table being operative to contain a plurality of lists of word numbers, the word numbers being associated with words in a plurality of indexed documents, each indexed document having at least one group of word numbers associated therewith and having a first word number and a last word number, each group having a uniform size greater than one, and the first word number of any document being at least the uniform size away from the first word number of any other document, wherein a minimum delta exists between a final word number associated with an indexed document and an initial word number associated with any other indexed document; and

a cross-reference table comprising a reference entry corresponding to each group of word numbers and containing a reference to an indexed document to which the group of word numbers is associated.

18. A full text index according to claim 17, further comprising a border table containing a border entry corresponding to each reference entry in the cross-reference table, each border entry being operative to indicate whether the word numbers associated with the reference entry are a first group of word numbers associated with an indexed document.

19. A full text index according to claim 17, wherein the word table contains a plurality of separate lists for at least one word, each separate list containing word numbers of words having a common attribute.