• RMIT Australia
  • RMIT Global
  • RMIT Australia
  • RMIT Europe
  • RMIT Vietnam

• Students
• Alumni
• Staff

Research Repository

Back to Library

• Home
• Browse
• Search
• FAQs
• About
• Contact Us

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) Related Links Link Description https://doi.org/10.1145/3219819.3219946 Link to Published Version   Versions Version Filter Type Thu, 21 Feb 2019, 15:03:56 EST Tue, 26 Feb 2019, 23:25:48 EST Filtered Full Citation counts:   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