The query-flow graph: model and applications

ABSTRACT

Query logs record the queries and the actions of the users of search engines, and as such they contain valuable information about the interests, the preferences, and the behavior of the users, as well as their implicit feedback to search engine results. Mining the wealth of information available in the query logs has many important applications including query-log analysis, user profiling and personalization, advertising, query recommendation, and more.

In this paper we introduce the query-flow graph, a graph representation of the interesting knowledge about latent querying behavior. 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 searching behavior, whose likelihood is given by the strength of the edges along the path.

The query-flow graph is an outcome of query-log mining and, at the same time, a useful tool for it. We propose a methodology that builds such a graph by mining time and textual information as well as aggregating queries from different users. Using this approach we build a real-world query-flow graph from a large-scale query log and we demonstrate its utility in concrete applications, namely, finding logical sessions, and query recommendation. We believe, however, that the usefulness of the query-flow graph goes beyond these two applications.

REFERENCES

• 1: 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]
• 2: 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]
• 3: R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In EDBT Workshops, volume 3268 of LNCS, pages 588--596. Springer, 2004.
• 4: Monica Bianchini , Marco Gori , Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.92-128, February 2005 [doi>10.1145/1052934.1052938]
• 5: P. Boldi, V. Lonati, M. Santini, and S. Vigna. Graph fibrations, graph isomorphism, and PageRank. RAIRO Inform. Théor., 40:227--253, 2006.
• 6: 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]
• 7: Lara D. Catledge , James E. Pitkow, Characterizing browsing strategies in the World-Wide Web, Proceedings of the Third International World-Wide Web conference on Technology, tools and applications, p.1065-1073, April 1995, Darmstadt, Germany
• 8: Kevyn Collins-Thompson , Jamie Callan, Query expansion using random walk models, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099727]
• 9: 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]
• 10: K. Csalogány, D. Fogaras, B. Rácz, and T. Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Math., 2(3):333--358, 2005.
• 11: 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
• 12: D. He and A. Göker. Detecting session boundaries from web user logs. In Proceedings of the BCS-IRSG 22nd annual colloquium on information retrieval research, pages 57--66, Cambridge, UK, 2000.
• 13: Daqing He , Ayse Göker , David J. Harper, Combining evidence for automatic web session identification, Information Processing and Management: an International Journal, v.38 n.5, p.727-742, September 2002 [doi>10.1016/S0306-4573(01)00060-7]
• 14: Rosie Jones , Fernando Diaz, Temporal profiles of queries, ACM Transactions on Information Systems (TOIS), v.25 n.3, p.14-es, July 2007 [doi>10.1145/1247715.1247720]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: Benjamin Piwowarski , Hugo Zaragoza, Predictive user click models based on click-through history, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321467]
• 19: 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]
• 20: W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66:622--626, 1971.
• 21: Jaime Teevan , Eytan Adar , Rosie Jones , Michael A. S. Potts, Information re-retrieval: repeat queries in Yahoo's logs, 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.1277770]
• 22: 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]
• 23: 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.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:
query flow graph, query recommendation, session segmentation