Multiple-Goal Search Algorithms and their Application to Web Crawling

The work described in this paper presents a new framework for heuristic search where the task is to collect as many goals as possible within the allocated resources. We show the inadequacy of traditional distance heuristics for this type of tasks and present alternative types of heuristics that are more appropriate for multiple-goal search. In particular we introduce the yield heuristic that estimates the cost and the benefit of exploring a subtree below a search node. We present a learning algorithm for inferring the yield based on search experience. We apply our adaptive and non-adaptive multiplegoal search algorithms to the web crawling problem and show their efficiency.

Authors

• Dmitry Davidov and Shaul Markovitch Technion

Keywords

No keywords are indexed for this paper.