Tractable near-optimal policies for crawling

Area of Science:

• Computer Science
• Distributed Systems
• Information Retrieval

Background:

• Maintaining local caches of frequently updated web pages is crucial for systems like web crawlers and proxy servers.
• Limited resources necessitate efficient polling and fetching strategies to ensure cached data remains current.
• Previous optimization models for this problem were computationally intractable for larger scales.

Purpose of the Study:

• To develop an efficient and scalable policy for managing local caches of dynamic web pages.
• To find an optimal randomized polling and fetching strategy that maximizes the utility of up-to-date served pages.
• To provide a computationally tractable solution for the web page caching problem.

Main Methods:

• Formulated the problem as an optimization task.
• Derived an exact solution for the optimal randomized policy with a time complexity of O(n).
• Developed a deterministic schedule based on optimal probabilities, computable in linear time.

Main Results:

• The optimal randomized policy for polling and fetching updates can be found exactly in O(n) operations.
• A deterministic schedule derived from optimal probabilities achieves 99% of the optimal utility in experimental settings.
• The proposed policy offers a tractable and highly effective solution for dynamic web page caching.

Conclusions:

• An efficient and exact method for determining optimal web page caching policies has been established.
• The developed deterministic schedule provides a practical and near-optimal solution for real-world applications.
• This research significantly advances the state-of-the-art in managing dynamic web content efficiently.