Mining a search engine's corpus: Efficient yet unbiased sampling and aggregate estimation

Mingyang Zhang, Nan Zhang, Gautam Das

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


Search engines over document corpora typically provide keyword-search interfaces. Examples include search engines over the web as well as those over enterprise and government websites. The corpus of such a search engine forms a rich source of information of analytical interest to third parties, but the only available access is by issuing search queries through its interface. To support data analytics over a search engine's corpus, one needs to address two main problems, the sampling of documents (for offline analytics) and the direct (online) estimation of aggregates, while issuing a small number of queries through the keyword-search interface. Existing work on sampling produces samples with unknown bias and may incur an extremely high query cost. Existing aggregate estimation technique suffers from a similar problem, as the estimation error and query cost can both be large for certain aggregates. We propose novel techniques which produce unbiased samples as well as unbiased aggregate estimates with small variances while incurring a query cost an order of magnitude smaller than the existing techniques. We present theoretical analysis and extensive experiments to illustrate the effectiveness of our approach.

Original languageEnglish (US)
Title of host publicationProceedings of SIGMOD 2011 and PODS 2011
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781450306614
StatePublished - 2011
Event2011 ACM SIGMOD and 30th PODS 2011 Conference - Athens, Greece
Duration: Jun 12 2011Jun 16 2011

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2011 ACM SIGMOD and 30th PODS 2011 Conference

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'Mining a search engine's corpus: Efficient yet unbiased sampling and aggregate estimation'. Together they form a unique fingerprint.

Cite this