Abstract | ||
---|---|---|
In this paper, we study a novel problem of influence maximization in trajectory databases that is very useful in precise location-aware advertising. It finds $k$ best trajectories to be attached with a given advertisement and maximizes the expected influence among a large group of audience. We show that the problem is NP-hard and propose both exact and approximate solutions to find the best set of trajectories. In the exact solution, we devise an expansion-based framework that enumerates trajectory combinations in a best-first manner and propose three types of upper bound estimation techniques to facilitate early termination. In addition, we propose a novel trajectory index to reduce the influence calculation cost. To support large $k$ , we propose a greedy solution with an approximation ratio of (1 − 1/e), whose performance is further optimized by a new proposed cluster-based method. We also propose a threshold method that can support any approximation ratio $\\epsilon \\in (0,1]$ . In addition, we extend our problem to support the scenario when there are a group of advertisements. In our experiments, we use real datasets to construct user profiles, motion patterns, and trajectory databases. The experimental results verified the efficiency of our proposed methods. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/TKDE.2016.2621038 | IEEE Trans. Knowl. Data Eng. |
Keywords | DocType | Volume |
Trajectory,Databases,Vehicles,Advertising,Upper bound,Q measurement,Estimation | Conference | 29 |
Issue | ISSN | Citations |
3 | 1041-4347 | 14 |
PageRank | References | Authors |
0.52 | 20 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Long Guo | 1 | 65 | 4.17 |
Dongxiang Zhang | 2 | 743 | 43.89 |
gao cong | 3 | 4086 | 169.93 |
Wei Wu | 4 | 160 | 13.27 |
Kian-Lee Tan | 5 | 6962 | 776.65 |