The discoverability of the web

@inproceedings{citeulike:1286300, abstract = {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.}, address = {New York, NY, USA}, author = {Dasgupta, Anirban and Ghosh, Arpita and Kumar, Ravi and Olston, Christopher and Pandey, Sandeep and Tomkins, Andrew }, booktitle = {WWW '07: Proceedings of the 16th international conference on World Wide Web}, citeulike-article-id = {1286300}, doi = {10.1145/1242572.1242630}, isbn = {9781595936547}, keywords = {crawling, dynamic, web}, pages = {421--430}, posted-at = {2007-05-21 16:02:45}, priority = {0}, publisher = {ACM Press}, title = {The discoverability of the web}, url = {http://portal.acm.org/citation.cfm?id=1242572.1242630}, year = {2007} }

TY - CONF ID - citeulike:1286300 L3 - citeulike-article-id:1286300 TI - The discoverability of the web T2 - WWW '07: Proceedings of the 16th international conference on World Wide Web SP - 421 EP - 430 AD - New York, NY, USA PB - ACM Press SN - 9781595936547 N2 - 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. KW - crawling KW - dynamic KW - web AU - Dasgupta, Anirban AU - Ghosh, Arpita AU - Kumar, Ravi AU - Olston, Christopher AU - Pandey, Sandeep AU - Tomkins, Andrew PY - 2007/// UR - http://portal.acm.org/citation.cfm?id=1242572.1242630 ER -