Name
Abstract | ||
|---|---|---|
In this paper we introduce the problem of query covering as a means to efficiently cache query results. The general idea is to populate the cache with documents that contribute to the result pages of a large number of queries, as opposed to caching the top documents for each query. It turns out that the problem is hard and solving it requires knowledge of the structure of the queries and the results space, as well as knowledge of the input query distribution. We formulate the problem under the framework of stochastic optimization; theoretically it can be seen as a stochastic universal version of set multicover. While the problem is NP-hard to be solved exactly, we show that for any distribution it can be approximated using a simple greedy approach. Our theoretical findings are complemented by experimental activity on real datasets, showing the feasibility and potential interest of query-covering approaches in practice. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1935826.1935923 | Web Search and Data Mining |
Keywords | Field | DocType |
stochastic optimization,experimental activity,input query distribution,query covering,results space,stochastic universal version,stochastic query,query-covering approach,cache query result,potential interest,large number,stochastic analysis,general idea,caching | Query optimization,Data mining,Stochastic optimization,Information retrieval,Query expansion,Computer science,Sargable,Web query classification,Theoretical computer science,Ranking (information retrieval),Spatial query,Boolean conjunctive query | Conference |
Citations | PageRank | References |
6 | 0.42 | 21 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aris Anagnostopoulos | 1 | 1054 | 67.08 |
| Luca Becchetti | 2 | 945 | 55.75 |
| Stefano Leonardi | 3 | 411 | 28.87 |
| Ida Mele | 4 | 73 | 10.95 |
| Piotr Sankowski | 5 | 596 | 47.95 |