PINOCCHIO: Probabilistic Influence-Based Location Selection over Moving Objects

The location selection (LS) problem, which aims to mine the optimal location from a set of candidates to place a new facility such that a score (i.e., benefit or influence on some given objects) can be maximized, has drawn significant research attention in recent years. State-of-the-art LS techniques assume each object is static and can only be influenced by a single facility. However, in reality, objects (e.g., people, vehicles) are mobile and are influenced by multiple facilities, which prevents classical LS solutions from selecting accurate results. In this paper, we introduce a generalized LS problem called PRIME-LS which takes mobility and probability factors into consideration to address the aforementioned limitations. Specifically, given a set of candidate locations, PRIME-LS aims to mine the optimal location which can influence the most number of moving objects. Also, to address the problem we propose an efficient algorithm called PINOCCHIO that leverages two pruning rules based on a novel distance measure. These rules enable us to prune many inferior candidate locations prior to influence computation, paving the way to efficient and accurate solution. Furthermore, we extend PINOCCHIO (PINOCCHIO-VO) by incorporating two optimization strategies during candidate validation phase, which further reduce unnecessary computations. Experimental study over two real-world datasets demonstrates superiority of our framework in comparison to state-of-the-art LS techniques.