Optimising topical query decomposition
Source:
Workshop on Web Search Click Data, ACM, Barcelona, Spain, p.43-47 (2009)
URL:
http://doi.acm.org/10.1145/1507509.1507516
Abstract:
Topical query decomposition (TQD) is a paradigm recently introduced, which, given a query, returns to the user a set of queries that cover the answer set of the original query. The TQD problem was studied as a variant of the set-cover problem and solved by means of a greedy algorithm.
This paper aims to strengthen the original formulation by introducing a new global objective function, and thus formalising the problem as a combinatorial optimisation one. Such a reformulation defines a common framework allowing a formal evaluation and comparison of different approaches to TQD. We apply simulated annealing, a sub-optimal meta-heuristic, to the problem of topical query decomposition and we show, through a large experimentation on a data sample extracted from an actual query log, that such meta-heuristic achieves better results than the greedy algorithm.
Download:
ACM COPYRIGHT NOTICE. Copyright © 2009 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or
permissions@acm.org.
