Social Influence-Aware Reverse Nearest Neighbor Search
Authors:
Open Access
- 10 October 2016
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Spatial Algorithms and Systems
- Vol. 2 (3) , 1-35
Abstract
Business-location planning, critical to the success of many businesses, can be addressed by the reverse nearest neighbors (RNN) query using geographical proximity to the customers as the main metric to find a store location close 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 article, we propose a framework for business-location planning that takes into account both factors ofgeographical proximityandsocial influence. An essential task in this framework is to compute the “influence spread” of RNNs for candidate locations. Here, the influence spread refers to the number of people influenced via the word-of-mouth effect. To alleviate the excessive computational overhead and long latency in the framework, we trade storage overhead for processing speed by precomputing and storing the social influence between pairs of customers. Based onTargeted Region (TR)-OrientedandRNN-Orientedprocessing strategies, we develop two suites of algorithms that incorporate various efficient pruning and segmentation techniques to enhance our framework. Experiments validate our ideas and evaluate the efficiency of the proposed algorithms over various parameter settings. The experimental results show that (a) TR-oriented and RNN-oriented processing are feasible for supporting the task of location planning; (b) RNN-oriented processing is more efficient than TR-oriented processing; and (c) the optimization technique that we developed significantly improves the efficiency of RNN-oriented and TR-oriented processing.Keywords
This publication has 56 references indexed in Scilit:
- Maximizing Social Influence in Nearly Optimal Time2013
- A 61-million-person experiment in social influence and political mobilizationNature, 2012
- Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model2012
- Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate2011
- Prediction of Information Diffusion Probabilities for Independent Cascade Model2008
- Nearest and reverse nearest neighbor queries for moving objectsThe VLDB Journal, 2006
- Influence sets based on reverse nearest neighbor queriesACM SIGMOD Record, 2000
- RURAL RETAIL BUSINESS THRESHOLDS AND INTERDEPENDENCIES*Journal of Regional Science, 1996
- R-treesACM SIGMOD Record, 1984
- Estimation of super market drawing power: An extension of location theory and practiceThe Annals of Regional Science, 1971