  Web search engines and specialized online verticals are increasingly
incorporating results from structured data sources to answer semantically rich
user queries. For example, the query \WebQuery{Samsung 50 inch led tv} can be
answered using information from a table of television data. However, the users
are not domain experts and quite often enter values that do not match precisely
the underlying data. Samsung makes 46- or 55- inch led tvs, but not 50-inch
ones. So a literal execution of the above mentioned query will return zero
results. For optimal user experience, a search engine would prefer to return at
least a minimum number of results as close to the original query as possible.
Furthermore, due to typical fast retrieval speeds in web-search, a search
engine query execution is time-bound.
  In this paper, we address these challenges by proposing algorithms that
rewrite the user query in a principled manner, surfacing at least the required
number of results while satisfying the low-latency constraint. We formalize
these requirements and introduce a general formulation of the problem. We show
that under a natural formulation, the problem is NP-Hard to solve optimally,
and present approximation algorithms that produce good rewrites. We empirically
validate our algorithms on large-scale data obtained from a commercial search
engine's shopping vertical.
