Trajectory-driven Top-k Influential Facility Placement

Facility placement problem has always been a hot issue in the current society,such as set-ting up billboards,building public facilities and selecting sales outlets.Such problems are common in practical applications.With the widespread application of GPS technology on mobile devices,we can obtain a large amount of location information for different users.The original intention of the facility placement problem is to better serve the public or at-tract the attention of the public.On the basis of these geographical location information,the analysis of the facility placement problem will make the results more valuable.In this thesis,we propose and study the problem of Trajectory-driven Top-k Influential Fa-cility Placement.Specifically,given a set of candidate locations,a group of moving objects,each of which is associated with a collection of reference points,as well as a budget k,we aim to mine a group of k locations,the combination of whom can influence the most num-ber of moving objects.We show that this problem is NP-hard and present a basic hill-climb algorithm,namely Greedy P.We prove this method with(1-_e~1)approximation ratio.One core challenge is to identify and reduce the overlap of the influence from different selected locations to maximize the marginal benefits.Therefore,the Greedy P approach may be very costly when the number of moving objects is large.In order to address the problem,we also propose another Greedy PS algorithm based on FM-sketch technique,which maps the moving objects to bitmaps such that the marginal benefit can be easily observed through bit-wise operations.Through this way,we are able to save more than a half running time while preserving the result quality.We further present a pair of extensions to the problem,namely k-Additional and k-Eliminative Influential Facility Placement problems.We also present corresponding approximate solutions towards both extensions and theoretically show that results of both algorithms are guaranteed.Experiments on real datasets verify the efficiency and effectiveness for all these algorithms comparing with baselines.