Compressed document surrogates

• US 6,665,665 B1
• Filed: 07/30/1999
• Issued: 12/16/2003
• Est. Priority Date: 07/30/1999
• Status: Expired due to Term

• Current Assignee: Knapp Investment Company Limited
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Ponte, Jay Michael
• Primary Examiner(s): Alam, Shahid Al
• Application Number:
  US09/365,326
• Time in Patent Office: 1,600 Days
• Field of Search: 707/3-5, 707/10, 707/101, 707/102, 707/1, 707/100, 707/203, 707/513, 709/218, 709/219, 709/223, 709/226, 709/250, 713/153, 713/201, 715/513, 715/501.1, 717/151, 717/121, 717/168
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Disclosed is a method and device for storing information about Web documents such as pages or sites in a manner which may be used in conjunction with inverted term lists to facilitate the retrieval of documents of interest from the Web. The method involves constructing compressed surrogates for documents, such that various operations may be performed without the need to retrieve a copy of the document from the Web. The method permits the efficient updating of inverted term lists when documents on the Web have been modified or deleted, and also permits the efficient processing of search queries in a variety of circumstances.

Claims

1. A method for maintaining information about documents in a database, the method comprising:

(a) creating a compressed document surrogate corresponding to each document that is part of a collection of documents of interest in said database, so as to identify terms occurring in said each document that is part of said collection;

(b) inserting in said compressed document surrogate information about terms which occur in said each document that is part of said collection, and,

(c) creating at least one inverted term list corresponding to at least one selected term of interest which occurs in said database, said at least one inverted term list including;

at least one document identifier number to uniquely identify a selected document in said database, and corresponding information indicating how often said selected term of interest occurs in said selected document.

2. The method of claim 1, where the documents consist of Web pages.

3. The method of claim 1, where the documents consist of Web sites.

4. The method of claim 1, where the compressed document surrogates and inverted term lists contain information about the same terms.

5. The method of claim 1, where the terms about which the compressed document surrogates and inverted term lists contain information are all terms which occur in the database.

6. The method of claim 1, where the terms about which the compressed document surrogates and inverted term lists contain information are a subset of all terms, excluding common words.

7. The method of claim 1, where the information about each term included in a compressed document surrogate for a document, includes at least one of:

a term identification number, a location in a lookup table of an entry for the term, an address of an inverted term list of the term, an address of a location in the inverted term list for the term of the document, a number of times the term occurs in the document, and a location in the document of each occurrence of the term.

8. The method of claim 1, where the information about each term included in a compressed document surrogate for a document includes a term identification number for each term found in the document.

9. The method of claim 8, where the information about each term included in a compressed document surrogate for a document includes the number of occurrences of the term in the document.

10. The method of claim 8, where the terms are stored in the compressed document surrogate in term identification number order.

11. The method of claim 10, where the term identification number of a term in the compressed document surrogate is given relative to the term identification number of the prior term in the document.

12. The method of claim 11, where information about terms is stored in a lookup table which is a fixed array in which information about terms is stored in term identification number order.

13. The method of claim 12, where the information the lookup table stores includes at least one of:

the term in a natural language, the address of the inverted term list of the term, the number of documents in the database which contain the term, and the maximum term frequency score for any document on any inverted term list for the term.

14. The method of claim 12, where the information the lookup table stores includes the term in a natural language, the address of the inverted term list of the term, the number of documents in the database which contain the term, and the maximum term frequency score for any document on any inverted term list for the term.

15. The method of claim 1, where there are two inverted term lists for each term:

a top inverted term list containing information about the documents which contain the term most frequently, and a remainder inverted term list containing information about all other documents which contain the term.

16. A device for maintaining information about documents in a database, the device comprising:

(a) means for creating a compressed document surrogate corresponding to each document that is part of a collection of documents of interest in said database, so as to identify terms occurring in said each document that is part of said collection;

(b) means for inserting in said compressed document surrogate information about terms which occur in said each document that is part of said collection, and,

(c) means for creating at least one inverted term list corresponding to at least one selected term of interest which occurs in said database, said at least one inverted term list including;

at least one document identifier number to uniquely identify a selected document in said database, and corresponding information indicating how often said selected term of interest occurs in said selected document.

17. The device of claim 16, where the documents consist of Web pages.

18. The device of claim 16, where the documents consist of Web sites.

19. The device of claim 16, where the compressed document surrogates and inverted term lists contain information about the same terms.

20. The device of claim 16, where the terms about which the compressed document surrogates and inverted term lists contain information are all terms which occur in the database.

21. The device of claim 16, where the terms about which the compressed document surrogates and inverted term lists contain information are a subset of all terms, excluding common words.

22. The device of claim 16, where the information about each term included in a compressed document surrogate for a document, includes at least one of:

a term identification number, a location in a lookup table of an entry for the term, an address of an inverted term list of the term, an address of a location in the inverted term list for the term of the document, a number of times the term occurs in the document, and a location in the document of each occurrence of the term.

23. The device of claim 16, where the information about each term included in a compressed document surrogate for a document includes a term identification number for each term found in the document.

24. The device of claim 23, where the information about each term included in a compressed document surrogate for a document includes the number of occurrences of the term in the document.

25. The device of claim 23, where the terms are stored in the compressed document surrogate in term identification number order.

26. The device of claim 25, where the term identification number of a term in the compressed document surrogate is given relative to the term identification number of the prior term in the document.

27. The device of claim 26, where information about terms is stored in a lookup table which is a fixed array in which information about terms is stored in term identification number order.

28. The device of claim 27, where the information the lookup table stores includes at least one of:

the term in a natural language, the address of the inverted term list of the term, the number of documents in the database which contain the term, and the maximum term frequency score for any document on any inverted term list for the term.

29. The device of claim 27, where the information the lookup table stores includes the term in a natural language, the address of the inverted term list of the term, the number of documents in the database which contain the term, and the maximum term frequency score for any document on any inverted term list for the term.

30. The device of claim 16, where there are two inverted term lists for each term:

a top inverted term list containing information about the documents which contain the term most frequently, and a remainder inverted term list containing information about all other documents which contain the term.