Breaking the top-k barrier of hidden web databases?

Saravanan Thirumuruganathan, Nan Zhang, Gautam Das

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

4 Scopus citations


A large number of web databases are only accessible through proprietary form-like interfaces which require users to query the system by entering desired values for a few attributes. A key restriction enforced by such an interface is the top-k output constraint - i.e., when there are a large number of matching tuples, only a few (top-k) of them are preferentially selected and returned by the website, often according to a proprietary ranking function. Since most web database owners set k to be a small value, the top-k output constraint prevents many interesting third-party (e.g., mashup) services from being developed over real-world web databases. In this paper we consider the novel problem of "digging deeper" into such web databases. Our main contribution is the meta-algorithm GetNext that can retrieve the next ranked tuple from the hidden web database using only the restrictive interface of a web database without any prior knowledge of its ranking function. This algorithm can then be called iteratively to retrieve as many top ranked tuples as necessary. We develop principled and efficient algorithms that are based on generating and executing multiple reformulated queries and inferring the next ranked tuple from their returned results. We provide theoretical analysis of our algorithms, as well as extensive experimental results over synthetic and real-world databases that illustrate the effectiveness of our techniques.

Original languageEnglish (US)
Title of host publicationICDE 2013 - 29th International Conference on Data Engineering
Number of pages12
StatePublished - 2013
Event29th International Conference on Data Engineering, ICDE 2013 - Brisbane, QLD, Australia
Duration: Apr 8 2013Apr 11 2013

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other29th International Conference on Data Engineering, ICDE 2013
CityBrisbane, QLD

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Breaking the top-k barrier of hidden web databases?'. Together they form a unique fingerprint.

Cite this