Pruned Query Evaluation Using Pre-Computed Impacts
Vo Ngoc Anh
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Status
Proc. 29th Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval,
Seattle, August 2006, pages 372-379.
Abstract
Exhaustive evaluation of ranked queries can be expensive,
particularly when only a small subset of the overall ranking is
required, or when queries contain common terms.
This concern gives rise to techniques for dynamic query pruning, that
is, methods for eliminating redundant parts of the usual exhaustive
evaluation, yet still generating a demonstrably ``good enough'' set
of answers to the query.
In this work we propose new pruning methods that make use of
impact-sorted indexes.
Compared to exhaustive evaluation, the new methods reduce the amount
of computation performed, reduce the amount of memory required for
accumulators, reduce the amount of data transferred from disk, and at
the same time allow performance guarantees in terms of precision and
mean average precision.
These strong claims are backed by experiments using the TREC Terabyte
collection and queries.
Full text
http://doi.acm.org/10.1145/1148170.1148235.