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. We also extend our problem to support the scenario when there are a group of advertisements. We validate our approach via extensive experiments with real datasets.


Click here:-  Dotnet Diploma Project Centers Chennai 



We make the first attempt to transplant the concept of influence maximization from social-aware advertising to location-aware advertising. To facilitate a better comprehension of our new problem, we start with a toy example depicted. Each user or audience ui in this scenario

is associated with an interest profile as well as motion patterns. For instance, we know that u2 likes pizza and will wait at bus stop o2 daily with probability 0.6 in a certain time period.

On the other hand, we are aware of the trajectory information of all the buses from their schedules.




It partitions the trajectory database into clusters and allows us to access the clusters in an order such that promising trajectories will be found earlier. Our third approximate solution, named threshold-based method, provides a flexible means to adjust the tradeoff between efficiency and accuracy



We 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 propose a novel trajectory index which pre-computes a portion of the influence. To facilitate early termination of the algorithm, we propose three types of upper bound influence score,





  • System               :  Pentium IV 2.4 GHz.
  • Hard Disk            :  40 GB.
  • Floppy Drive        :  1.44 Mb.
  • Monitor               :  15 VGA Colour.
  • Mouse                 :  Logitech.
  • Ram                    :  2 Gb.




  • Operating system     :   Windows XP/7.
  • Coding Language      :,
  • Tool                         :   Visual Studio 2010
  • Database                  :   SQL SERVER 2008




[1] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan, “A data-based approach to social influence maximization,” Proc. VLDB Endow., 2011.

[2] Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si, and K. Xie, “Simulated annealing based influence maximization in social networks,” in AAAI, 2011.

[3] Y. Li, D. Zhang, and K.-L. Tan, “Real-time targeted influence maximization for online advertisements,” Proc. VLDB Endow., 2015.

[4] P. Domingos and M. Richardson, “Mining the network value of customers,” in KDD, 2001.

[5] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” in KDD, 2003


Leave a comment