Inferring semantic query relations from collective user behavior

ABSTRACT

In this paper we describe how high quality transaction data comprising of online searching, product viewing, and product buying activity of a large online community can be used to infer semantic relationships between queries. We work with a large scale query log consisting of around 115 million queries from eBay. We discuss various techniques to infer semantic relationships among queries and show how the results from these methods can be combined to measure the strength and depict the kinds of relationships. Further, we show how this extraction of relations can be used to improve search relevance, related query recommendations, and recovery from null results in an eCommerce context.

REFERENCES

• 1: Metzler D., Dumais S. and Meek C. Similarity measures for short segments of text. Advances in Information Retrieval (2007), pp. 16--27.
• 2: 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]
• 3: Gabrilovich E. and Markovitch S. Computing semantic relatedness using Wikipedia--based explicit semantic analysis. In proceedings of the Twentieth International Joint Conference for Artificial Intelligence, pages 1601--1611, Hyderabad, India, 2007.
• 4: 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]
• 5: 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]
• 6: Measuring semantic similarity between words using web search engines, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242675]
• 7: Ben Carterette , Rosie Jones , Wiley Greiner , Cory Barr, N semantic classes are harder than two, Proceedings of the COLING/ACL on Main conference poster sessions, p.49-56, July 17-18, 2006, Sydney, Australia
• 8: Xiaodong Shi , Christopher C. Yang, Mining related queries from search engine query logs, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135956]
• 9: Silverstein R., Helzinger M., Marais H. and Moricz M. Analysis of a very large AltaVista query log. SRC Technical Note, 1998--014, October 26, 1998.
• 10: Cucerzan S. and Brill E. Extracting semantically related queries by exploiting user session information. Technical Report, Microsoft Research, 2005.
• 11: Steve Chien , Nicole Immorlica, Semantic similarity between search engine queries using temporal correlation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060752]
• 12: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 13: Gupta R. Query representation in a space defined by item features. Technical Report, eBay Research Labs, 2007.
• 14: Rudi L. Cilibrasi , Paul M. B. Vitanyi, The Google Similarity Distance, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.370-383, March 2007 [doi>10.1109/TKDE.2007.48]
• 15: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 16: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 17: Hui Fang , Tao Tao , ChengXiang Zhai, A formal study of information retrieval heuristics, 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.1009004]
• 18: Bruno M. Fonseca , Paulo Golgher , Bruno Pôssas , Berthier Ribeiro-Neto , Nivio Ziviani, Concept-based interactive query expansion, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099726]
• 19: Landauer T., Foltz P. and Laham D. Introduction to Latent Semantic Analysis, Discourse Processes, 25, 259--284 (1998).

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
graph mining, query log mining, semantic query networks, semantic relatedness