Detecting spam documents in a phrase based information retrieval system

• US 7,603,345 B2
• Filed: 06/28/2006
• Issued: 10/13/2009
• Est. Priority Date: 07/26/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US11/478,330
• Publication Number:
  US 20060294155A1
• Time in Patent Office: 1,203 Days
• Field of Search: 707/3, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

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. A spam document is identified based on the number of related phrases included in a document.

Claims

1. A computer implemented method for identifying spam documents in an information retrieval system, the method comprising:

maintaining a list of phrases in a memory, each phrase associated with a list of related phrases;

determining, for a document that contains a first phrase from the list of phrases, a number of the related phrases related to the first phrase expected to be present in the document;

determining for the document, and for the first phrase in the document, an actual number of related phrases present in the document; and

identifying the document as a spam document by comparing the actual number of related phrases present in the document with the expected number of related phrases,

wherein determining the number of related phrases related to the first phrase expected to be present in the document includes;

traversing an index of a plurality of documents;

for each of the indexed documents;

determining a set of phrases in the indexed document from the list of phrases, and

for each phrase in the set, determining a number of related phrases also in the indexed document; and

determining the expected number of related phrases based on the determined number of related phrases, related to the first phrase, in the indexed documents.

2. The method of claim 1, wherein

determining the expected number of related phrases based on the determined number of related phrases, related to the first phrase, in the indexed documents includes determining the expected number of related phrases as a medium of the determined number of related phrases, related to the first phrase, in the indexed documents.

3. The method of claim 1, wherein identifying the document as a spam document, further comprises:

determining, for a second phrase contained in the document, a number of the related phrases related to a second phrase expected to be present in the document;

determining for the document, and for the second phrase in the document, an actual number of related phrases present in the document;

determining, for a third phrase contained in the document, a number of the related phrases related to a third phrase expected to be present in the document;

determining for the document, and for the third phrase in the document, an actual number of related phrases present in the document; and

identifying the document as a spam document when the actual number of related phrases present in the document for any of the first phrase, the second phrase, or the third phrase exceeds the expected number of related phrases.

4. The method of claim 1, wherein the determination of the number of the related phrases expected to be present in the document is based on a statistical analysis of a plurality of documents that include the first phrase and related phrases, and wherein identifying the document as a spam document, further comprises:

determining a standard deviation of the expected number of related phrases; and

responsive to the actual number of related phrases present in the document exceeds the expected number of related phrases by at least a multiple of a standard deviation of the expected number of related phrases, identifying the document as a spain document.

5. The method of claim 1, wherein identifying the document as a spain document, further comprises:

responsive to the actual number of related phrases present in the document exceeding the expected number of related phrases by at least a multiple of the expected number of related phrases, identifying the document as a spam document.

6. The method of claim 1, wherein identifying the document as a spam document, further comprises:

determining, for a second phrase contained in the document, a number of the related phrases related to a second phrase expected to be present in the document;

determining for the document, and for the second phrase in the document, an actual number of related phrases present in the document;

determining, for a third phrase contained in the document, a number of the related phrases related to a third phrase expected to be present in the document;

determining for the document, and for the third phrase in the document, an actual number of related phrases present in the document;

identifying the document as a spam document where, for each of the first phrase, the second phrase, and the third phrase, the actual number of related phrases present in the document exceeds the expected number of related phrases based on a threshold.

7. The method of claim 1, wherein identifying the document as a spam document, further comprises:

identifying the document as a spam document when the actual number of related phrases present in the document exceeds a predetermined maximum expected number of related phrases.

8. The method of claim 1, wherein identifying the document as a spam document, further comprises:

determining for a document, a first, second, and third most significant phrases present in the document, wherein the first phrase is the most significant phrase;

determining, for the second most significant phrase, a number of the related phrases related to a second most significant phrase expected to be present in the document;

determining, for the third most significant phrase, a number of the related phrases related to a third most significant phrase expected to be present in the document;

for each of the most significant phrases, determining an actual number of related phrases present in the document; and

responsive to the actual number of related phrases exceeding the expected number of related phrases for each of the most significant phases based on a threshold, identifying the document as a spam document with respect to that significant phrase.

9. The method of claim 1, further comprising

adding the identified document to a spam list that includes a list of spam documents.

10. The method of claim 9, further comprising:

receiving a search query;

retrieving a set of documents relevant to the search query, each document having a relevance score;

for each document in the set of documents, determining whether the document has been identified as a spam document;

responsive to a document being identified as a spam document, down weighting the relevance score of the document; and

organizing the set of documents by their relevance scores.

11. The method of claim 8, further comprising:

adding the identified document to spam list that includes a list of spam documents associated with the most significant phrase; and

for each related phrase of the most significant phrase, adding the identified document to a list of spam documents associated with the related phrase.

12. The method of claim 1, further comprising adding the identified document to a spam list of documents based on a result of the comparing indicating that the actual number of related phrases exceeds the expected number of related phrases.

13. The method of claim 1, further comprising:

receiving a search query;

determining a set of documents that match the search query; and

determining a relevance of each document of the set to the search query, wherein the relevance depends on whether or not the document is on the spam list.

14. The method of claim 1, wherein the determination of the number of the related phrases expected to be present in the document is based on a statistical analysis of a plurality of documents that include the phrase and related phrases.

15. The method of claim 1, wherein the document is identified as a spam document based on the comparison of the actual number of related phrases present in the document with the expected number of related phrases indicating that the actual number of related phrases present in the document exceeds the expected number of related phrases.