An Algorithmic Treatment of Strong Queries.

A strong query for a target document with respect to an index is the smallest query for which the target document is returned by the index as the top result for the query. The strong query problem was rst studied more than a decade ago in the context of measuring search engine overlap. Despite its simple-to-state nature and its longevity in the eld, this problem has not been suciently addressed in a formal manner. In this paper we provide the rst rigorous treatment of the strong query problem. We show an interesting connection between this problem and the set cover problem, and use it to obtain basic hardness and algorithmic results. Experiments on more than 10K documents show that our proposed algorithm performs much better than the widely-used word frequency-based heuristic. En route, our study suggests that less than four words on average can be sucient to uniquely identify web pages.