document: The discoverability of the web Previous studies have highlighted the high arrival rate of new contenton the web . We study the extent to which this new content can beefficiently discovered by a crawler . Our study has two parts . First , we study the inherent difficulty of the discovery problem using amaximum cover formulation , under an assumption of perfect estimates oflikely sources of links to new content . Second , we relax thisassumption and study a more realistic setting in which algorithms mustuse historical statistics to estimate which pages are most likely toyield links to new content . We recommend a simple algorithm thatperforms comparably to all approaches we consider . We measure the emphoverhead of discovering new content , defined asthe average number of fetches required to discover one new page . Weshow first that with perfect foreknowledge of where to explore forlinks to new content , it is possible to discover 90 % of all newcontent with under 3 % overhead , and 100 % of new content with 9 % overhead . But actual algorithms , which do not have access to perfectforeknowledge , face a more difficult task : one quarter of new contentis simply not amenable to efficient discovery . Of the remaining threequarters , 80 % of new content during a given week may be discoveredwith 160 % overhead if content is recrawled fully on a monthly basis .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O