  Many web databases are "hidden" behind proprietary search interfaces that
enforce the top-$k$ output constraint, i.e., each query returns at most $k$ of
all matching tuples, preferentially selected and returned according to a
proprietary ranking function. In this paper, we initiate research into the
novel problem of skyline discovery over top-$k$ hidden web databases. Since
skyline tuples provide critical insights into the database and include the
top-ranked tuple for every possible ranking function following the monotonic
order of attribute values, skyline discovery from a hidden web database can
enable a wide variety of innovative third-party applications over one or
multiple web databases. Our research in the paper shows that the critical
factor affecting the cost of skyline discovery is the type of search interface
controls provided by the website. As such, we develop efficient algorithms for
three most popular types, i.e., one-ended range, free range and point
predicates, and then combine them to support web databases that feature a
mixture of these types. Rigorous theoretical analysis and extensive real-world
online and offline experiments demonstrate the effectiveness of our proposed
techniques and their superiority over baseline solutions.
