Extracting semantic relations from query logs

ABSTRACT

In this paper we study a large query log of more than twenty million queries with the goal of extracting the semantic relations that are implicitly captured in the actions of users submitting queries and clicking answers. Previous query log analyses were mostly done with just the queries and not the actions that followed after them. We first propose a novel way to represent queries in a vector space based on a graph derived from the query-click bipartite graph. We then analyze the graph produced by our query log, showing that it is less sparse than previous results suggested, and that almost all the measures of these graphs follow power laws, shedding some light on the searching user behavior as well as on the distribution of topics that people want in the Web. The representation we introduce allows to infer interesting semantic relationships between queries. Second, we provide an experimental analysis on the quality of these relations, showing that most of them are relevant. Finally we sketch an application that detects multitopical URLs.

REFERENCES

• 1: R. Baeza-Yates. Applications of web query mining. ECIR'05.
• 2: R. Baeza-Yates, C. Hurtado, and M. Mendoza. Query clustering for boosting web page ranking. AWIC'04,
• 3: R. Baeza-Yates, C. Hurtado, and M. Mendoza. Query recommendation using query logs in a search engine. EDBT Workshops, 2004.
• 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: Ariel Cid , Carlos Hurtado , Marcelo Mendoza, Automatic Maintenance ofWeb Directories using Click-Through Data, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.43, April 03-07, 2006 [doi>10.1109/ICDEW.2006.36]
• 6: S.-L. Chuang and L.-F. Chien. Automatic query taxonomy generation for information retrieval applications. Online Information Review 27(4), 2003.
• 7: Shui-Lung Chuang , Lee-Feng Chien, Enriching web taxonomies through subject categorization of query terms from search engine logs, Decision Support Systems, v.35 n.1, p.113-127, 01 April 2003 [doi>10.1016/S0167-9236(02)00099-4]
• 8: Shui-Lung Chuang , Lee-Feng Chien, Towards Automatic Generation of Query Taxonomy: A Hierarchical Query Clustering Approach, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.75, December 09-12, 2002
• 9: Pu-Jeng Cheng , Ching-Hsiang Tsai , Chen-Ming Hung , Lee-Feng Chien, Query taxonomy generation for web search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183768]
• 10: G. Dupret and M. Mendoza. Automatic Query Recommendation using Click-Through Data. IFIP PPAI'06.
• 11: Larry Fitzpatrick , Mei Dent, Automatic feedback using past queries: social searching?, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.306-313, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 12: 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
• 13: Hsiao-Tieh Pu , Shui-Lung Chuang , Chyan Yang, Subject categorization of query terms for exploring Web users' search interests, Journal of the American Society for Information Science and Technology, v.53 n.8, p.617-630, August 2002 [doi>10.1002/asi.10071]
• 14: Vijay V. Raghavan , Hayri Sever, On the reuse of past optimal queries, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.344-350, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215381]
• 15: Mehran Sahami , Timothy D. Heilman, A web-based kernel function for measuring the similarity of short text snippets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135834]
• 16: James Surowiecki, The Wisdom of Crowds, Anchor, 2005
• 17: 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]
• 18: 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]

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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Experimentation, Measurement

Keywords:
graph mining, query log analysis