Top-k most influential location selection

We propose and study a new type of facility location selection query, the top-k most influential location selection query. Giv-en a set M of customers and a set F of existing facilities, this query finds k locations from a set C of candidate locations with the largest influence values, where the influence of a candidate lo-cation c (c ∈ C) is defined as the number of customers inM who are the reverse nearest neighbors of c. We first present a naive algo-rithm to process the query. However, the algorithm is computation-ally expensive and not scalable to large datasets. This motivates us to explore more efficient solutions. We propose two branch and bound algorithms, the Estimation Expanding Pruning (EEP) algo-rithm and the Bounding Influence Pruning (BIP) algorithm. These algorithms exploit various geometric properties to prune the search space, and thus achieve much better performance than that of th