Method and system for calculating document importance using document classifications

• US 20060004809A1
• Filed: 06/30/2004
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun
• Granted Patent: US 7,774,340 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations

Abstract

A system for calculating the importance of web pages is provided. The web pages are organized hierarchically into collections. The system calculates the importance of each collection based on inter-collection links from a web page in one collection to a web page in another collection. The system then calculates the importance of web pages in the collections with a high calculated importance based on links between the web pages in those collections using, for example, a conventional page rank algorithm. The system may also calculate the importance of web pages in each collection with a low calculated importance separately based on the links between the web pages in the collection using, for example, a conventional page rank algorithm.

Claims

1. A method in a computer system for calculating importance of documents, the documents having inter-document links, the method comprising:

providing a hierarchical organization of the documents, the documents being organized into collections;

calculating importance for each collection of documents based on inter-collection links from a document in one collection to a document in another collection;

selecting documents of collections with a high calculated importance; and

calculating the importance of the selected documents based on the inter-document links of the selected documents.

2. The method of claim 1 wherein the documents are web pages and the hierarchical organization is based on domains of the web pages.

3. The method of claim 1 wherein the documents are web pages that are organized by hosts and the hosts are organized by domains and wherein the calculating of the importance for each collection includes calculating importance for the domain collections, selecting domain collections with high importance, and calculating importance of host collections in the selected domain collections.

4. The method of claim 3 wherein the calculating of the importance is performed using a page rank algorithm.

5. The method of claim 1 wherein the calculating of the importance for each collection includes generating an adjacency matrix for the collections with an indication of inter-collection links between each pair of collections.

6. The method of claim 1 wherein the calculating of the importance for the documents includes generating an adjacency matrix for the selected documents with an indication of inter-document links between each pair of the selected documents.

7. The method of claim 1 including for each collection without a high calculated importance, calculating a local importance for documents in that collection based on links between the documents in that collection.

8. The method of claim 7 wherein the calculating of the local importance for documents includes factoring in the calculated importance for the collection that contains the document.

9. The method of claim 1 wherein the calculating of the importance is performed using a ranking algorithm based on links between documents.

10. A computer-readable medium containing instructions for controlling a computer system to calculate the importance of nodes, the nodes having inter-node links, by a method comprising:

for each level of a hierarchical organization of the nodes, calculating importance for selected collections of nodes within the level based on inter-collection links from a node in one collection to a node in another collection, each selected collection being in a higher level collection with a high calculated importance; and

calculating the importance of nodes in the lowest level collections with a high calculated importance based on the inter-node links between the nodes in the lowest level collections with a high calculated importance.

11. The computer-readable medium of claim 10 wherein the nodes are web pages and the hierarchical organization is based on domains of the web pages.

12. The computer-readable medium of claim 10 wherein the nodes are web pages that are organized by domain collections and by host collections in domain collections.

13. The computer-readable medium of claim 12 wherein the calculating of the importance is performed using a page rank algorithm.

14. The computer-readable medium of claim 10 wherein the calculating of the importance for selected collections includes generating an adjacency matrix for the collections with an indication of inter-collection links between each pair of collections.

15. The computer-readable medium of claim 10 wherein the calculating of the importance for the nodes includes generating an adjacency matrix for the nodes with an indication of inter-node links between each pair of the nodes in the lowest level collections with a high calculated importance.

16. The computer-readable medium of claim 10 including for each level of a hierarchical organization of the nodes, calculating a local importance for nodes of a collection without a high calculated importance based on links between the nodes in the collection.

17. The computer-readable medium of claim 16 wherein the calculating of the local importance for the nodes includes factoring in the calculated importance for the collection that contains the node.

18. The computer-readable medium of claim 10 wherein the calculating of the importance is performed using a ranking algorithm based on links between nodes.

19. A computer system for calculating the importance of documents that are hierarchically organized into collections, comprising:

a component that calculates importance for each collection of documents; and

a component that calculates importance of documents in collections with a high calculated importance based on inter-document links of the selected documents.

20. The computer system of claim 19 wherein the calculating of importance for each collection of documents is based on inter-collection links from a document in one collection to a document in another collection.

21. The computer system of claim 19 wherein the documents are web pages and the hierarchical organization is based on domains of the web pages.

22. The computer system of claim 19 wherein the documents are web pages that are organized by hosts and the hosts are organized by domains and wherein the calculating of the importance for each collection includes calculating importance for the domain collections, selecting domain collections with high importance, and calculating importance of host collections in the selected domain collections.

23. The computer system of claim 21 wherein the calculating of the importance is performed using a page rank algorithm.

24. The computer system of claim 19 wherein the component that calculates the importance for each collection generates an adjacency matrix for the collections with an indication of inter-collection links between each pair of collections.

25. The computer system of claim 19 wherein the component that calculates the importance for the documents generates an adjacency matrix for the documents with an indication of inter-document links between each pair of the documents.

26. The computer system of claim 19 including a component that, for each collection without a high calculated importance, calculates a local importance for documents in that collection based on links between the documents in the collection.

27. The computer system of claim 26 wherein the calculating of the local importance for documents includes factoring in the calculated importance for the collection that contains the document.

28. The computer system of claim 19 wherein the calculating of the importance is performed using a ranking algorithm based on links between documents.

29. A computer-readable medium containing instructions for controlling a computer system to generate scores for nodes, the nodes having inter-node links, by a method comprising:

generating a score for collections of the nodes;

for each collection with a low score, generating a score for each node of the collection based on links between nodes in the collection and based on the generated score for the collection; and

for collections with a high score, generating a score for the nodes of the collections based on links between nodes in the collections with a high score.

30. The computer-readable medium of claim 29 wherein the nodes are web pages and the scores are generated using a page rank algorithm.

31. The computer-readable medium of claim 30 wherein the scores for collections are generated based on inter-collection links of the nodes within the collections.

32. The computer-readable medium of claim 31 wherein the collections are hierarchically organized and the generating of a score for collections is performed for each level in the hierarchy with scores for collections at lower levels being generated only for higher level collections with a high importance.

33. The computer-readable medium of claim 32 wherein the generating of a score for nodes of collections with a low score is performed for collections at each level of the hierarchy.

34. The computer-readable medium of claim 30 wherein the collections are domains.

35. The computer-readable medium of claim 30 wherein the collections are hosts.

36. The computer-readable medium of claim 30 including ranking the web pages based on their scores.

37. The computer-readable medium of claim 29 including ranking the nodes based on their scores.