ABSTRACT
In this paper we propose and study the problem of optimizing the influence of outdoor advertising (ad) when impression counts are taken into consideration. Given a database U of billboards, each of which has a location and a non-uniform cost, a trajectory database T and a budget B, it aims to find a set of billboards that has the maximum influence under the budget. In line with the advertising consumer behavior studies, we adopt the logistic function to take into account the impression counts of an ad (placed at different billboards) to a user trajectory when defining the influence measurement. However, this poses two challenges: (1) our problem is NP-hard to approximate within a factor of O(|T|1-ε) for any ε>0 in polynomial time; (2) the influence measurement is non-submodular, which means a straightforward greedy approach is not applicable. Therefore, we propose a tangent line based algorithm to compute a submodular function to estimate the upper bound of influence. Henceforth, we introduce a branch-and-bound framework with a θ-termination condition, achieving θ2/(1 - 1/e) approximation ratio. However, this framework is time-consuming when |U| is huge. Thus, we further optimize it with a progressive pruning upper bound estimation approach which achieves θ2/(1 - 1/e - ε) approximation ratio and significantly decreases the running-time. We conduct the experiments on real-world billboard and trajectory datasets, and show that the proposed approaches outperform the baselines by 95% in effectiveness. Moreover, the optimized approach is around two orders of magnitude faster than the original framework.
- Penneco Outdoor Advertising. 2016. Billboard Statistics. https://www.pennecooutdoor.com/billboard-statisticsGoogle Scholar
- Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. 2013. Local-Search based Approximation Algorithms for Mobile Facility Location Problems. In SODA. SIAM, 1607--1621. Google ScholarDigital Library
- Christoph Ambü hl, Monaldo Mastrolilli, and Ola Svensson. 2011. Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut. SIAM J. Comput., Vol. 40, 2 (2011), 567--596. Google ScholarDigital Library
- Margaret C Campbell and Kevin Lane Keller. 2003. Brand familiarity and advertising repetition effects. Journal of consumer research, Vol. 30, 2 (2003), 292--304.Google ScholarCross Ref
- Can Chen, Junming Liu, Qiao Li, Yijun Wang, Hui Xiong, and Shanshan Wu. 2017. Warehouse Site Selection for Online Retailers in Inter-Connected Warehouse Networks. In ICDM. IEEE, 805--810.Google Scholar
- Farhana Murtaza Choudhury, J. Shane Culpepper, Zhifeng Bao, and Timos Sellis. 2018. Finding the optimal location and keywords in obstructed and unobstructed space. VLDB J., Vol. 27, 4 (2018), 445--470. Google ScholarDigital Library
- Gershon Feder, Richard E Just, and David Zilberman. 1985. Adoption of agricultural innovations in developing countries: A survey. Economic development and cultural change, Vol. 33, 2 (1985), 255--298.Google ScholarCross Ref
- Gerald J Gorn and Marvin E Goldberg. 1980. Children's responses to repetitive television commercials. Journal of Consumer Research, Vol. 6, 4 (1980), 421--424.Google ScholarCross Ref
- William H Greene. 2003. Econometric analysis .Pearson Education India.Google Scholar
- Johny K Johansson. 1979. Advertising and the S-curve: A new approach. Journal of Marketing Research (1979), 346--354.Google Scholar
- Samir Khuller, Anna Moss, and Joseph Naor. 1999. The Budgeted Maximum Coverage Problem. Inf. Process. Lett., Vol. 70, 1 (1999), 39--45. Google ScholarDigital Library
- LAMAR. 2017. National Rate Card. http://apps.lamar.com/demographicrates/content/salesdocuments/nationalratecard.xlsxGoogle Scholar
- Sang Yup Lee. 2014. Examining the factors that influence early adopters' smartphone adoption: The case of college students. Telematics and Informatics, Vol. 31, 2 (2014), 308--318. Google ScholarDigital Library
- Guoliang Li, Shuo Chen, Jianhua Feng, Kian-Lee Tan, and Wen-Syan Li. 2014. Efficient location-aware influence maximization. In SIGMOD. ACM, 87--98. Google ScholarDigital Library
- Shi Li. 2019. On Facility Location with General Lower Bounds. In SODA. SIAM, 2279--2290. Google ScholarDigital Library
- John DC Little. 1979. Aggregate advertising models: The state of the art. Operations research, Vol. 27, 4 (1979), 629--667. Google ScholarDigital Library
- Dongyu Liu, Di Weng, Yuhong Li, Jie Bao, Yu Zheng, Huamin Qu, and Yingcai Wu. 2017. SmartAdP: Visual Analytics of Large-scale Taxi Trajectories for Selecting Billboard Locations. IEEE Trans. Vis. Comput. Graph., Vol. 23, 1 (2017), 1--10. Google ScholarDigital Library
- Yubao Liu, Raymond Chi-Wing Wong, Ke Wang, Zhijie Li, Cheng Chen, and Zitong Chen. 2013. A new approach for maximizing bichromatic reverse nearest neighbor search. Knowl. Inf. Syst., Vol. 36, 1 (2013), 23--58. Google ScholarDigital Library
- Prashant Malaviya. 2007. The moderating influence of advertising context on ad repetition effects: The role of amount and type of elaboration. Journal of Consumer Research, Vol. 34, 1 (2007), 32--40.Google ScholarCross Ref
- M. Teresa Melo, Stefan Nickel, and Francisco Saldanha-da-Gama. 2006. Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Computers & OR, Vol. 33 (2006), 181--208. Google ScholarDigital Library
- M. Teresa Melo, Stefan Nickel, and Francisco Saldanha-da-Gama. 2009. Facility location and supply chain management - A review. European Journal of Operational Research, Vol. 196, 2 (2009), 401--412.Google ScholarCross Ref
- George A Miller. 1956. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological review, Vol. 63, 2 (1956), 81.Google Scholar
- Kristian S Palda. 1965. The measurement of cumulative advertising effects. The Journal of Business, Vol. 38, 2 (1965), 162--179.Google ScholarCross Ref
- William Sierzchula, Sjoerd Bakker, Kees Maat, and Bert Van Wee. 2014. The influence of financial incentives and other socio-economic factors on electric vehicle adoption. Energy Policy, Vol. 68 (2014), 183--194.Google ScholarCross Ref
- Julian L Simon and Johan Arndt. 1980. The shape of the advertising response function. Journal of Advertising Research (1980).Google Scholar
- Jennifer Taylor, Rachel Kennedy, and Byron Sharp. 2009. Is once really enough? Making generalizations about advertising's convex sales response function. Journal of Advertising Research, Vol. 49, 2 (2009), 198--200.Google ScholarCross Ref
- Gerard J Tellis. 1988. Advertising exposure, loyalty, and brand purchase: A two-stage model of choice. Journal of marketing research (1988), 134--144.Google Scholar
- Kenneth E Train. 2009. Discrete choice methods with simulation .Cambridge university press.Google Scholar
- Demetrios Vakratsas, Fred M Feinberg, Frank M Bass, and Gurumurthy Kalyanaram. 2004. The shape of advertising response functions revisited: A model of dynamic probabilistic thresholds. Marketing Science, Vol. 23, 1 (2004), 109--119.Google ScholarDigital Library
- Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, and Gao Cong. 2018. Reverse k Nearest Neighbor Search over Trajectories. IEEE Trans. Knowl. Data Eng., Vol. 30, 4 (2018), 757--771.Google ScholarCross Ref
- Raymond Chi-Wing Wong, M. Tamer Ö zsu, Philip S. Yu, Ada Wai-Chee Fu, and Lian Liu. 2009. Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor. PVLDB, Vol. 2, 1 (2009), 1126--1137. Google ScholarDigital Library
- Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. 2018. Trajectory-driven Influential Billboard Placement. In SIGKDD. ACM, 2748--2757. Google ScholarDigital Library
- Zenan Zhou, Wei Wu, Xiaohui Li, Mong-Li Lee, and Wynne Hsu. 2011. MaxFirst for MaxBRkNN. In ICDE. IEEE, 828--839. Google ScholarDigital Library
Index Terms
- Optimizing Impression Counts for Outdoor Advertising
Recommendations
Data-driven Targeted Advertising Recommendation System for Outdoor Billboard
In this article, we propose and study a novel data-driven framework for Targeted Outdoor Advertising Recommendation (TOAR) with a special consideration of user profiles and advertisement topics. Given an advertisement query and a set of outdoor billboards ...
Towards an Optimal Outdoor Advertising Placement: When a Budget Constraint Meets Moving Trajectories
Special Issue on KDD 2018, Regular Papers and Survey PaperIn this article, we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards U (each with a location and a cost), a database of trajectories T, and a budget L, we find a set of billboards within the ...
Trajectory-driven Influential Billboard Placement
KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningIn this paper we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards $\ur$ (each with a location and a cost), a database of trajectories $\td$ and a budget $\budget$, find a set of billboards ...
Comments