Large-scale behavioral targeting
Authors:
Open Access
- 28 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 209-218
Abstract
Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from ne-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and ecient solution to BT using Hadoop MapReduce framework. With our paral- lel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo's user base within one day, the scale that one can not even imagine with prior systems. Moreover, our approach has yielded 20% CTR lift over the existing production system by lever- aging the well-grounded probabilistic model tted from a much larger training dataset. Specically, our major contributions include: (1) A MapRe- duce statistical learning algorithm and implementation that achieve optimal data parallelism, task parallelism, and load balance in spite of the typically skewed distribution of do- main data. (2) An in-place feature vector generation algo- rithm with linear time complexity O(n) regardless of the granularity of sliding target window. (3) An in-memory caching scheme that signicantly reduces the number of disk IOs to make large-scale learning practical. (4) Highly e- cient data structures and sparse representations of models and data to enable fast model updates. We believe that our work makes signicant contributions to solving large-scale machine learning problems of industrial relevance in gen- eral. Finally, we report comprehensive experimental results, using industrial proprietary codebase and datasets.Keywords
This publication has 5 references indexed in Scilit:
- MapReduceCommunications of the ACM, 2008
- GaP2004
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- Regression Analysis of Count Data1998
- A Comparison of Several Bandwidth and Profile Reduction AlgorithmsACM Transactions on Mathematical Software, 1976