Query suggestions using query-flow graphs

ABSTRACT

The query-flow graph [Boldi et al., CIKM 2008] is an aggregated representation of the latent querying behavior contained in a query log. Intuitively, in the query-flow graph a directed edge from query q_i to query q_j means that the two queries are likely to be part of the same search mission. Any path over the query-flow graph may be seen as a possible search task, whose likelihood is given by the strength of the edges along the path. An edge (q_i, q_j) is also labelled with some information: e.g., the probability that user moves from q_i to q_j, or the type of the transition, for instance, the fact that q_j is a specialization of q_i.

In this paper we propose, and experimentally study, query recommendations based on short random walks on the query-flow graph. Our experiments show that these methods can match in precision, and often improve, recommendations based on query-click graphs, without using users' clicks. Our experiments also show that it is important to consider transition-type labels on edges for having good quality recommendations.

Finally, one feature that we had in mind while devising our methods was that of providing diverse sets of recommendations: the experimentation that we conducted provides encouraging results in this sense.

REFERENCES

• 1: Antonellis, I., Garcia-Molina, H., and Chang, C.-C. Simrank++: Query rewriting through link analysis of the click graph. In Proceedings of VLDB (Dec 2008), pp. 408--421.
• 2: Ricardo Baeza-Yates, Graphs from Search Engine Queries, Proceedings of the 33rd conference on Current Trends in Theory and Practice of Computer Science, January 20-26, 2007, Harrachov, Czech Republic [doi>10.1007/978-3-540-69507-3_1]
• 3: Baeza-yates, R., Hurtado, C., and Mendoza, M. Query recommendation using query logs in search engines. In In International Workshop on Clustering Information over the Web (ClustWeb, in conjunction with EDBT), Creete (2004), Springer, pp. 588--596.
• 4: Ricardo Baeza-Yates , Alessandro Tiberi, Extracting semantic relations from query logs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281204]
• 5: Baeza-Yates, R. A., Hurtado, C. A., and Mendoza, M. Query recommendation using query logs in search engines. In EDBT Workshops (2004), vol. 3268 of LNCS, Springer, pp. 588--596.
• 6: 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]
• 7: Belazzougui, D., Boldi, P., Pagh, R., and Vigna, S. Theory and practise of monotone minimal perfect hashing. In ALENEX 09: Algorithm Engineering and Experimentes (2009), Lecture Notes in Computer Science, Springer--Verlag.
• 8: Paolo Boldi , Francesco Bonchi , Carlos Castillo , Debora Donato , Aristides Gionis , Sebastiano Vigna, The query-flow graph: model and applications, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458163]
• 9: Boldi, P., Bonchi, F., Castillo, C., and Vigna, S. From "dango" to "japanese cakes": Query reformulation models and patterns. Submitted for publication, 2008.
• 10: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 11: Jose Borges , Mark Levene, Evaluating Variable-Length Markov Chain Models for Analysis of User Web Navigation Sessions, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.441-452, April 2007 [doi>10.1109/TKDE.2007.1012]
• 12: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 13: Nick Craswell , Martin Szummer, Random walks on the click graph, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277784]
• 14: Bruno M. Fonseca , Paulo B. Golgher , Edleno S. de Moura , Nivio Ziviani, Using Association Rules to Discover Search Engines Related Queries, Proceedings of the First Conference on Latin American Web Congress, p.66, November 10-12, 2003
• 15: Ariel Fuxman , Panayiotis Tsaparas , Kannan Achan , Rakesh Agrawal, Using the wisdom of the crowds for keyword generation, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367506]
• 16: Stephanie W. Haas , Erika S. Grams, Page and link classifications: connecting diverse resources, Proceedings of the third ACM conference on Digital libraries, p.99-107, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276686]
• 17: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 18: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 19: Rosie Jones , Kristina Lisa Klinkner, Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458176]
• 20: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 21: Mark Levene , George Loizou, A probabilistic approach to navigation in Hypertext, Information Sciences: an International Journal, v.114 n.1-4, p.165-186, March 1999 [doi>10.1016/S0020-0255(98)10055-5]
• 22: Julia Luxenburger , Shady Elbassuoni , Gerhard Weikum, Matching task profiles and user needs in personalized web search, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458175]
• 23: Qiaozhu Mei , Dengyong Zhou , Kenneth Church, Query suggestion using hitting time, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458145]
• 24: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 25: Matthew Richardson, Learning about the world through long-term query logs, ACM Transactions on the Web (TWEB), v.2 n.4, p.1-27, October 2008 [doi>10.1145/1409220.1409224]
• 26: Soo Young Rieh , Hong Xie, Analysis of multiple query reformulations on the web: the interactive information retrieval context, Information Processing and Management: an International Journal, v.42 n.3, p.751-768, May 2006 [doi>10.1016/j.ipm.2005.05.005]
• 27: 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]
• 28: 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]
• 29: Ryen W. White , Mikhail Bilenko , Silviu Cucerzan, Studying the use of popular destinations to enhance web search interaction, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277771]
• 30: Ryen W. White , Mikhail Bilenko , Silviu Cucerzan, Leveraging popular destinations to enhance Web search interaction, ACM Transactions on the Web (TWEB), v.2 n.3, p.1-30, July 2008 [doi>10.1145/1377488.1377490]
• 31: Ryen W. White , Charles L. A. Clarke , Silviu Cucerzan, Comparing query logs and pseudo-relevance feedbackfor web-search query refinement, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277931]
• 32: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance