When video search goes wrong: predicting query failure using search engine logs and visual search results

ABSTRACT

The recent increase in the volume and variety of video content available online presents growing challenges for video search. Users face increased difficulty in formulating effective queries and search engines must deploy highly effective algorithms to provide relevant results. Although lately much effort has been invested in optimizing video search engine results, relatively little attention has been given to predicting for which queries results optimization is most useful, i.e., predicting which queries will fail. Being able to predict when a video search query would fail is likely to make the video search result optimization more efficient and effective, improve the search experience for the user by providing support in the query formulation process and in this way boost the development of video search engines in general. While insight about a query's performance in general could be obtained using the well-known concept of query performance prediction (QPP), we propose a novel approach for predicting a failure of a video search query in the specific context of a search session. Our 'context-aware query failure' prediction approach uses a combination of 'user indicators' and 'engine indicators' to predict whether a particular query is likely to fail in the context of a particular search session. User indicators are derived from the search log and capture the patterns of query (re)formulation behavior and the click-through data of a user during a typical video search session. Engine indicators are derived from the video search results list and capture the visual variance of search results that would be offered to the user for the given query. We validate our approach experimentally on a test set containing 1+ million video search queries and show its effectiveness compared to a set of conventional QPP baselines. Our approach achieves a 13% relative improvement over the baseline.

References

1. Bosch, A., Zisserman, A. and Muoz, X. Image Classification using Random Forests and Ferns. 2007.
2. Cronen-Townsend, S., Zhou, Y. and Croft, W. B. Predicting query performance. In SIGIR (2002). ACM, 299--306.
3. Fox, S., Karnawat, K., Mydland, M., Dumais, S. and White, T. Evaluating implicit measures to improve web search. ACM Trans. Inf. Syst., 23, 2, 2005, 147--168.
4. Guo, Q., White, R. W., Dumais, S. T., Wang, J. and Anderson, B. Predicting query performance using query, result, and user inter-action features. In Adaptivity, Personalization and Fusion of Heterogeneous Information (2010), 198--201.
5. Guo, Q., White, R. W., Zhang, Y., Anderson, B. and Dumais, S. T. Why searchers switch: understanding and predicting engine switching rationales. In SIGIR (2011). ACM, 335--344.
6. Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P. and Witten, I. H. The WEKA data mining software: an update. SIGKDD Explor. Newsl., 11, 1, 2009, 10--18.
7. He, B. and Ounis, I. Inferring Query Performance Using Pre-retrieval Predictors. 2004.
8. Hollink, V. and Vries, A. d. Towards an automated query modification assistant. ACM, 2011.
9. Hsu, W. H., Kennedy, L. S. and Chang, S.-F. Reranking Methods for Visual Search. IEEE MultiMedia, 14, 3, 2007, 14--22.
10. Huang, J. and Efthimiadis, E. N. Analyzing and evaluating query reformulation strategies in web search logs. In CIKM (2009). ACM, 77--86.
11. Imran, H. and Sharan, A. Co-occurrence based predictors for estimating query difficulty. In International Conference on Data Mining Workshops (2010). IEEE Computer Society, 867--874.
12. Jansen, B. J. Search log analysis: What it is, what's been done, how to do it. Library & Information Science Research, 28, 3, 2006, 407--432.
13. Jansen, B. J., Booth, D. L. and Spink, A. Patterns of query reformulation during Web searching. J. Am. Soc. Inf. Sci. Technol., 60, 7, 2009, 1358--1371.
14. Jansen, B. J., Spink, A. and Pedersen, J. The effect of specialized multimedia collections on web searching. J. Web Eng., 3, 3, 2004, 182--199.
15. Joachims, T. Optimizing search engines using clickthrough data. In SIGKDD (2002). ACM, 133--142.
16. Kim, J. and Can, A. Characterizing Queries in Different Search Tasks. In Hawaii International Conference on System Sciences (2012). IEEE Computer Society, 1697--1706.
17. Kofler, C., Larson, M. and Hanjalic, A. To seek, perchance to fail: expressions of user needs in internet video search. In ECIR (2011). Springer-Verlag, 611--616.
18. Kotov, A., Bennett, P. N., White, R. W., Dumais, S. T. and Teevan, J. Modeling and analysis of cross-session search tasks. In SIGIR (2011). ACM, 5--14.
19. Leuken, R. H. v., Garcia, L., Olivares, X. and Zwol, R. v. Visual diversification of image search results. In WWW (2009). ACM, 341--350.
20. Lux, M. and Chatzichristofis, S. A. Lire: lucene image retrieval: an extensible java CBIR library. In MM (2008). ACM, 1085--1088.
21. Mastora, A., Kapidakis, S. and Monopoli, M. Failed Queries: a Morpho-Syntactic Analysis Based on Transaction Log Files. In (2011)
22. Pu, H.-T. An analysis of failed queries for web image retrieval. J. Inf. Sci., 34, 3, 2008, 275--289.
23. Rose, D. E. and Levinson, D. Understanding user goals in web search. In WWW (2004). ACM, 13--19.
24. Rudinac, S., Larson, M. and Hanjalic, A. Exploiting noisy visual concept detection to improve spoken content based video retrieval. In MM (2010). ACM, 727--730.
25. Shechtman, E. and Irani, M. Matching Local Self-Similarities across Images and Videos. 2007.
26. Snoek, C. G. M. and Worring, M. Concept-Based Video Retrieval. Found. Trends Inf. Retr., 2, 4, 2009, 215--322.
27. Tjondronegoro, D., Spink, A. and Jansen, B. J. A study and comparison of multimedia Web searching: 1997--2006. J. Am. Soc. Inf. Sci. Technol., 60, 9, 2009, 1756--1768.
28. White, R. W., Bennett, P. N. and Dumais, S. T. Predicting short-term interests using activity-based search context. In CIKM (2010). ACM, 1009--1018.
29. Xiang, B., Jiang, D., Pei, J., Sun, X., Chen, E. and Li, H. Con-text-aware ranking in web search. In SIGIR (2010). ACM, 451--458.
30. Yang, L. and Hanjalic, A. Supervised reranking for web image search. In MM (2010). ACM, 183--192.
31. Zha, Z.-J., Yang, L., Mei, T., Wang, M., Wang, Z., Chua, T.-S. and Hua, X.-S. Visual query suggestion: Towards capturing user intent in internet image search. ACM Trans. Multimedia Comput. Commun. Appl., 6, 3, 2010, 1--19.
32. Zhao, Y., Scholer, F. and Tsegay, Y. Effective pre-retrieval query performance prediction using similarity and variability evidence. In ECIR (2008). Springer-Verlag, 52--64.

Index Terms

• Information systems

  • Information retrieval

    • Document representation

    • Information retrieval query processing

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction