Topical query decomposition

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

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In Proc. of EDBT Workshops, pp. 588--596, 2004.
• 3: Sugato Basu , Ian Davidson , Kiri Wagstaff, Constrained Clustering: Advances in Algorithms, Theory, and Applications, Chapman & Hall/CRC, 2008
• 4: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 5: Nicolas J. Belkin, Helping people find what they don't know, Communications of the ACM, v.43 n.8, p.58-61, Aug. 2000 [doi>10.1145/345124.345143]
• 6: 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
• 7: V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4:233--235, 1979.
• 8: Nick Craswell , Onno Zoeter , Michael Taylor , Bill Ramsey, An experimental comparison of click position-bias models, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341545]
• 9: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. of ACM Int. Conf. on Knowledge Discovery and Data Mining (KDD), 1996.
• 10: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 11: Paolo Ferragina , Antonio Gulli, A personalized search engine based on web-snippet hierarchical clustering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062760]
• 12: B. M. Fonseca, P. B. Golgher, E. S. de Moura, B. Pôssas, and N. Ziviani. Discovering search engine related queries using association rules. Journal of Web Engineering, 2(4), 2004.
• 13: Bruno M. Fonseca , Paulo Golgher , Bruno Pôssas , Berthier Ribeiro-Neto , Nivio Ziviani, Concept-based interactive query expansion, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099726]
• 14: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 15: 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]
• 16: 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]
• 17: Krishna Kummamuru , Rohit Lotlikar , Shourya Roy , Karan Singal , Raghu Krishnapuram, A hierarchical monothetic document clustering algorithm for summarization and browsing search results, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988762]
• 18: 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]
• 19: Barbara Poblete , Ricardo Baeza-Yates, Query-sets: using implicit feedback and query patterns to organize web documents, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367504]
• 20: Bruno Pôssas , Nivio Ziviani , Wagner Meira, Jr. , Berthier Ribeiro-Neto, Set-based model: a new approach for information retrieval, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564417]
• 21: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 23: K. Wagstaff, S. Basu, and I. Davidson. When is constrained clustering beneficial, and why? In Proc. of AAAAI'06, 2006.
• 24: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 25: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Clustering user queries of a search engine, Proceedings of the 10th international conference on World Wide Web, p.162-168, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371974]
• 26: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]
• 27: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009030]
• 28: Zhiyong Zhang , Olfa Nasraoui, Mining search engine query logs for query recommendation, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1136004]
• 29: Ying Zhao , George Karypis, Evaluation of hierarchical clustering algorithms for document datasets, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584877]

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:
clustering, query recommendation, set cover