Multiple intents re-ranking

ABSTRACT

One of the most fundamental problems in web search is how to re-rank result web pages based on user logs. Most traditional models for re-ranking assume each query has a single intent. That is, they assume all users formulating the same query have similar preferences over the result web pages. It is clear that this is not true for a large portion of queries as different users may have different preferences over the result web pages. Accordingly, a more accurate model should assume that queries have multiple intents. In this paper, we introduce the multiple intents re-ranking problem. This problem captures scenarios in which some user makes a query, and there is no information about its real search intent. In such cases, one would like to re-rank the search results in a way that minimizes the efforts of all users in finding their relevant web pages. More formally, the setting of this problem consists of various types of users, each of which interested in some subset of the search results. Moreover, each user type has a non-negative profile vector. Consider some ordering of the search results. This order sets a position for each search result, and induces a position vector of the results relevant to each user type. The overhead of a user type is the dot product of its profile vector and its induced position vector. The goal is to order the search results as to minimize the average overhead of the users. Our main result is an O(log r)-approximation algorithm for the problem, where r is the maximum number of search results that are relevant to any user type. The algorithm is based on a new technique, which we call harmonic interpolation. In addition, we consider two important special cases. The first case is when the profile vector of each user type is non-increasing. This case is a generalization of the well-known min-sum set cover problem. We extend the techniques of Feige, Lovasz and Tetali (Algorithmica '04), and present an algorithm achieving 4-approximation. The second case is when the profile vector of each user type is non-decreasing. This case generalizes the minimum latency set cover problem, introduced by Hassin and Levin (ESA '05). We devise an LP-based algorithm that attains 2-approximation for it.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 2: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 3: Amotz Bar-Noy , Mihir Bellare , Magnús M. Halldórsson , Hadas Shachnai , Tami Tamir, On chromatic sums and distributed resource allocation, Information and Computation, v.140 n.2, p.183-202, Feb. 1, 1998 [doi>10.1006/inco.1997.2677]
• 4: A. Bar-Noy, M. M. Halldórsson, and G. Kortsarz. A matched approximation bound for the sum of a greedy coloring. Inf. Process. Lett., 71(3-4):135--140, 1999.
• 5: Edith Cohen , Amos Fiat , Haim Kaplan, Efficient sequences of trials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: Georges E. Dupret , Benjamin Piwowarski, A user browsing model to predict search engine click data from past observations., Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390392]
• 7: Uriel Feige , Prasad Tetali, Approximating Min Sum Set Cover, Algorithmica, v.40 n.4, p.219-234, September 2004 [doi>10.1007/s00453-004-1110-5]
• 8: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 9: R. Hassin and A. Levin. An approximation algorithm for the minimum latency set cover problem. In Proceedings 13th Annual European Symposium on Algorithms, pages 726--733, 2005.
• 10: Bernard J. Jansen , Danielle L. Booth , Amanda Spink, Determining the informational, navigational, and transactional intent of Web queries, Information Processing and Management: an International Journal, v.44 n.3, p.1251-1266, May, 2008 [doi>10.1016/j.ipm.2007.07.015]
• 11: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Filip Radlinski , Geri Gay, Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web search, ACM Transactions on Information Systems (TOIS), v.25 n.2, p.7-es, April 2007 [doi>10.1145/1229179.1229181]
• 12: Haim Kaplan , Eyal Kushilevitz , Yishay Mansour, Learning with attribute costs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060644]
• 13: K. Munagala, S. Babu, R. Motwani, and J. Widom. The pipelined set cover problem. In Proceedings 10th International Conference on Database Theory, pages 83--98, 2005.
• 14: Maurice Queyranne, Structure of a simple scheduling polyhedron, Mathematical Programming: Series A and B, v.58 n.2, p.263-285, Feb. 2, 1993 [doi>10.1007/BF01581271]
• 15: Andreas S. Schulz, Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.301-315, June 03-05, 1996
• 16: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 17: Ruihua Song , Zhenxiao Luo , Ji-Rong Wen , Yong Yu , Hsiao-Wuen Hon, Identifying ambiguous queries in web search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242749]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, min-sum set cover, minimum latency set cover, multiple intents, ranking