skip to main content
10.1145/1526709.1526853acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
poster

Query clustering using click-through graph

Published: 20 April 2009 Publication History

Abstract

In this paper we describe a problem of discovering query clusters from a click-through graph of web search logs. The graph consists of a set of web search queries, a set of pages selected for the queries, and a set of directed edges that connects a query node and a page node clicked by a user for the query. The proposed method extracts all maximal bipartite cliques (bicliques) from a click-through graph and compute an equivalence set of queries (i.e., a query cluster) from the maximal bicliques. A cluster of queries is formed from the queries in a biclique. We present a scalable algorithm that enumerates all maximal bicliques from the click-through graph. We have conducted experiments on Yahoo web search queries and the result is promising.

References

[1]
J. J. Carrasco, D. C. Fain, K. J. Lang, and L. Zhukov. Clustering of bipartite advertiser-keywork grdaph. Workshop on Large Scale Clustering, ICDM 2003.
[2]
R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Trawling the web for emerging cyber-communities. The 8th Int. World Wide Web Conference, 1999.
[3]
K. Makino, and T. Uno, New algorithms for enumerating all maximal cliques, The 9th Scandinavian Workshop on Algorithm Theory, 2004.
[4]
E. Tomita, A. Tanaka, and H. Takahashi. The worst--case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1), pp.28--42, 2006.
[5]
J. Wen, J. Nie, H. Zhang. Query clustering using user logs. ACM Transactions on Information Systems, 20(1), pp. 59--31, 2002.

Cited By

View all
  • (2025)Improved binary linear programming models for finding maximum edge Bi-clique in bipartite graphsThe Journal of Supercomputing10.1007/s11227-024-06733-281:1Online publication date: 1-Jan-2025
  • (2019)An Efficient Algorithm for Enumerating Maximal Bicliques from a Dynamically Growing GraphAdvances in Natural Computation, Fuzzy Systems and Knowledge Discovery10.1007/978-3-030-32591-6_35(329-337)Online publication date: 7-Nov-2019
  • (2018)Supervised Search Result Diversification via Subtopic AttentionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.281087330:10(1971-1984)Online publication date: 1-Oct-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WWW '09: Proceedings of the 18th international conference on World wide web
April 2009
1280 pages
ISBN:9781605584874
DOI:10.1145/1526709

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. biclique
  2. click-through graph
  3. equivalence set
  4. maximal bipartite clique
  5. query clustring
  6. query intent

Qualifiers

  • Poster

Conference

WWW '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Improved binary linear programming models for finding maximum edge Bi-clique in bipartite graphsThe Journal of Supercomputing10.1007/s11227-024-06733-281:1Online publication date: 1-Jan-2025
  • (2019)An Efficient Algorithm for Enumerating Maximal Bicliques from a Dynamically Growing GraphAdvances in Natural Computation, Fuzzy Systems and Knowledge Discovery10.1007/978-3-030-32591-6_35(329-337)Online publication date: 7-Nov-2019
  • (2018)Supervised Search Result Diversification via Subtopic AttentionIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.281087330:10(1971-1984)Online publication date: 1-Oct-2018
  • (2018)Finding High Quality Documents through Link and Click Graphs2018 7th International Congress on Advanced Applied Informatics (IIAI-AAI)10.1109/IIAI-AAI.2018.00020(49-54)Online publication date: Jul-2018
  • (2018)Efficient Query Suggestion System using Users Search History2018 International Conference on Information , Communication, Engineering and Technology (ICICET)10.1109/ICICET.2018.8533799(1-6)Online publication date: Aug-2018
  • (2017)Learning to Diversify Search Results via Subtopic AttentionProceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3077136.3080805(545-554)Online publication date: 7-Aug-2017
  • (2017)Enumerating Maximal Bicliques from a Large Graph Using MapReduceIEEE Transactions on Services Computing10.1109/TSC.2016.252399710:5(771-784)Online publication date: 1-Sep-2017
  • (2017)Incorporating Position Bias into Click-Through Bipartite GraphInformation Retrieval10.1007/978-3-319-68699-8_5(57-68)Online publication date: 21-Oct-2017
  • (2016)Accurate and efficient query clustering via top ranked search resultsWeb Intelligence10.3233/WEB-16033514:2(119-138)Online publication date: 25-Apr-2016
  • (2015)Predicting Search Intent Based on Pre-Search ContextProceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/2766462.2767757(503-512)Online publication date: 9-Aug-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media