Ranking documents

• US 8,244,722 B1
• Filed: 01/05/2010
• Issued: 08/14/2012
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Koningstein, Ross
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US12/652,563
• Time in Patent Office: 952 Days
• Field of Search: 707/711, 707/722, 707/723, 707/748
• US Class Current: 707/723
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system determines a first rank associated with a document and determines a second rank associated with the document, where the second rank is different from the first rank. The system also changes, during a transition period that occurs during a transition from the first rank to the second rank, a transition rank associated with the document based on a rank transition function that varies the transition rank over time without any change in ranking factors associated with the document.

Claims

1. A method comprising:

computing, by a processor, a first rank corresponding to a rank for a document at a first time;

detecting, by the processor, a change in one or more ranking factors associated with the document during a transition period between the first time and a subsequent second time;

computing, by the processor and based on the detected change in the one or more ranking factors associated with the document, a second rank corresponding to the rank for the document at the second time;

selecting, by the processor, a rank transition function, from a plurality of rank transition functions, that corresponds to how the rank, for the document, changes from the first rank to the second rank over the transition period;

calculating, by the processor and based on the selected rank transition function, a plurality of transition ranks that correspond, respectively, to the rank for the document during a plurality of different times in the transition period;

estimating, by the processor and based on the plurality of transition ranks and the detected change in the one or more ranking factors, changes to the one or more ranking factors during the plurality of different times in the transition period;

identifying, by the processor and based on the estimated changes in the one or more ranking factors, an indication of rank-manipulation during the transition period; and

reducing, by the processor, the rank of the document at a third time that is subsequent to the first time and the second time, based on the indication of rank-manipulation.

2. The method of claim 1, where reducing the rank of the document comprises:

reducing based on the indication of rank-manipulation, a ranking value for at least one of;

a site associated with the document, a domain associated with the document, a link associated with the document, or a linking document associated with the document.

3. The method of claim 1, where selecting the rank transition function includes:

identifying one of the plurality of rank transition functions to use to determine a ranking score for at least one of;

the document, or

another document that shares a trait of the document, where the other document includes at least one of;

a first document associated with a domain corresponding to the document,

a second document associated with a site corresponding to the document, or

a third document hosted by a server associated with the document.

4. The method of claim 1, where selecting a rank transition function includes:

randomly selecting one of the plurality of rank transition functions.

5. The method of claim 1, where calculating the plurality of transition ranks includes:

causing the rank for the document to transition, at a particular rate, from the first rank to the second rank during the transition period.

6. The method of claim 1, where calculating the plurality of transition ranks includes:

causing the rank, for the document, to initially move in a direction, with regard to the first rank and the second rank, before moving in an opposite direction with regard to the first rank and second rank during the transition period.

7. The method of claim 6, where calculating the plurality of transition ranks includes:

causing the rank, for the document, to decrease and to increase during the transition period.

8. The method of claim 1, where identifying the indication of rank-manipulation during the transition period further includes:

publishing, during the transition period, one or more of the plurality of transition ranks;

detecting one or more additional transition ranks for the document during the during the transition period;

determining a relationship between the published one or more transition ranks and the detected one or more additional transition ranks;

identifying the indication of rank-manipulation further based on the determined relationship.

9. A method comprising:

storing, by a processor associated with a search engine, a first rank associated with a document;

computing, by the processor, a second rank associated with the document, where the second rank is different from the first rank;

changing, by the processor and during a transition period that occurs during a transition from the first rank to the second rank, a transition rank associated with the document based on a rank transition function that varies the transition rank over time;

observing, by the processor and during the transition period, changes to one or more ranking factors associated with the document;

comparing, by the processor, the changing transition rank to the changes in the one or more ranking factors associated with the document;

detecting, by the processor and based on comparing the changing transition rank to the changes in the one or more ranking factors associated with the document, an indication of rank-manipulation of the document during the transition; and

adjusting, by the processor, a ranking of document based on detecting the indication of the rank-manipulation.

10. The method of claim 9, where the transition period lasts a plurality of days.

11. The method of claim 9, where computing the second rank occurs in response to detecting the changes in the one or more ranking factors associated with the document.

12. The method of claim 9, further comprising:

selecting the rank transition function from a plurality of rank transition functions, where changing the transition rank is based on the selected rank transition function.

13. The method of claim 12, where selecting a rank transition function includes:

identifying one of the plurality of the rank transition functions to use to determine a ranking for at least one of;

documents associated with a domain associated with the document,

documents associated with a site associated with the document,

documents hosted by a same server associated with the document, or

documents sharing a similar trait associated with the document.

14. The method of claim 12, where selecting a rank transition function includes:

randomly selecting one of the plurality of rank transition functions.

15. The method of claim 9, where the rank transition function causes the transition rank to transition, at a particular rate, from the first rank to the second rank during the transition period.

16. The method of claim 9, where the rank transition function causes the transition rank to initially move in a first direction with regard to the first rank before moving in a second direction with regard to the first rank during the transition period, where the first direction is different from the second direction.

17. The method of claim 9, where the rank transition function causes the transition rank to initially decrease and to increase, after the decrease, during the transition period.

18. The method of claim 9, further comprising:

publishing a plurality of changes in the transition rank during the transition period;

detecting a plurality of additional changes in the transition rank; and

determining a relationship between the published plurality of changes and the detected plurality of additional changes.

19. The method of claim 9, where detecting the indication of rank-manipulation further includes:

injecting noise into the rank transition function during the transition period;

detecting additional changes to the one or more ranking factors after injecting of the noise; and

detecting the indication of rank-manipulation based on the detected additional changes.

20. A device, comprising:

a memory to store a first rank associated with a document; and

a processor to;

retrieve the first rank;

dynamically compute a second rank associated with the document;

select a rank transition function that represents a transition, over a period of time, from the first rank to the second rank;

compute, based on the rank transition function, a sequence including a plurality of transition ranks over the period of the time;

detect, during the period of time, changes to one or more ranking factors associated with the document;

compare the sequence to the detected changes to the one or more ranking factors;

identify a signal of rank-modifying spam based on comparing the sequence to the detected changes to the one or more ranking factors;

determine whether the signal of rank-modifying spam satisfies a threshold associated with a positive identification of the rank-modifying spamming; and

reduce, when the signal of rank-modifying spam satisfies the threshold, a rank score associated with the document.

21. The device of claim 20, where the processor is further to:

inject, when the signal of rank-modifying spam does not satisfy the threshold, noise into the rank transition function during the period of time;

detect one or more additional changes to one or more ranking factors associated with the document, the one or more additional changes occurring after injection of the noise; and

update the signal of rank-modifying spam based on the detected one or more additional changes.

22. The device of claim 21, where the processor is further to:

adjust, when the signal of rank-modifying spam does not satisfy the threshold, the rank of the document;

detect an additional change to one or more ranking factors, associated with the document, the additional changes occurring after adjustment of the rank of the document and

update the signal of rank-modifying spam based on the detected additional change.

23. The device of claim 20, where the processor, when reducing the ranking score associated with the document, is further to:

assign a negative ranking score to the document.

24. A non-transitory computer-readable memory device comprising:

one or more instructions which, when executed by one or more devices, cause the one or more devices to detect a change in a ranking factor associated with a document, where the change causes a rank, for the document, to transition from a first rank to a second rank;

one or more instructions which, when executed by the one or more devices, cause the one or more devices to identify a rank transition function, where the rank transition function defines how an estimated rank, for the document, changes from the first rank to the second rank over a transition period associated with the transition from first rank to the second rank;

one or more instructions which, when executed by the one or more devices, cause the one or more devices to calculate, based on the rank transition function, a sequence of estimated ranks, associated with the document, during the transition period, and

one or more instructions which, when executed by the one or more devices, cause the one or more devices to compare the detected change in the ranking factor to the sequence of estimated ranks, associated with the document, during the transition period;

one or more instructions which, when executed by the one or more devices, cause the one or more devices to designate the document as being subjected to rank-modifying spam based on a comparison of the detected change and the sequence of estimated ranks; and

one or more instructions which, when executed by the one or more devices, cause the one or more devices to reduce the rank for the document in response to designating the document as being subjected to the rank-modifying spam.

25. The non transitory computer-readable memory device of claim 24, where at least one of the estimated ranks, in the sequence of estimated ranks, is less than the first rank and less than the second rank.

26. The non transitory computer-readable memory device of claim 24, where at least one of the estimated ranks, in the sequence of estimated ranks, is greater than the first rank and greater than the second rank.

27. The non transitory computer-readable memory device of claim 24, where the rank transition function causes each of the estimated ranks, in the sequence, to change by less than a particular amount, from a previous one of the estimated ranks, in the sequence.

28. The non transitory computer-readable memory device of claim 24, where the rank transition function causes the sequence of estimated ranks to include:

a first estimated rank that is below the first rank, and

a second estimated rank, subsequent in the series after the first estimated rank, that is between the first rank and the second rank.

29. The non transitory computer-readable memory device of claim 24, further comprising:

one or more instructions to inject noise into the identified rank transition function during the transition period;

one or more instructions to detect additional changes to the ranking factor, the one or more additional changes occurring after injection of the noise; and

one or more instructions to designate the document as being subjected to rank-modifying spam based spam further based on the detected additional changes.