选址问题一直是当前社会中常见的热点问题,比如:广告气球的投放,公共设施安置以及实体销售网点选择,这类问题时时刻刻出现在实际生活中。随着,GPS技术在移动设备上的广泛应用,可以获取到不同设备用户大量的位置信息。选址问题的初衷便是更好的服务大众或者吸引大众的注意力。在这些地理位置信息的基础上,再进行选址问题的分析,会使得到的结果更具有参考价值。在本文中,主要研究并提出一个基于移动轨迹的Top-k最大影响力设施问题。具体来说,给定一个侯选地集合,一组移动对象的轨迹数据,每个对象的轨迹由一系列特定的位置点组成的,以及一个期望值k,本文的目标是找到一组由k个位置组成的集合,该集合可以影响最大数量的移动对象。本文说明了这个问题是一个NP难问题,并且提出了一个基本的贪心算法,命名为Greedy P算法。同时证明了利用贪心算法解决该问题可以达到至少(1-_e~1)近似度保证。利用贪心算法面临的一大挑战便是鉴别并删除已经选出位置影响的重叠从而最大化边际收益。因此,在移动对象轨迹集合数量非常庞大的时候,Greedy P算法时间消耗巨大。为了解决这个问题,文中提出了另一种利用FM-sketch技术的Greedy PS算法。FM-sketch技术是将移动对象轨迹映射到比特数组中,因此最大边际收益可以使用位-或运算简单快速地计算出来。通过这种方法,将算法的时间消耗降低了一半,同时在算法精度上保持可以接受的损失。接着,文中又提出了一对扩展问题命名为k-Additional和k-Eliminative最大影响设施放置问题。同样提出了对应问题的近似算法解决方案,并且展示了各个算法的理论保证。最后,在真实的数据集上,实验验证了所有算法与基准算法相比的有效性。