Approximating Aggregate Queries about Web Pages via Random Walks
Ziv Bar-Yossef, Alexander Berg, Steve Chien, Jittat Fakcharoenphol, Dror Weitz · 2000
We present a random walk as an eÆcient and accurate approach to approximating cer-tain aggregate queries about web pages. Our method uses a novel random walk to produce an almost uniformly distributed sample of web pages. The walk traverses a dynamically built regular undirected graph. Queries we have es-timated using this method include the cover-age of search engines, the proportion of pages belonging to.com and other domains, and the average size of web pages. Strong experimen-tal evidence suggests that our walk produces accurate results quickly using very limited re-sources. 1