Effectiveness of cooperative resource collecting robots for Web search engines

摘要

In this paper, we consider cooperative resource collecting robots in web space. Especially, we discuss the effectiveness of algorithm to share domains among several robots in the network. We define the cost model for documents retrieval system by the product of the size of document and the distance from each site to each robot. The algorithm to minimize the collecting time resolves itself into multi processor scheduling problem, which is one of famous NP complete problems. Hence, we propose approximation algorithm which is based on greedy method. Consequently, we estimate that the length of collecting time can be reduced from 1/3 to 1/6 to collect almost all web documents in Japan.