  Threshold queries are an important class of queries that only require
computing or counting answers up to a specified threshold value. To the best of
our knowledge, threshold queries have been largely disregarded in the research
literature, which is surprising considering how common they are in practice. In
this paper, we present a deep theoretical analysis of threshold query
evaluation and show that thresholds can be used to significantly improve the
asymptotic bounds of state-of-the-art query evaluation algorithms. We also
empirically show that threshold queries are significant in practice. In
surprising contrast to conventional wisdom, we found important scenarios in
real-world data sets in which users are interested in computing the results of
queries up to a certain threshold, independent of a ranking function that
orders the query results by importance.
