document: Sampling search-engine results We consider the problem of efficiently sampling Web search engine query results . In turn , using a small random sample instead of the full set of results leads to efficient approximate algorithms for several applications , such as : Determining the set of categories in a given taxonomy spanned by the search results ; Finding the range of metadata values associated to the result set in order to enable `` multi-faceted search ; '' Estimating the size of the result set ; Data mining associations to the query terms . We present and analyze an efficient algorithm for obtaining uniform random samples applicable to any search engine based on posting lists and document-at-a-time evaluation . ( To our knowledge , all popular Web search engines , e.g. Google , Inktomi , AltaVista , AllTheWeb , belong to this class . ) Furthermore , our algorithm can be modified to follow the modern object-oriented approach whereby posting lists are viewed as streams equipped with a next method , and the next method for Boolean and other complex queries is built from the next method for primitive terms . In our case we show how to construct a basic next ( p ) method that samples term posting lists with probability p , and show how to construct next ( p ) methods for Boolean operators ( AND , OR , WAND ) from primitive methods . Finally , we test the efficiency and quality of our approach on both synthetic and real-world data .
doc_bio_tags: B 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 B I 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