In this abstract, we analyze the characteristics of difficult queries over databases and propose a novel method to detect such queries. We propose the Structured Robustness (SR) score, which measures the difficulty of a query based on the differences between the rankings of the same query over the original and noisy (corrupted) versions of the same database, where the noise spans on both the content and the structure of the result entities. We take advantage of the structure of the data to gain insight about the degree of the difficulty of a query given the database. We have implemented some of the most popular and representative algorithms for keyword search on databases and used them to evaluate our techniques on the INEX benchmarks. The results show that our method predicts the degree of the difficulty of a query efficiently and effectively.
You are here: / / A NOVEL FRAMEWORK TO MEASURE THE DEGREE OF DIFFICULTY FOR A KEYWORD QUERY OVER A DATABASE