skip to main content
10.1145/1458082.1458145acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Query suggestion using hitting time

Published: 26 October 2008 Publication History

Abstract

Generating alternative queries, also known as query suggestion, has long been proved useful to help a user explore and express his information need. In many scenarios, such suggestions can be generated from a large scale graph of queries and other accessory information, such as the clickthrough. However, how to generate suggestions while ensuring their semantic consistency with the original query remains a challenging problem.
In this work, we propose a novel query suggestion algorithm based on ranking queries with the hitting time on a large scale bipartite graph. Without involvement of twisted heuristics or heavy tuning of parameters, this method clearly captures the semantic consistency between the suggested query and the original query. Empirical experiments on a large scale query log of a commercial search engine and a scientific literature collection show that hitting time is effective to generate semantically consistent query suggestions. The proposed algorithm and its variations can successfully boost long tail queries, accommodating personalized query suggestion, as well as finding related authors in research.

References

[1]
E. Agichtein, S. Lawrence, and L. Gravano. Learning search engine specific query transformations for question answering. In Proceedings of the 10th international conference on World Wide Web, pages 169--178, 2001.
[2]
C. Anderson. The Long Tail: Why the Future of Business is Selling Less of More. Hyperion, 2006.
[3]
R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In EDBT Workshops, pages 588--596, 2004.
[4]
D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log. In Proceedings of KDD '00, pages 407--416, 2000.
[5]
S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1-7):107--117, 1998.
[6]
S. Chakrabarti, M. Joshi, and V. Tawde. Enhanced topic distillation using text, markup tags, and hyperlinks. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 208--216, 2001.
[7]
K. Church and B. Thiesson. The wild thing! In Proceedings of the ACL 2005 on Interactive poster and demonstration sessions, pages 93--96, 2005.
[8]
K. W. Church and B. Thiesson. The wild thing goes local. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 901--901, 2007.
[9]
N. Craswell and M. Szummer. Random walks on the click graph. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 239--246, 2007.
[10]
S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of EMNLP 2004, pages 293--300, 2004.
[11]
T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to personalizing pagerank, 2003.
[12]
T. Joachims, L. Granka, B. Pan, H. Hembrooke, and G. Gay. Accurately interpreting clickthrough data as implicit feedback. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 154--161, 2005.
[13]
R. Jones, B. Rey, O. Madani, and W. Greiner. Generating query substitutions. In Proceedings of the 15th international conference on World Wide Web, pages 387--396, 2006.
[14]
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632.
[15]
M. Li, Y. Zhang, M. Zhu, and M. Zhou. Exploring distributional similarity based models for query spelling correction. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, pages 1025--1032, 2006.
[16]
Q. Mei and K. Church. Entropy of search logs: how hard is search? with personalization? with backoff? In Proceedings of the international conference on Web search and web data mining, pages 45--54, 2008.
[17]
F. Radlinski and T. Joachims. Query chains: learning to rank from implicit feedback. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 239--248, 2005.
[18]
F. Radlinski and T. Joachims. Active exploration for learning rankings from clickthrough data. In Proceedings of KDD' 07, pages 570--579, 2007.
[19]
D. Shen, T. Walkery, Z. Zhengy, Q. Yangz, and Y. Li. Personal name classification in web queries. In Proceedings of the international conference on Web search and web data mining, pages 149--158, 2008.
[20]
X. Shen, B. Tan, and C. Zhai. Implicit user modeling for personalized search. In Proceedings of CIKM' 05, pages 824--831, 2005.
[21]
J.-R. Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine. In Proceedings of WWW '01, pages 162--168, 2001.
[22]
R. W. White and G. Marchionini. Examining the effectiveness of real-time query expansion. Inf. Process. Manage., 43(3):685--704, 2007.
[23]
G.-R. Xue, H.-J. Zeng, Z. Chen, Y. Yu, W.-Y. Ma, W. Xi, and W. Fan. Optimizing web search using web click-through data. In Proceedings of CIKM '04, pages 118--126, 2004.
[24]
C. Zhai and J. Lafferty. Model-based feedback in the language modeling approach to information retrieval. In Proceedings of CIKM' 01, pages 403--410, 2001.

Cited By

View all
  • (2024)Study of Random Walk Invariants for Spiro-Ring Network Based on Laplacian MatricesMathematics10.3390/math1209130912:9(1309)Online publication date: 25-Apr-2024
  • (2024)Query Augmentation with Brain SignalsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681658(7561-7570)Online publication date: 28-Oct-2024
  • (2024)Encouraging Exploration in Spotify Search through Query RecommendationsProceedings of the 18th ACM Conference on Recommender Systems10.1145/3640457.3688035(775-777)Online publication date: 8-Oct-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '08: Proceedings of the 17th ACM conference on Information and knowledge management
October 2008
1562 pages
ISBN:9781595939913
DOI:10.1145/1458082
Permission to make digital or hard copies of all or part 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. bipartite graph
  2. hitting time
  3. personalized query suggestion
  4. query suggestion

Qualifiers

  • Research-article

Conference

CIKM08
CIKM08: Conference on Information and Knowledge Management
October 26 - 30, 2008
California, Napa Valley, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)2
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Study of Random Walk Invariants for Spiro-Ring Network Based on Laplacian MatricesMathematics10.3390/math1209130912:9(1309)Online publication date: 25-Apr-2024
  • (2024)Query Augmentation with Brain SignalsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681658(7561-7570)Online publication date: 28-Oct-2024
  • (2024)Encouraging Exploration in Spotify Search through Query RecommendationsProceedings of the 18th ACM Conference on Recommender Systems10.1145/3640457.3688035(775-777)Online publication date: 8-Oct-2024
  • (2024)Knowledge-Augmented Large Language Models for Personalized Contextual Query SuggestionProceedings of the ACM Web Conference 202410.1145/3589334.3645404(3355-3366)Online publication date: 13-May-2024
  • (2024)Efficient Algorithms for Group Hitting Probability Queries on Large GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3349164(1-13)Online publication date: 2024
  • (2023)Exploiting Intent Evolution in E-commercial Query RecommendationProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599821(5162-5173)Online publication date: 6-Aug-2023
  • (2023)Improving Content Retrievability in Search with Controllable Query GenerationProceedings of the ACM Web Conference 202310.1145/3543507.3583261(3182-3192)Online publication date: 30-Apr-2023
  • (2023)Bootstrapping Query Suggestions in Spotify's Instant Search SystemProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591827(3230-3234)Online publication date: 19-Jul-2023
  • (2023)trie-nlg: trie context augmentation to improve personalized query auto-completion for short and unseen prefixesData Mining and Knowledge Discovery10.1007/s10618-023-00966-037:6(2306-2329)Online publication date: 7-Aug-2023
  • (2023)Mean Hitting Time of Q-subdivision Complex NetworksComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_28(359-370)Online publication date: 26-Jan-2023
  • 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

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media