{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T13:12:15Z","timestamp":1777554735554,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research & Development Program of China","award":["2018YFB1003400, 2018YFB1003402"],"award-info":[{"award-number":["2018YFB1003400, 2018YFB1003402"]}]},{"name":"ARC","award":["DP170102726, DP180102050"],"award-info":[{"award-number":["DP170102726, DP180102050"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61728204, 91646204,61632016, 61472198, 61521002, 61661166012"],"award-info":[{"award-number":["61728204, 91646204,61632016, 61472198, 61521002, 61661166012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Google Faculty Award"},{"name":"Ministry of Science and Technology of China","award":["2016YFB1000700"],"award-info":[{"award-number":["2016YFB1000700"]}]},{"name":"973 Program of China","award":["2015CB358700"],"award-info":[{"award-number":["2015CB358700"]}]},{"name":"TAL education"},{"name":"Singapore MOE Tier 1 grant","award":["MSS18C001"],"award-info":[{"award-number":["MSS18C001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            In this article, we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards\n            <jats:italic>U<\/jats:italic>\n            (each with a location and a cost), a database of trajectories\n            <jats:italic>T<\/jats:italic>\n            , and a budget\n            <jats:italic>L<\/jats:italic>\n            , 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 |\n            <jats:italic>U<\/jats:italic>\n            | is large. By exploiting the locality property of billboards\u2019 influence, we propose a partition-based framework PartSel. PartSel partitions\n            <jats:italic>U<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3350488","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T21:19:53Z","timestamp":1594070393000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Towards an Optimal Outdoor Advertising Placement"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5463-1762","authenticated-orcid":false,"given":"Ping","family":"Zhang","sequence":"first","affiliation":[{"name":"Wuhan Univeristy, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University, Victoria, Australia"}]},{"given":"Yuchen","family":"Li","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}]},{"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"given":"Yipeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"RMIT University, Victoria, Australia"}]},{"given":"Zhiyong","family":"Peng","sequence":"additional","affiliation":[{"name":"Wuhan Univeristy, Wuhan, China"}]}],"member":"320","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Outdoor Advertising Association of America. 2018. Retrieved from http:\/\/oaaa.org\/StayConnected\/NewsArticles\/IndustryRevenue\/tabid\/322\/id\/4928.  Outdoor Advertising Association of America. 2018. Retrieved from http:\/\/oaaa.org\/StayConnected\/NewsArticles\/IndustryRevenue\/tabid\/322\/id\/4928."},{"key":"e_1_2_1_2_1","unstructured":"A. Guttmann. 2018. Retrieved from https:\/\/www.statista.com\/topics\/979\/advertising-in-the-us.  A. Guttmann. 2018. Retrieved from https:\/\/www.statista.com\/topics\/979\/advertising-in-the-us."},{"key":"e_1_2_1_3_1","unstructured":"Lamar Advertising Company. 2018. Retrieved from http:\/\/apps.lamar.com\/demographicrates\/content\/salesdocuments\/nationalratecard.xlsx.  Lamar Advertising Company. 2018. Retrieved from http:\/\/apps.lamar.com\/demographicrates\/content\/salesdocuments\/nationalratecard.xlsx."},{"key":"e_1_2_1_4_1","unstructured":"Ranjan. 2018. Retrieved from http:\/\/www.alloutdigital.com\/2012\/09\/what-are-some-advantages-of-digital-billboard-advertising.  Ranjan. 2018. Retrieved from http:\/\/www.alloutdigital.com\/2012\/09\/what-are-some-advantages-of-digital-billboard-advertising."},{"key":"e_1_2_1_5_1","unstructured":"Running Boards Pty Ltd. 2018. Retrieved from http:\/\/www.runningboards.com.au\/outdoor\/relocatable-billboards.  Running Boards Pty Ltd. 2018. Retrieved from http:\/\/www.runningboards.com.au\/outdoor\/relocatable-billboards."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735706"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0504-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2621038"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588561"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794376"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035952"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598432"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0527-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/26.4.354"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1718024"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_24_1","volume-title":"Between Min Cut and Graph Bisection","author":"Wagner Dorothea","unstructured":"Dorothea Wagner and Frank Wagner . 1993. Between Min Cut and Graph Bisection . Springer , Berlin . 744--750. Dorothea Wagner and Frank Wagner. 1993. Between Min Cut and Graph Bisection. Springer, Berlin. 744--750."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.114"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2776268"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3209989"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687754"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767892"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350488","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:20Z","timestamp":1750202600000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350488"}},"subtitle":["When a Budget Constraint Meets Moving Trajectories"],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3350488"],"URL":"https:\/\/doi.org\/10.1145\/3350488","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}