2008 TopicalQueryDecomposition

• (Bonchi et al., 2008) ⇒ Francesco Bonchi, Carlos Castillo, Debora Donato, and Aristides Gionis. (2008). “Topical Query Decomposition.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401902

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Topical+query+decomposition%22+2008
• http://portal.acm.org/citation.cfm?doid=1401890.1401902&preflayout=flat#citedby

Quotes

Abstract

We introduce the problem of query decomposition, where we are given a query and a document retrieval system, and we want to produce a small set of queries whose union of resulting documents corresponds approximately to that of the original query. Ideally, these queries should represent coherent, conceptually well-separated topics.

We provide an abstract formulation of the query decomposition problem, and we tackle it from two different perspectives. We first show how the problem can be instantiated as a specific variant of a set cover problem, for which we provide an efficient greedy algorithm. Next, we show how the same problem can be seen as a constrained clustering problem, with a very particular kind of constraint, i.e., clustering with predefined clusters. We develop a two-phase algorithm based on hierarchical agglomerative clustering followed by dynamic programming. Our experiments, conducted on a set of actual queries in a Web scale search engine, confirm the effectiveness of the proposed solutions.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 TopicalQueryDecomposition	Francesco Bonchi Aristides Gionis Carlos Castillo Debora Donato			Topical Query Decomposition				10.1145/1401890.1401902