Decision-theoretic web-crawling and predicting web-page change

• US 7,310,632 B2
• Filed: 02/12/2004
• Issued: 12/18/2007
• Est. Priority Date: 02/12/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Kadie, Carl M.
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Kim; Paul
• Application Number:
  US10/777,365
• Publication Number:
  US 20050192936A1
• Time in Patent Office: 1,405 Days
• Field of Search: 707/3
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Systems and methods are described that facilitate predictive web-crawling in a computer environment. Aspects of the invention provide for predictive, utility-based, and decision theoretic probability assessments of changes in subsets of web pages, enhancing web-crawling ability and ensuring that web page information is maintained in a fresh state. Additionally, the invention facilitates selective crawling of pages with a high probability of change.

Claims

1. A computer implemented system that facilitates web-crawling, comprising at least a processor, one or more memories with following components stored thereon:

a managing component that performs a predictive analysis to predict when a web page will change, and determines when, and how to perform web-crawling;

a server computer component that implements a web-crawling component that crawls subsets of web pages as a function of the predictive analysis, discovers and updates the pages in a catalogue of possible search results; and

a decision-theoretic component that determines an appropriate time to crawl the at least one web page and makes predictions regarding changes in at least one web page based at least in part on;

a probability that a particular outcome will occur, Pr; and

a utility factor associated with each outcome, Utility(O);

an action, a, selected from a set of possible actions, A, to be performed on the at least one web page, which maximizes the value of;

$\underset{o\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{Pr}<br><br>\left(o❘<br><br>a\right)\times <br><br>\mathrm{Utility}<br><br>\left(o\right)$

 

where o is an outcome selected from a set of possible outcomes, O, wherein the outcome o maximizes the efficiency of the web-crawling component in discovering and updating changed web pages.

2. The system of claim 1, the predictive analysis is based at least in part on the utility of the at least one web page.

3. The system of claim 1, the predictive analysis is based at least in part on historical data related to the at least one web page.

4. The system of claim 1, the predictive analysis is based at least in part on content contained in the at least one web page.

5. The system of claim 1, further comprising a bundling component that rearranges crawled web pages into new subsets according to the utility of the web pages.

6. The system of claim 1, the web-crawling component comprises a Round Robin crawling component that sequentially crawls web pages in a subset and ensures that every web page will be crawled within a crawling period, and a Greedy crawling component that non-sequentially crawls pages according to a score associated with each page.

7. A computer readable medium that has computer executable instructions stored thereon to:

predict when a web page will change in order to determine when, and how to perform web-crawling;

crawl subsets of web pages based on the predicting when a web page will change, to catalogue possible web page search results; and

determine an appropriate time to crawl the web page and make predictions regarding changes in at least one web page based at least in part on;

a probability that a particular outcome will occur, Pr; and

a utility factor associated with each outcome, Utility(O);

an action, a, selected from a set of possible actions, A, to be performed on the at least one web page, which maximizes the value of;

$\underset{o\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{Pr}<br><br>\left(o❘<br><br>a\right)\times <br><br>\mathrm{Utility}<br><br>\left(o\right)$

 

where o is an outcome selected from a set of possible outcomes, O, wherein the outcome o maximizes the efficiency of crawling in discovering and updating changed web pages.

8. The computer readable medium of claim 7, the instructions that predict are based at least in part on the utility of the at least one web page.

9. The computer readable medium of claim 7, the instructions that predict are based at least in part on historical data related to the at least one web page.

10. The computer readable medium of claim 7, the instructions that predict are based at least in part on content contained in the at least one web page.

11. The computer readable medium of claim 7, further comprising instructions that rearrange the crawled web pages into new subsets according to the utility of the web pages.

12. The computer readable medium of claim 7, the instructions that crawl comprise instructions that sequentially crawl web pages in a subset within a crawling period, and non-sequentially crawl pages according to a score associated with each page.

13. A computer readable medium having stored thereon components that facilitate web-crawling, the components comprising:

a managing component that performs a predictive analysis to predict when a web page will change, and determines when, and how to perform web-crawling;

a server computer component that implements a web-crawling component that crawls subsets of web pages as a function of the predictive analysis, discovers and updates the pages in a catalogue of possible search results; and

a decision-theoretic component that determines an appropriate time to crawl the at least one web page and makes predictions regarding changes in at least one web page based at least in part on;

a probability that a particular outcome will occur, Pr; and

a utility factor associated with each outcome, Utility(O);

an action, a, selected from a set of possible actions, A, to be performed on the at least one web page, which maximizes the value of;

$\underset{o\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{Pr}<br><br>\left(o❘<br><br>a\right)\times <br><br>\mathrm{Utility}<br><br>\left(o\right)$

 

where o is an outcome selected from a set of possible outcomes, O, wherein the outcome o maximizes the efficiency of the web-crawling component in discovering and updating changed web pages.

14. The medium of claim 13, the predictive analysis is based at least in part on the utility of the at least one web page.

15. The medium of claim 13, the predictive analysis is based at least in part on historical data related to the at least one web page.

16. The medium of claim 13, the predictive analysis is based at least in part on content contained in the at least one web page.

17. The medium of claim 13, further comprising a bundling component that rearranges crawled web pages into new subsets according to the utility of the web pages.

18. The medium of claim 13, the web-crawling component comprises a Round Robin crawling component that sequentially crawls web pages in a subset and ensures that every web page will be crawled within a crawling period, and a Greedy crawling component that non-sequentially crawls pages according to a score associated with each page.