Retroactive answering of search queries

ABSTRACT

Major search engines currently use the history of a user's actions (e.g., queries, clicks) to personalize search results. In this paper, we present a new personalized service, query-specific web recommendations (QSRs), that retroactively answers queries from a user's history as new results arise. The QSR system addresses two important subproblems with applications beyond the system itself: (1) Automatic identification of queries in a user's history that represent standing interests and unfulfilled needs. (2) Effective detection of interesting new results to these queries. We develop a variety of heuristics and algorithms to address these problems, and evaluate them through a study of Google history users. Our results strongly motivate the need for automatic detection of standing interests from a user's history, and identifies the algorithms that are most useful in doing so. Our results also identify the algorithms, some which are counter-intuitive, that are most useful in identifying interesting new results for past queries, allowing us to achieve very high precision over our data set.

References

1. Amazon website. http://www.amazon.com.
2. S. Babu and J. Widom. Continuous queries over data streams. In SIGMOD Record, September 2001.
3. J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proc. of the Conference on Uncertainty in Artifical Intelligence, 1998.
4. J. Chen, D. DeWitt, F. Tian, and Y. Wang. Niagaracq: A scalable continuous query system for internet databases. In Proc. of SIGMOD, 2000.
5. D. Goldberg, D. Nichols, B. Oki, and D. Terry. Using collaborative filtering to weave an information tapestry. In Communications of the ACM, December 1992.
6. Google website. http://www.google.com.
7. Google Web Alerts. http://www.google.com/alerts.
8. J. Herlocker, J. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In SIGIR, August 1999.
9. G. Jeh and J. Widom. Scaling personalized web search. In Proc. of WWW 2003, May 2003.
10. U. Lee, Z. Liu, and J. Cho. Automatic identification of user goals in web search. In Proc. of WWW 2005, May 2005.
11. F. Liu, C. Yu, and W. Meng. Personalized web search by mapping user queries to categories. In Proc. of the Conference on Information and Knowledge Management, November 2002.
12. S. Madden, M. Shah, J. Hellerstein, and J. Raman. Continuously adaptive continuous queries over streams. In Proc. of SIGMOD, 2002.
13. P. Melville, R. Mooney, and R. Nagarajan. Content-boosted collaborative filtering for improved recommenadtions. In Proc. of the Conference on Artifical Intelligence, July 2002.
14. J. H. Hwanga nd M. Balazinska, A. Rasin, U. Cetintemel, M. Stonebraker, and S. Zdonik. High availability algorithms for distributed stream processing. In Proc. of the 21st International Conference on Data Engineering, April 2005.
15. J. Pitkow, H. Schutze, T. Cass, R. Cooley, D. Turnbull, A. Edmonds, E. Edar, and T. Breuel. Personalized search. In Communications of the ACM, 45(9):50--55, 2002.
16. A. Popescul, L. Ungar, D. Pennock, and S. Lawrence. Probabilistic models for unified collaborative and content-based recommendation in sparse-data environments. In Proc. of the Conference on Uncertainty in Artifical Intelligence, 2001.
17. D. Rose and D. Levinson. Understanding user goals in web search. In World Wide Web Conference (WWW), 2004.
18. K. Sugiyama, K. Hatano, and M. Yoshikawa. Adaptive web search based on user profile constructed without any effort from users. In Proc. of WWW, 2004.
19. J. Sun, H. Zeng, H. Liu, Y. Lu, and Z. Chen. Cubesvd: A novel approach to personalized web search. In Proc. of WWW 2005, 2005 May.
20. Yahoo website. http://www.yahoo.com.
21. B. Yang and G. Jeh. Retroactive answering of search queries. Technical report, 2006. Extended version, available upon request.

Index Terms

• Information systems

  • Information retrieval

    • Users and interactive retrieval

      • Personalization

  • World Wide Web

    • Web searching and information discovery

      • Personalization