Social influence-aware reverse nearest neighbor search

Business location planning, critical to success of many businesses, can be addressed by reverse nearest neighbors (RNN) query using geographical proximity to the customers as the main metric to find a store location which is the closest to many customers. Nevertheless, we argue that other marketing factors such as social influence could be considered in the process of business location planning. In this paper, we propose a framework for business location planning that takes into account both factors of geographical proximity and social influence. An essential task in this framework is to compute the “influence spread” of RNNs for candidate locations. However, excessive computational overhead and long latency hinder its feasibility for our framework. Thus, we trade storage overhead for the processing speed by precomputing and storing the social influences between pairs of customers and design a suite of algorithms based on Targeted Region-oriented strategy. Various ordering and pruning techniques have been incorporated in these algorithms to enhance the processing efficiency of our framework. Experiments also show that the proposed algorithms efficiently support the task of location planning under various parameter settings.