Systems and methods for ranking documents based upon structurally interrelated information

• US 7,739,281 B2
• Filed: 09/16/2003
• Issued: 06/15/2010
• Est. Priority Date: 09/16/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Najork, Marc A.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Hicks; Michael J
• Application Number:
  US10/663,933
• Publication Number:
  US 20050060297A1
• Time in Patent Office: 2,464 Days
• Field of Search: 707/735
• US Class Current: 707/735
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Systems and methods for ranking Web pages based on hyperlink information in a manner that is resistant to nepotistic links are provided. In one embodiment, a Web search service is provided for returning quality query results. The vulnerability of existing ranking algorithms, such as PageRank, to Web pages that are artificially generated for the sole purpose of inflating the score of target page(s) is addressed. Intuitively, it is recognized that it is less likely to reach a particular page on a Web server having many pages via a random jump than it is to reach a particular page on a Web server having few pages, which implies that the influence of such a page upon another page by linking to, or endorsing, the other page is diminished. Thus, in various non-limiting embodiments, each Web server, not each Web page, is assigned a guaranteed minimum score. This minimum score assigned to a server can then be divided among all the pages on that Web server.

Claims

1. In a computing system comprising at least one processor and a memory communicatively coupled to said at least one processor, a method for adjusting a score of a document returned in a list of scored documents responsive to a search engine query, wherein a Web server is assigned a minimum score to be divided among documents hosted on the Web server and said minimum score increases in proportion to a number of structurally linked documents endorsing said document, the method comprising:

identifying, using said computing system, the Web server hosting said document, said Web server defined by at least one of;

(A) a server comprising a plurality of Web pages with the same symbolic host name, (B) a server comprising a plurality of Web pages associated with the same domain, and (C) a server having a plurality of Web pages associated with the same IP address;

determining, on said computing system, an adjustment factor in inverse proportion to a total number of documents hosted on said Web server;

adjusting said score as a function of said adjustment factor, whereby when said number of documents on said Web server increases said score decreases and when said number of documents on said Web server decreases said score increases; and

storing the adjusted score in said memory.

2. The method according to claim 1, further including:

assigning the score to the document in proportion to the number of structurally linked documents endorsing said document.

3. The method according to claim 1, further including:

assigning the score in proportion to at least one score assigned to at least one of said structurally linked documents endorsing said document.

4. The method according to claim 1, further including:

assigning the score in proportion to (A) the number of structurally linked documents endorsing said document and (B) at least one score assigned to at least one of said structurally linked documents endorsing said document.

5. The method according to claim 2, further including:

assigning the score to the document in inverse proportion to the number of outlinks of at least one of said structurally linked documents endorsing said document.

6. The method according to claim 1, wherein said adjusting includes adjusting the score in inverse proportion to the number of documents located on the same domain as said document.

7. The method according to claim 1, wherein said adjusting includes adjusting the score in inverse proportion to the number of documents having the same symbolic host name as said document.

8. The method according to claim 1, wherein said adjusting includes adjusting the score in inverse proportion to the number of documents associated with the same internet protocol (IP) address as said document.

9. The method according to claim 1, further comprising:

adjusting the score based upon summing the scores of the at least one other document linking to said first document.

10. The method according to claim 1, wherein the structurally linked documents are Web pages having hyperlinks and the document is a Web page.

11. The method according to claim 1, further including outputting the adjusted score of the document to a component of a Web search service.

12. The method according to claim 1, further including assigning a set of documents scores higher than an average minimum score.

13. The method according to claim 12, wherein the set of documents is based on at least one of Nielsen ratings, ratings assigned by humans, Web page usage patterns extracted from ISP proxy logs, Web page usage patterns extracted from a search engine and documents specified according to a user preference.

14. The method according to claim 1, further including altering the adjusted score of the document based upon an additional scoring technique to said adjusting the score.

15. The method according to claim 14, further including comparing the adjusted score against said additional scoring technique to discover anomalous results.

16. In a computing system comprising at least one processor and a memory communicatively coupled to said at least one processor, a method for assigning a score to a document of a plurality of structurally linked documents, the document is hosted on a Web server and the Web server is assigned a minimum score to be divided among documents hosted on the Web server and said document is returned in a list of scored documents responsive to a search engine query, the method comprising:

locating said document on the Web server defined by at least one of;

(A) a server comprising a plurality of the Web pages with the same symbolic host name, (B) a server comprising a plurality of Web pages associated with the same domain, and (C) a server having a plurality of Web pages associated with the same IP address, wherein said document has at least one backlink from at least one source document of the plurality of structurally linked documents;

calculating the score of the document in proportion to at least one score associated with at least one of the at least one source document;

calculating the score in inverse proportion to a total number of said at least one source document located on said Web server resulting in said score being divided among said total number of documents, whereby when said number of documents increases said score decreases and when said number of documents decreases said score increases; and

storing the score in said memory.

17. The method according to claim 16, wherein the score is calculated inversely proportional to the number of said at least one source document located on the same Web server.

18. The method according to claim 17, wherein the score is calculated inversely proportional to the number of said at least one source document having the same symbolic host name.

19. The method according to claim 17, wherein the score is calculated inversely proportional to the number of said at least one source document associated with the same domain.

20. The method according to claim 17, wherein the score is calculated inversely proportional to the number of said at least one source document associated with the same internet protocol (IP) address.

21. The method according to claim 16, wherein the plurality of structurally linked documents are Web pages having hyperliniks and the document is a Web page.

22. A computer readable medium storing computer executable instructions for assigning a score to a document of a plurality of structurally linked documents, wherein the document is located on a Web server assigned a minimum score to be divided among documents hosted on the Web server and the document is returned in a list of scored documents responsive to a search engine query, the documents having at least one backlink from at least one other document of the plurality of structurally linked documents, the medium comprising:

instructions for locating said document on the Web server defined by at least one of;

(A) a server comprising a plurality of Web pages with the same symbolic host name, (B) a server comprising a plurality of Web pages associated with the same domain, and (C) a server having a plurality of Web pages associated with the same IP address;

instructions for assigning the score to the document in inverse proportion to a total number of documents located on said Web server resulting in said score being assigned to said document by being distributed among said number of documents, including said document, whereby when said number of documents increases said score assigned to said document decreases and when said number of documents decreases said score assigned to said document increases; and

instructions for storing the score in a memory.

23. The computer readable medium according to claim 22, further including:

instructions for assigning the score to the document in proportion to the number of said at least one other document.

24. The computer readable medium according to claim 22, further including:

instructions for assigning the score in proportion to at least one score assigned to at least one of said at least one other document.

25. The computer readable medium according to claim 22, further including:

instructions for assigning the score in proportion to (A) the number of said at least one other document and (B) at least one score assigned to at least one of said at least one other document.

26. The computer readable medium according to claim 23, further including:

instructions for assigning the score to the document in inverse proportion to the number of outlinks of at least one of said at least one other document.

27. The computer readable medium according to claim 22, wherein said instructions for assigning include instructions for assigning the score to the document in inverse proportion to the number of documents located on a Web server with the same symbolic host name as said document.

28. The computer readable medium according to claim 22, wherein said instructions for assigning include instructions for assigning the score to the document in inverse proportion to the number of documents located on the same domain as said document.

29. The computer readable medium according to claim 22, wherein said instructions for assigning include instructions for assigning the score to the document in inverse proportion to the number of documents associated with the same internet protocol (IP) address as said document.