Optimising topical query decomposition

ABSTRACT

Topical query decomposition (TQD) is a paradigm recently introduced in [1], 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.

REFERENCES

• 1: Francesco Bonchi , Carlos Castillo , Debora Donato , Aristides Gionis, Topical query decomposition, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401902]
• 2: Robert D. Carr , Srinivas Doddi , Goran Konjevod , Madhav Marathe, On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.345-353, January 09-11, 2000, San Francisco, California, United States
• 3: V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4:233--235, 1979.
• 4: Bernard J. Jansen , Amanda Spink, How are we searching the world wide web?: a comparison of nine search engine transaction logs, Information Processing and Management: an International Journal, v.42 n.1, p.248-263, January 2006 [doi>10.1016/j.ipm.2004.10.007]
• 5: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 6: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, May 1983.
• 7: David Peleg, Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems, Journal of Discrete Algorithms, v.5 n.1, p.55-64, March, 2007 [doi>10.1016/j.jda.2006.03.008]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Algorithms

Keywords:
objective function, query decomposition, query logs, query recommendation, simulated annealing