Name
Abstract | ||
|---|---|---|
Processing top-k bag-of-words queries is critical to many information retrieval applications, including web-scale search. In this work, we consider algorithmic properties associated with dynamic pruning mechanisms. Such algorithms maintain a score threshold (the k th highest similarity score identified so far) so that low-scoring documents can be bypassed, allowing fast top-k retrieval with no loss in effectiveness. In standard pruning algorithms the score threshold is initialized to the lowest possible value. To accelerate processing, we make use of term- and query-dependent features to predict the final value of that threshold, and then employ the predicted value right from the commencement of processing. Because of the asymmetry associated with prediction errors (if the estimated threshold is too high the query will need to be re-executed in order to assure the correct answer), the prediction process must be risk-sensitive. We explore techniques for balancing those factors, and provide detailed experimental results that show the practical usefulness of the new approach.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3331184.3331207 | Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval |
Keywords | Field | DocType |
dynamic pruning, inverted index, query efficiency | Inverted index,Data mining,Computer science,Information retrieval applications,Pruning | Conference |
ISBN | Citations | PageRank |
978-1-4503-6172-9 | 2 | 0.36 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias Petri | 1 | 164 | 14.74 |
| Alistair Moffat | 2 | 5913 | 728.91 |
| Joel Mackenzie | 3 | 44 | 10.36 |
| Shane Culpepper | 4 | 519 | 47.52 |
| Daniel Beck | 5 | 103 | 15.12 |