0


轨迹驱动的影响广告牌放置

Trajectory-driven Influential Billboard Placement
课程网址: http://videolectures.net/kdd2018_zhang_billboard_placement/  
主讲教师: Ping Zhang
开课单位: 武汉大学(WHU)
开课时间: 2018-11-23
课程语种: 英语
中文简介:
在本文中,我们提出并研究了轨迹驱动的有影响力的广告牌放置问题:给定一组广告牌$ur$(每个广告牌都有位置和成本)、一个轨迹数据库$td$和一个预算$budge$,在预算内找到一组影响最多轨迹的广告牌。一个核心挑战是确定并减少不同广告牌对相同轨迹的影响重叠,同时考虑预算限制。我们证明了这个问题是NP难的,并提出了一个基于枚举的算法,其近似比为$(1-1/e)$。然而,当$|ur|$较大时,枚举的开销应该非常大。通过利用广告牌影响的局部性,我们提出了一个基于分区的框架psel。psel将$ur$划分为一组小集群,计算每个集群的本地影响力广告牌,并将它们合并以生成全局解决方案。由于可以获得比全局解更有效的局部解,psel应该大大降低计算成本;同时,它实现了非平凡的近似比保证。然后,我们提出了一种bbsel方法来进一步修剪具有低边缘影响的广告牌,同时实现与psel相同的近似比率。在真实数据集上的实验验证了我们方法的效率和有效性。
课程简介: In 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 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 $|ur|$ is large. By exploiting the locality property of billboards’ influence, we propose a partition-based framework psel. psel partitions $ur$ 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, psel should reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a bbsel method to further prune billboards with low marginal influence, while achieving the same approximation ratio as psel. Experiments on real datasets verify the efficiency and effectiveness of our methods.
关 键 词: 相同的近似比率; 有影响力的广告牌放置问题; 真实数据集; 生成全局解决方案
课程来源: 视频讲座网
数据采集: 2023-03-08:cyh
最后编审: 2023-03-08:cyh
阅读次数: 30