Influential facilities placement over moving objects
- PDF / 2,048,476 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 207 Views
Influential facilities placement over moving objects Ying Zhou1,2 · Hui Li1,2 · Dan Li1 · Meng Wang3 · Jiangtao Cui4 Accepted: 14 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper we propose and study the problem of k-Collective influential facility placement over moving object. 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 number of moving objects. We show that this problem is NP-hard and present a basic hill-climb algorithm, namely GreedyP. We prove this method with (1 − 1e ) 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 GreedyP approach may be very costly when the number of moving objects is large. In order to address the problem, we also propose another GreedyPS 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. Keywords Moving objects · Location selection · Submodular · Approximate algorithm
A short version of this paper appeared in [16], which received the Best Paper Award Runner-up in MDM 2019. * Hui Li [email protected] 1
State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an, China
2
School of Cyber Engineering, Xidian University, Xi’an, China
3
School of Computer Science, Xi’an Polytechnic University, Xi’an, China
4
School of Computer Science and Technology, Xidian University, Xi’an, China
13
Vol.:(0123456789)
Distributed and Parallel Databases
Fig. 1 Motivating example
1 Introduction Location Selection (ls) problem has always received great attention due to the value of application in many aspects. Given a set of moving objects 𝛺 , each of which is represented using a set of reference positions, and a set of candidate locations C, many methods have been proposed to detect an optimal c ∈ C , such that c can influence (i.e., affect/cover) the maximum number of moving objects [29]. Finding such an optimal location from candidates to establish a new facility has a wide spectrum of applications such as marketing, urban planning [35], monitoring wildlife [14], scientific research, etc. In ls problem, influence refers to the number (i.e., probability) of persons (i.e
Data Loading...
