Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
8-2018
Abstract
In this paper 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, find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with (1−1/e) approximation ratio. However, the enumeration should be very costly when |U| is large. By exploiting the locality property of billboards’ influence, we propose a partition-based framework PartSel. PartSel partitions U into a set of small clusters, computes the locally influential billboards for each cluster, and merges them to generate the global solution. Since the local solutions can be obtained much more efficient than the global one, PartSel should reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a LazyProbe method to further prune billboards with low marginal influence, while achieving the same approximation ratio as PartSel. Experiments on real datasets verify the efficiency and effectiveness of our methods.
Keywords
Outdoor Advertising, Influence Maximization, Trajectory
Discipline
Advertising and Promotion Management | Computer Sciences | Databases and Information Systems
Research Areas
Data Science and Engineering
Publication
KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, August 19-23
First Page
2748
Last Page
2757
ISBN
9781450355520
Identifier
10.1145/3219819.3219946
Publisher
ACM
City or Country
New York
Citation
ZHANG, Ping; BAO, Zhifeng; LI, Yuchen; LI, Guoliang; ZHANG, Yipeng; and PENG, Zhiyong.
Trajectory-driven influential billboard placement. (2018). KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, August 19-23. 2748-2757.
Available at: https://ink.library.smu.edu.sg/sis_research/4144
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1145/3219819.3219946