Integrating external related phrase information into a phrase-based indexing information retrieval system

• US 8,117,223 B2
• Filed: 09/07/2007
• Issued: 02/14/2012
• Est. Priority Date: 09/07/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US11/851,962
• Publication Number:
  US 20090070312A1
• Time in Patent Office: 1,621 Days
• Field of Search: 705/79, 707722-723, 707727-730, 707/759, 707765-767, 715900-901
• US Class Current: 707/759
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents, analyzing documents and storing the results of the analysis as phrase data. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Changes to existing phrase data about a document collection submitted by a user is captured and analyzed, and the existing phrase data is updated to reflect the additional knowledge gained through the analysis.

Claims

1. A computer-implemented method for updating phrases associated with a limited document collection, comprising:

determining, by at least one processor of a computer system, a list of top phrases for the limited document collection, at least in part based on presence, in documents of the document collection, of both the top phrases and related phrases of the top phrases;

receiving, by at least one processor of the computer system, a replacement phrase for at least one of the top phrases; and

updating, by at least one processor of the computer system, related phrase data for the replacement phrase from the related phrase data of the top phrase that is being replaced.

2. A computer-implemented method of determining top phrases of a limited document collection, comprising:

determining, by at least one processor of a computer system, top phrases for a plurality of documents in the limited document collection, wherein determining the top phrases of a document includes;

identifying phrases in the document;

for each identified phrase in the document, determining an importance score for the identified phrase based on occurrences of related phrases of the identified phrase, which are also in the document;

associating each top phrase with the importance score for the document;

for each top phrase, determining, by at least one processor of the computer system, an aggregate score of the top phrase for the limited document collection based on the top phrase'"'"'s scores for individual documents of the limited document collection in which the top phrase appears; and

selecting, by at least one processor of the computer system, a set of top phrases with the highest aggregate scores.

3. The method of claim 2, wherein determining the related phrases of an identified phrase comprises examining a posting list for the identified phrase.

4. The method of claim 2, wherein determining the importance score of an identified phrase in the document is based on a frequency of the related phrases in the document.

5. The method of claim 2, wherein determining an aggregate score for the top phrase comprises summing the scores of the top phrase for each document for which the top phrase is a top phrase.

6. The method of claim 5, further comprising weighting each summed score based on a location within the document collection of the document to which the summed score corresponds.

7. The method of claim 2, further comprising modifying the aggregate score by combining it with a previously determined aggregate score.

8. The method of claim 7, wherein the combination of the aggregate score and the previously determined aggregate score is accomplished by a linear combination of the aggregate score and the previously determined aggregate score.

9. A computer-implemented method comprising:

receiving, by at least one processor of a computer system, a user request to change a current top phrase for a limited document collection to a replacement top phrase;

associating, by at least one processor of the computer system, the replacement top phrase with a root document of the document collection;

associating, by at least one processor of a computer system, the current top phrase and the replacement top phrase with each other;

adding, by at least one processor of the computer system, to phrase information for the replacement top phrase, phrase information for the current top phrase; and

adding, by at least one processor of the computer system, to related phrase information of the replacement top phrase, related phrase information of the current top phrase.

10. The method of claim 9, wherein associating the replacement top phrase with the root document of the document collection comprises adding the root document of the document collection to a posting list for the replacement top phrase.

11. The method of claim 9, wherein associating the current top phrase and replacement top phrase with each other comprises:

adding the current top phrase to a related phrase list of the replacement top phrase; and

adding the replacement top phrase to a related phrase list of the current top phrase.

12. The method of claim 9,wherein adding to phrase information for the replacement top phrase, phrase information for the current top phrase, comprises:

determining a count corresponding to a related phrase of the current top phrase that is also a top phrase of the limited document collection;

creating for the replacement top phrase a corresponding copy of the count;

determining each related phrase of the replacement top phrase that is also a top phrase of the limited document collection; and

updating for the replacement top phrase, a count of the determined related phrases based on a number of occurrences of the related phrases.

13. The method of claim 9, wherein adding to related phrase information for the replacement top phrase, related phrase information of the current top phrase, comprises incrementing counts of related phrases of the replacement top phrase that are also related phrases of the current top phrase.

14. The method of claim 9, further comprising denying the request to change the current top phrase to the current top phrase, responsive to the current and replacement top phrases having no related phrases in common.

15. The method of claim 9, further comprising decrementing the counts of the related phrases of the replacement top phrase, responsive to the current and replacement top phrases having no related phrases in common.

16. A system comprising:

a tangible computer readable medium storing instructions that when executed by one or more processors cause the system to;

determine top phrases for a plurality of documents in a limited document collection, wherein determining the top phrases of a document includes;

identifying phrases in the document;

for each identified phrase in the document, determining an importance score for the identified phrase based on occurrences of related phrases of the identified phrase, which are also in the document;

associate each top phrase with the importance score for the document;

for each top phrase, determine an aggregate score of the top phrase for the limited document collection based on the top phrase'"'"'s scores for individual documents of the limited document collection in which the top phrase appears; and

select a set of top phrases with the highest aggregate scores; and

one or more processors configured for executing the instructions stored on the computer readable storage medium.

17. The system of claim 16, wherein determining the related phrases of an identified phrase comprises examining a posting list for the identified phrase.

18. The system of claim 16, wherein determining the importance score of an identified phrase in the document is based on a frequency of the related phrases in the document.

19. The system of claim 16, wherein determining an aggregate score for the top phrase comprises summing the scores of the top phrase for each document for which the top phrase is a top phrase.

20. The system of claim 19, wherein the tangible computer readable medium further stores instructions that when executed by one or more of the processors cause the system to weight each summed score based on a location within the document collection of the document to which the summed score corresponds.

21. The system of claim 16, wherein the tangible computer readable medium further stores instructions that when executed by one or more of the processors cause the system to modify the aggregate score by combining it with a previously determined aggregate score.

22. The system of claim 21, wherein the combination of the aggregate score and the previously determined aggregate score is accomplished by a linear combination of the aggregate score and the previously determined aggregate score.

23. A system comprising:

a tangible computer readable medium storing instructions that when executed by one or more processors cause the system to;

receive a user request to change a current top phrase for a limited document collection to a replacement top phrase;

associate the replacement top phrase with a root document of the document collection;

associate the current top phrase and the replacement top phrase with each other;

add to phrase information for the replacement top phrase, phrase information for the current top phrase; and

add to related phrase information of the replacement top phrase, related phrase information of the current top phrase and one or more processors configured for executing the instructions stored on the computer readable storage medium.

24. The system of claim 23, wherein associating the replacement top phrase with the root document of the document collection comprises adding the root document of the document collection to a posting list for the replacement top phrase.

25. The system of claim 23, wherein associating the current top phrase and replacement top phrase with each other comprises:

adding the current top phrase to a related phrase list of the replacement top phrase; and

adding the replacement top phrase to a related phrase list of the current top phrase.

26. The system of claim 23, wherein adding to phrase information for the replacement top phrase, phrase information for the current top phrase, comprises:

determining a count corresponding to a related phrase of the current top phrase that is also a top phrase of the limited document collection;

creating for the replacement top phrase a corresponding copy of the count;

determining each related phrase of the replacement top phrase that is also a top phrase of the limited document collection; and

updating for the replacement top phrase, a count of the determined related phrases based on a number of occurrences of the related phrases.

27. The system of claim 23, wherein adding to related phrase information for the replacement top phrase, related phrase information of the curr ent top phrase, comprises incrementing counts of related phrases of the replacement top phrase that are also related phrases of the current top phrase.

28. The system of claim 23, wherein the tangible computer readable medium further stores instructions that when executed by one or more of the processors cause the system to deny the request to change the current top phrase to the curr ent top phrase, responsive to the current and replacement top phrases having no related phrases in common.

29. The system of claim 23, wherein the tangible computer readable medium further stores instructions that when executed by one or more of the processors cause the system to decrement the counts of the related phrases of the replacement top phrase, responsive to the current and replacement top phrases having no related phrases in common.

30. A tangible computer readable storage medium comprising instructions that when executed by one or more processors cause a computer system to:

determine top phrases for a plurality of documents in a limited document collection, wherein determining the top phrases of a document includes;

identifying phrases in the document;

for each identified phrase in the document, determining an importance score for the identified phrase based on occurrences of related phrases of the identified phrase, which are also in the document;

associate each top phrase with the importance score for the document;

for each top phrase, determine an aggregate score of the top phrase for the limited document collection based on the top phrase'"'"'s scores for individual documents of the limited document collection in which the top phrase appears; and

select a set of top phrases with the highest aggregate scores.

31. The computer readable storage medium of claim 30, wherein determining the related phrases of an identified phrase comprises examining a posting list for the identified phrase.

32. The computer readable storage medium of claim 30, wherein determining the importance score of an identified phrase in the document is based on a frequency of the related phrases in the document.

33. The computer readable storage medium of claim 30, wherein determining an aggregate score for the top phrase comprises summing the scores of the top phrase for each document for which the top phrase is a top phrase.

34. The computer readable storage medium of claim 33, further comprising instructions that when executed by one or more of the processors cause the system to weight each summed score based on a location within the document collection of the document to which the summed score corresponds.

35. The computer readable storage medium of claim 30, further comprising instructions that when executed by one or more of the processors cause the system to modify the aggregate score by combining it with a previously determined aggregate score.

36. The computer readable storage medium of claim 35, wherein the combination of the aggregate score and the previously determined aggregate score is accomplished by a linear combination of the aggregate score and the previously determined aggregate score.

37. A tangible computer readable storage medium comprising instructions that when executed by one or more processors cause a computer system to:

receive a user request to change a current top phrase for a limited document collection to a replacement top phrase;

associate the replacement top phrase with a root document of the document collection;

associate the current top phrase and the replacement top phrase with each other;

add to phrase information for the replacement top phrase, phrase information for the current top phrase; and

add to related phrase information of the replacement top phrase, related phrase information of the current top.

38. The computer readable storage medium of claim 37, wherein associating the replacement top phrase with the root document of the document collection comprises adding the root document of the document collection to a posting list for the replacement top phrase.

39. The computer readable storage medium of claim 37, wherein associating the current top phrase and replacement top phrase with each other comprises:

adding the current top phrase to a related phrase list of the replacement top phrase; and

adding the replacement top phrase to a related phrase list of the current top phrase.

40. The computer readable storage medium of claim 37, wherein adding to phrase information for the replacement top phrase, phrase information for the current top phrase, comprises:

determining a count corresponding to a related phrase of the current top phrase that is also a top phrase of the limited document collection;

creating for the replacement top phrase a corresponding copy of the count;

determining each related phrase of the replacement top phrase that is also a top phrase of the limited document collection; and

updating for the replacement top phrase, a count of the determined related phrases based on a number of occurrences of the related phrases.

41. The computer readable storage medium of claim 37, wherein adding to related phrase information for the replacement top phrase, related phrase information of the current top phrase, comprises incrementing counts of related phrases of the replacement top phrase that are also related phrases of the current top phrase.

42. The computer readable storage medium of claim 37, further comprising instructions that when executed by one or more of the processors cause the system to deny the request to change the current top phrase to the current top phrase, responsive to the current and replacement top phrases having no related phrases in common.

43. The computer readable storage medium of claim 37, further comprising instructions that when executed by one or more of the processors cause the system to decrement the counts of the related phrases of the replacement top phrase, responsive to the current and replacement top phrases having no related phrases in common.