Trajectory-driven Influential Billboard Placement

Zhang, P, Bao, Z, Li, Y, Li, G, Zhang, Y and Peng, Z 2018, 'Trajectory-driven Influential Billboard Placement', in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, United Kingdom, August 19 - 23 2018, pp. 2748-2757.


Document type: Conference Paper
Collection: Conference Papers

Title Trajectory-driven Influential Billboard Placement
Author(s) Zhang, P
Bao, Z
Li, Y
Li, G
Zhang, Y
Peng, Z
Year 2018
Conference name 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Conference location London, United Kingdom
Conference dates August 19 - 23 2018
Proceedings title Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018
Publisher ACM
Place of publication United States
Start page 2748
End page 2757
Total pages 10
Abstract 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.
Subjects Pattern Recognition and Data Mining
Database Management
DOI - identifier 10.1145/3219819.3219946
Copyright notice © 2018 Copyright held by the owner/author(s)
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Altmetric details:
Access Statistics: 13 Abstract Views  -  Detailed Statistics
Created: Thu, 21 Feb 2019, 12:10:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us