{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:18Z","timestamp":1750307298822,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>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 fine-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and efficient solution to BT using Hadoop MapReduce framework. With our parallel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo\u2019s 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 leveraging the well-grounded probabilistic model fitted from a much larger training dataset.<\/jats:p>\n          <jats:p>\n            Specifically, our major contributions include: (1) A MapReduce statistical learning algorithm and implementation that achieve optimal data parallelism, task parallelism, and load balance in spite of the typically skewed distribution of domain data. (2) An in-place feature vector generation algorithm with strict linear-time complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) regardless of the granularity of sliding target window. (3) An in-memory caching scheme that significantly reduces the number of disk IOs to make large-scale learning practical. (4) Highly efficient data structures and sparse representations of models and data to enable fast model updates. We believe that our work makes significant contributions to solving large-scale machine learning problems of industrial relevance in general. Finally, we report comprehensive experimental results, using industrial proprietary codebase and datasets.\n          <\/jats:p>","DOI":"10.1145\/1857947.1857949","type":"journal-article","created":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T13:32:33Z","timestamp":1288618353000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Behavioral Targeting"],"prefix":"10.1145","volume":"4","author":[{"given":"Ye","family":"Chen","sequence":"first","affiliation":[{"name":"Microsoft Corporation"}]},{"given":"Dmitry","family":"Pavlov","sequence":"additional","affiliation":[{"name":"Yandex Labs"}]},{"given":"John F.","family":"Canny","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]}],"member":"320","published-online":{"date-parts":[[2010,10]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"925","article-title":"Determining ad targeting information and\/or ad creative information using past search queries","volume":"10","author":"Agarwal S.","year":"2004","journal-title":"U.S. Patent"},{"volume-title":"Proceedings of the NIPS Workshop on Parallel Implementations of Learning Algorithms: What have you done for me lately?","year":"2008","author":"Andersen D.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277837"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Cameron A. C. and Trivedi P. K. 1998. Regression Analysis of Count Data. Cambridge University Press. Cameron A. C. and Trivedi P. K. 1998. Regression Analysis of Count Data . Cambridge University Press.","DOI":"10.1017\/CBO9780511814365"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009016"},{"key":"e_1_2_1_6_1","first-page":"413","article-title":"Granular data for behavioral targeting","volume":"11","author":"Canny J.","year":"2007","journal-title":"U.S. Patent Application"},{"volume-title":"Proceedings of the NIPS Workshop on Beyond Search: Computational Intelligence for the Web.","year":"2008","author":"Chang E.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems 22 (NIPS\u201909)","author":"Chen Y.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","first-page":"749","article-title":"Large-scale behavioral targeting for advertising over a network","volume":"12","author":"Chen Y.","year":"2009","journal-title":"U.S. Patent Application"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646087"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557048"},{"key":"e_1_2_1_12_1","first-page":"374","article-title":"Model for generating user profiles in a behavioral targeting system","volume":"11","author":"Chung C. Y.","year":"2006","journal-title":"U.S. Patent"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367529"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355707"},{"key":"e_1_2_1_16_1","unstructured":"Hadoop. 2009a. http:\/\/hadoop.apache.org\/. Hadoop . 2009a. http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_17_1","unstructured":"Hadoop. 2009b. http:\/\/hadoop.apache.org\/common\/docs\/current\/mapred_tutorial.html#DistributedCache. Hadoop . 2009b. http:\/\/hadoop.apache.org\/common\/docs\/current\/mapred_tutorial.html#DistributedCache."},{"volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201900)","author":"Lee D. D.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2000.10474340"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_21_1","unstructured":"Torque. 2009. http:\/\/www.clusterresources.com\/pages\/products.php. Torque . 2009. http:\/\/www.clusterresources.com\/pages\/products.php."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857947.1857949","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1857947.1857949","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:51Z","timestamp":1750244391000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857947.1857949"}},"subtitle":["The Art of Scaling Up Simple Algorithms"],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1857947.1857949"],"URL":"https:\/\/doi.org\/10.1145\/1857947.1857949","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2009-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}