Measuring index quality using random walks on the Web

Recent research has studied how to measure the of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the of the pages in a search engine index. We provide a simple, effective algorithm for approximating the quality of an index by performing a random walk on the Web, and we use this methodology to compare the index quality of several major search engines.