Time-dependent semantic similarity measure of queries using historical click-through data

ABSTRACT

It has become a promising direction to measure similarity of Web search queries by mining the increasing amount of click-through data logged by Web search engines, which record the interactions between users and the search engines. Most existing approaches employ the click-through data for similarity measure of queries with little consideration of the temporal factor, while the click-through data is often dynamic and contains rich temporal information. In this paper we present a new framework of time-dependent query semantic similarity model on exploiting the temporal characteristics of historical click-through data. The intuition is that more accurate semantic similarity values between queries can be obtained by taking into account the timestamps of the log data. With a set of user-defined calendar schema and calendar patterns, our time-dependent query similarity model is constructed using the marginalized kernel technique, which can exploit both explicit similarity and implicit semantics from the click-through data effectively. Experimental results on a large set of click-through data acquired from a commercial search engine show that our time-dependent query similarity model is more accurate than the existing approaches. Moreover, we observe that our time-dependent query similarity model can, to some extent, reflect real-world semantics such as real-world events that are happening over time.

REFERENCES

• 1: R. Attar , A. S. Fraenkel, Local Feedback in Full-Text Retrieval Systems, Journal of the ACM (JACM), v.24 n.3, p.397-417, July 1977 [doi>10.1145/322017.322021]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: 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]
• 4: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, 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.1009048]
• 5: 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]
• 6: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Probabilistic query expansion using query logs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511489]
• 7: S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41:391--407, 1990.
• 8: T. Heath, E. Motta, and M. Dzbor. Uses of contextual information to support online tasks. In Proceedings of International World Wide Web Conference, pages 1102--1103, 2005.
• 9: Thorsten Joachims, Optimizing search engines using clickthrough data, 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.775067]
• 10: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 11: H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of International Conference on Machine Learning, pages 321--328, 2003.
• 12: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceeding 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]
• 13: Xuehua Shen , Susan Dumais , Eric Horvitz, Analysis of topic dynamics in web search, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062889]
• 14: Jian-Tao Sun , Hua-Jun Zeng , Huan Liu , Yuchang Lu , Zheng Chen, CubeSVD: a novel approach to personalized Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060803]
• 15: K. Tsuda, T. Kin, and K. Asai. Marginalized kernels for biological sequences. Bioinformatics, 18(1):268--275, 2002.
• 16: 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]
• 17: Chuang Wang , Xing Xie , Lee Wang , Yansheng Lu , Wei-Ying Ma, Web resource geographic location classification and detection, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062907]
• 18: L. Wang, C. Wang, X. Xie, J. Forman, Y. Lu, W.-Y. Ma, and Y. Li. Detecting dominant locations from search queries. In International Conference on Machine Learning, pages 321--328, 2003.
• 19: 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]
• 20: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]
• 21: Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Yong Yu , Wei-Ying Ma , WenSi Xi , WeiGuo Fan, Optimizing web search using web click-through data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031192]

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: Clustering; Information filtering

General Terms:
Experimentation, Measurement, Performance

Keywords:
click-through data, event detection, evolution pattern, marginalized kernel, semantic similarity measure