Towards an Optimal Outdoor Advertising Placement
Towards an Optimal Outdoor Advertising Placement
复制标题
实现最佳户外广告投放：当预算约束满足移动轨迹时
DOI：
10.1145/3350488
复制
发表时间：
2020-07
影响因子：
3.6
通讯作者：
Zhiyong Peng
中科院分区：
文献类型：
--
作者：
Ping Zhang;Zhifeng Bao;Yuchen Li;Guoliang Li;Yipeng Zhang;Zhiyong Peng
在这篇文章中，我们提出和研究的问题，有影响力的广告牌的位置：给定一组广告牌U（每个位置和成本），轨迹T的数据库，和预算L，我们找到一组广告牌的预算内影响最大数量的轨迹。一个核心挑战是识别和减少不同广告牌对相同轨迹的影响的重叠，同时考虑到预算限制。我们证明了这个问题是NP-难的，并提出了一个基于枚举的算法（1-1/e）的近似比。然而，枚举将是非常昂贵的，|U|很大。通过利用广告牌影响的局部性，我们提出了一个基于划分的框架PartSel。PartSel将U划分为一组小集群，计算每个集群的本地影响力广告牌，并合并它们以生成全局解决方案。由于局部解的获得比全局解的获得效率高得多，PartSel在保证非平凡逼近比的同时，大大降低了计算量.然后，我们提出了一个LazyProbe方法，以进一步修剪广告牌的边际影响力低，同时达到相同的近似比PartSel。接下来，我们提出了一个分支定界方法来消除PartSel和LazyProbe中不必要的枚举，以及一个聚合索引来加速边际影响的计算。在真实的数据集上的实验验证了本文方法的有效性。
In 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 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 would 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 efficiently than the global one, PartSel would 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. Next, we propose a branch-and-bound method to eliminate unnecessary enumerations in both PartSel and LazyProbe, as well as an aggregated index to speed up the computation of marginal influence. Experiments on real datasets verify the efficiency and effectiveness of our methods.
登录
查看更多内容
DOI：
10.1109/icde.2011.5767892
发表时间：
2011-04
期刊：
2011 IEEE 27th International Conference on Data Engineering
影响因子：
--
作者：
Zenan Zhou;Wei Wu;Xiaohui Li;M. Lee;W. Hsu
通讯作者：
Zenan Zhou;Wei Wu;Xiaohui Li;M. Lee;W. Hsu
DOI：
10.1007/3-540-57182-5_65
发表时间：
1993-08
期刊：
--
影响因子：
--
作者：
D. Wagner;Frank Wagner
通讯作者：
D. Wagner;Frank Wagner
DOI：
10.1145/3035918.3035952
发表时间：
2017-05
期刊：
Proceedings of the 2017 ACM International Conference on Management of Data
影响因子：
--
作者：
Yuchen Li;Ju Fan;Dongxiang Zhang;K. Tan
通讯作者：
Yuchen Li;Ju Fan;Dongxiang Zhang;K. Tan
影响因子：
2.7
作者：
Yubao Liu;R. C. Wong;Ke Wang;Zhijie Li;Cheng Chen;Zitong Chen
通讯作者：
Yubao Liu;R. C. Wong;Ke Wang;Zhijie Li;Cheng Chen;Zitong Chen
DOI：
10.1109/icde.2017.20
发表时间：
2017-04
期刊：
2017 IEEE 33rd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Long Guo;Dongxiang Zhang;G. Cong;Wei Wu;K. Tan
通讯作者：
Long Guo;Dongxiang Zhang;G. Cong;Wei Wu;K. Tan