Optimal algorithms for crawling a hidden database in the web

Cheng Sheng, Nan Zhang, Yufei Tao, Xin Jin

Research output: Contribution to journalArticlepeer-review

54 Scopus citations


A hidden database refers to a dataset that an organization makes accessible on the web by allowing users to issue queries through a search interface. In other words, data acquisition from such a source is not by following static hyper-links. Instead, data are obtained by querying the interface, and reading the result page dynamically generated. This, with other facts such as the interface may answer a query only partially, has prevented hidden databases from being crawled effectively by existing search engines. This paper remedies the problem by giving algorithms to extract all the tuples from a hidden database. Our algorithms are provably efficient, namely, they accomplish the task by performing only a small number of queries, even in the worst case. We also establish theoretical results indicating that these algorithms are asymptotically optimal - i.e., it is impossible to improve their efficiency by more than a constant factor. The derivation of our upper and lower bound results reveals significant insight into the characteristics of the underlying problem. Extensive experiments confirm the proposed techniques work very well on all the real datasets examined.

Original languageEnglish (US)
Pages (from-to)1112-1123
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number11
StatePublished - Jul 2012

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Optimal algorithms for crawling a hidden database in the web'. Together they form a unique fingerprint.

Cite this