BBM: bayesian browsing model from petabyte-scale data

ABSTRACT

Given a quarter of petabyte click log data, how can we estimate the relevance of each URL for a given query? In this paper, we propose the Bayesian Browsing Model (BBM), a new modeling technique with following advantages: (a) it does exact inference; (b) it is single-pass and parallelizable; (c) it is effective.

We present two sets of experiments to test model effectiveness and efficiency. On the first set of over 50 million search instances of 1.1 million distinct queries, BBM out-performs the state-of-the-art competitor by 29.2% in log-likelihood while being 57 times faster. On the second click-log set, spanning a quarter of petabyte data, we showcase the scalability of BBM: we implemented it on a commercial MapReduce cluster, and it took only 3 hours to compute the relevance for 1.15 billion distinct query-URL pairs.

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: Eugene Agichtein , Eric Brill , Susan Dumais , Robert Ragno, Learning user interaction models for predicting web search result preferences, 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.1148175]
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: ]]R. Baeza-Yates. Applications of web query mining. Advances in Information Retrieval, pages 7--22, 2005.
• 5: ]]R. Baeza-Yates, C. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In International Workshop on Clustering Information over the Web, 2004.
• 6: Mikhail Bilenko , Ryen W. White, Mining the search trails of surfing crowds: identifying relevant websites from user activity, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367505]
• 7: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 8: Nick Craswell , Onno Zoeter , Michael Taylor , Bill Ramsey, An experimental comparison of click position-bias models, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341545]
• 9: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 10: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 11: 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]
• 12: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 13: Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083789]
• 14: ]]C. Giannella, J. Han, J. Pei, X. Yan, and P. S. Yu. Mining frequent patterns in data streamsat multiple time granularities. Next Generation Data Mining, 2003.
• 15: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 16: Fan Guo , Lei Li , Christos Faloutsos, Tailoring click models to user goals, Proceedings of the 2009 workshop on Web Search Click Data, p.88-92, February 09-09, 2009, Barcelona, Spain [doi>10.1145/1507509.1507523]
• 17: Fan Guo , Chao Liu , Yi Min Wang, Efficient multiple-click models in web search, Proceedings of the Second ACM International Conference on Web Search and Data Mining, February 09-12, 2009, Barcelona, Spain [doi>10.1145/1498759.1498818]
• 18: 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]
• 19: 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]
• 20: 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]
• 21: Thomas P. Minka, Expectation Propagation for approximate Bayesian inference, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.362-369, August 02-05, 2001
• 22: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings 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]
• 23: Matthew Richardson , Ewa Dominowska , Robert Ragno, Predicting clicks: estimating the click-through rate for new ads, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242643]
• 24: ]]M. Shokouhi1, F. Scholer, and A. Turpin. Investigating the effectiveness of clickthrough data for document reordering. In ECIR'08, pages 591--595, 2008.
• 25: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 26: Andrew Trotman, Learning to Rank, Information Retrieval, v.8 n.3, p.359-381, May 2005 [doi>10.1007/s10791-005-6991-7]
• 27: Ming-Feng Tsai , Tie-Yan Liu , Tao Qin , Hsin-Hsi Chen , Wei-Ying Ma, FRank: a ranking method with fidelity loss, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277808]
• 28: Steve Wedig , Omid Madani, A large-scale analysis of query logs for assessing personalization opportunities, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150497]
• 29: 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]
• 30: ]]J. S. Yedidia, W. T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theory, 51(7):2282--2312, 2005.
• 31: Zhiyong Zhang , Olfa Nasraoui, Mining search engine query logs for query recommendation, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1136004]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bayesian models, click log analysis, web search