Information retrieval system for archiving multiple document versions

• US 7,702,618 B1
• Filed: 01/25/2005
• Issued: 04/20/2010
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US11/043,438
• Time in Patent Office: 1,911 Days
• Field of Search: 707 3- 6, 707/203, 707/102, 715/526, 715/511, 715/500, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Index data for multiple versions or instances of documents is also maintained. Each document instance is associated with a date range and relevance data derived from the document for the date range.

Claims

1. A method performed by at least one computer systems of providing an archival index of a plurality of documents, the method comprising:

maintaining an index of a plurality of documents, the index relating phrases contained in at least some of the documents with documents containing the phrases;

accessing a document of the plurality of documents;

determining, using a processor of the at least one computer system, whether the document has changed since a previous date the document was indexed;

responsive to determining that the document has changed,

indicating a first date range, including the previous date, for which the document is valid;

indexing the document to obtain current information-retrieval relevance data for the document, the current information-retrieval relevance data including phrases contained in a current version of the document;

storing the current information-retrieval relevance data in association with a current date range for the document; and

maintaining previous information-retrieval relevance data for the document in association with the first date range, the previous information-retrieval relevance data including phrases contained in a version of the document that was valid during the first date range.

2. The method of claim 1, wherein determining whether the document has changed since a previous date the document was indexed, comprises:

identifying current information-retrieval relevance data for the document;

determining the document to have changed responsive based on a change in the current information-retrieval relevance data relative to information-retrieval relevance data for the document on the previous date.

3. The method of claim 2, wherein the information-retrieval relevance data further include one or more data from the group consisting of:

document length, term frequency, types of HTML markup.

4. The method of claim 2, wherein the information-retrieval relevance data for a document include data a page rank for the document.

5. The method of claim 2, wherein the information-retrieval relevance data for a document include data a number of inlinks for the document.

6. The method of claim 1, wherein determining whether the document has changed since a previous date the document was indexed, comprises:

identifying, at the time that the document is indexed, a current set of topics for the document; and

determining the document to have changed responsive based on a change in the current set of topics relative to a prior set of topics associated with the document on the previous date.

7. The method of claim 1, further comprising:

storing for a document a plurality of date ranges, each date range associated with information-retrieval relevance data for the document during the date range.

8. The method of claim 1, wherein storing the current information-retrieval relevance data in association with a current date range for the document comprises:

storing an open date for the document indicating a first date for which the document is currently valid, and a status value indicating that the document is currently valid.

9. The method of claim 1, further comprising:

deriving a unique document identifier for an instance associated with a date range for a document from a date included in the date range and from a document locator for the document.

10. The method of claim 9, wherein the data included in the date range includes the first date for the date range.

11. The method of claim 1, wherein indexing the document to obtain current information-retrieval relevance data for the document includes generating a posting list for a phrase contained in the document and associating a document identifier with the phrase in the posting list.

12. The method of claim 11, wherein the phrase is good phrase that predicts the occurrence of other phrases in a corpus of documents that is indexed.

13. The method of claim 1, wherein the index of the plurality of documents includes posting lists for phrases contained in the plurality of documents, and the posting lists include document identifiers of documents that contain the phrases for the posting lists.

14. The method of claim 13, wherein phrases of the posting lists include good phrases.

15. The method of claim 14, wherein the posting lists for a good phrase includes, for each document in the posting list, information about related phrases, related to the good phrase, which appear in the document.

16. A method performed by at least one computer system of providing an archival index, the method comprising:

maintaining an index of a plurality of documents, the index relating phrases contained in at least some of the documents with documents containing the phrases, each document associated with a current date range for which the document is currently indexed and associated with current information-retrieval relevance data for the current date range, wherein the current date range includes a first date, and at least one document associated with a plurality of non-overlapping, contiguous date ranges prior to the current date range, each prior date range having information-retrieval relevance data for the document for that date range;

accessing a document of the plurality of documents that has been previously indexed and having current information-retrieval relevance data;

responsive to the accessed document having changed since the first date,

updating, using a processor of the at least one computer system, the current date range for the changed document to be a new prior date range and to include a closed date;

storing the current information-retrieval relevance data for the changed document as information-retrieval relevance data for the new prior date range;

establishing, using a processor, a new current date range for the changed document, wherein the new current date range includes a current date as an open date;

updating the current information-retrieval relevance data for the changed document, the updated current information-retrieval relevance data including phrases contained in the changed document; and

storing the updated current information-retrieval relevance data in association with the new current date range.

17. The method of claim 16, further comprising:

identifying information-retrieval relevance data for the accessed document;

determining the accessed document to have changed responsive based on a change in the information-retrieval relevance data relative to information-retrieval relevance data for the document on a previous date.

18. The method of claim 17, wherein the information-retrieval relevance data further include one or more data from the group consisting of:

document length, term frequency, types of HTML markup.

19. The method of claim 16, further comprising:

identifying, at the time that the accessed document is accessed, a current set of topics for the document; and

determining the accessed document to have changed responsive based on a change in the current set of topics relative to a prior set of topics associated with the document on a previous date.

20. The method of claim 16, further comprising:

deriving a first unique document identifier for an instance of the accessed document associated with a the new prior date range for a document from a date included in the prior date range and from a document locator for the accessed document; and

deriving a second unique document identifier for an instance of the accessed document associated with a the new current date range for a document from a date included in the new current date range and from a document locator for the accessed document.

21. A tangible computer readable storage medium storing a computer program executable by a processor for providing an archival index, the actions of the computer program comprising:

maintaining an index of a plurality of documents, the index relating phrases contained in at least some of the documents with documents containing the phrases;

accessing a document of the plurality of documents;

determining whether the document has changed since a previous date the document was indexed;

responsive to determining that the document has changed,

indicating a first date range including the previous date and a recent date for which the document is valid;

indexing the document to obtain current information-retrieval relevance data for the document, the current information-retrieval relevance data including phrases contained in a current version of the document;

storing the current information-retrieval relevance data in association with a current date range for the document; and

maintaining previous information-retrieval relevance data for the document in association with the first date range, the previous information-retrieval relevance data including phrases contained in a version of the document that was valid during the first date range.

22. The computer readable storage medium of claim 21, wherein determining whether the document has changed since a previous date the document was indexed, comprises:

identifying current information-retrieval relevance data for the document;

determining the document to have changed responsive to a change in the current information-retrieval relevance data relative to information-retrieval relevance data for the document on the previous date.

23. The computer readable storage medium of claim 22, wherein the information-retrieval relevance data are one or more data from the group consisting of:

document length, term frequency, types of HTML markup.

24. The computer readable storage medium of claim 21, wherein determining whether the document has changed since a previous date the document was indexed, comprises:

identifying, at the time that the document is indexed, a current set of topics for the document; and

determining the document to have changed responsive to a change in the current set of topics relative to a prior set of topics associated with the document on the previous date.

25. The computer readable storage medium of claim 21, further comprising:

storing for a document a plurality of date ranges, each date range associated with information-retrieval relevance data for the document during the date range.

26. The computer readable storage medium of claim 21, wherein storing the current information-retrieval relevance data in association with a current date range for the document comprises:

storing an open date for the document indicating a first date for which the document is currently valid, and a status value indicating that the document is currently valid.

27. The computer readable storage medium of claim 21, further comprising:

deriving a unique document identifier for an instance associated with a date range for a document from a date included in the date range and from a document locator for the document.

28. The computer readable storage medium of claim 27, wherein the data included in the date range is the first date for the date range.

29. A tangible computer readable storage medium storing a computer program executable by a processor for providing an archival index, the actions of the computer program comprising:

maintaining an index of a plurality of documents, the index relating phrases contained in at least some of the documents with documents containing the phrases, each document associated with a current date range for which the document is currently indexed, and current information-retrieval relevance data for the current date range, wherein the current date range includes a first date, and at least one document associated with a plurality of non-overlapping, contiguous date ranges prior to the current date range, each prior date range having information-retrieval relevance data for the document for that date range;

accessing a document of the plurality of documents that has been previously indexed and having current information-retrieval relevance data;

responsive to the accessed document having changed since the first date,

updating, using a processor of the at least one computer system, the current date range for the changed document to be a new prior date range and to include a closed date;

storing the current information-retrieval relevance data for the changed document as information-retrieval relevance data for the new prior date range;

establishing, using a processor, a new current date range for the changed document, wherein the new current date range includes a current date as an open date;

updating the current information-retrieval relevance data for the changed document, the updated current information-retrieval relevance data including phrases contained in the changed document; and

storing the updated current information-retrieval relevance data in association with the new current date range.

30. The computer readable storage medium of claim 29, the action of the computer program further comprising:

deriving a first unique document identifier for an instance of the accessed document associated with a the new prior date range for a document from a date included in the prior date range and from a document locator for the accessed document; and

deriving a second unique document identifier for an instance of the accessed document associated with a the new current date range for a document from a date included in the new current date range and from a document locator for the accessed document.

31. The computer readable storage medium of claim 29, the action of the computer program further comprising:

identifying information-retrieval relevance data for the accessed document;

determining the accessed document to have changed responsive based on a change in the information-retrieval relevance data relative to information-retrieval relevance data for the document on a previous date.

32. The computer readable storage medium of claim 29, wherein the information-retrieval relevance data further include one or more data from the group consisting of:

document length, term frequency, types of HTML markup.

33. The computer readable storage medium of claim 29, the action of the computer program further comprising:

identifying, at the time that the accessed document is accessed, a current set of topics for the document; and

determining the accessed document to have changed responsive based on a change in the current set of topics relative to a prior set of topics associated with the document on a previous date.

34. A tangible computer-program product, stored on computer-readable storage medium, for archival indexing of a plurality of documents, the product comprising instructions executable to cause a processor to:

receive a current version of a document previously indexed in an index under a previous version of the document, wherein the index relates phrases contained in at least some of the documents with documents containing the phrases;

determine whether the document'"'"'s current version differs from the previous version;

responsive to a determination that the current version differs from the previous version;

index the document under its current version, in the index;

specify a first date range during which the document was indexed under its previous version and associate any previous information-retrieval relevance data for the document with the first date range, wherein the previous information-retrieval relevance data includes phrases contained in the previous version of the document;

specify a second date range during which the document is indexed under its current version and associate any current information-retrieval relevance data with the second date range, wherein the current information-retrieval relevance data includes phrases contained in the current version of the document; and

store, for the indexed document, the first and second date ranges along with their respective information-retrieval relevance data.