Name
Abstract | ||
|---|---|---|
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.14778/1453856.1453930 | PVLDB |
Keywords | Field | DocType |
new retrieval model,latter problem,novel document retrieval model,text search,online search problem,new model,relaxation cost,minimal cost,query processing,local search,particular relaxation cost,document retrieval | Approximation algorithm,Data mining,Query expansion,Computer science,Full text search,Search engine indexing,Theoretical computer science,Search problem,Local search (optimization),Document retrieval,Database,Online search | Journal |
Volume | Issue | ISSN |
1 | 1 | 2150-8097 |
Citations | PageRank | References |
10 | 0.59 | 32 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Fontoura | 1 | 1116 | 61.74 |
| Vanja Josifovski | 2 | 2265 | 148.84 |
| Ravi Kumar | 3 | 13932 | 1642.48 |
| Chris Olston | 4 | 3576 | 316.59 |
| Andrew Tomkins | 5 | 9388 | 1401.23 |
| Sergei Vassilvitskii | 6 | 2750 | 139.31 |