Social influence-aware reverse nearest neighbor search

Hui Ju Hung, De Nian Yang, Wang Chien Lee

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 of geographical proximity and social 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 on Targeted Region (TR)-Oriented and RNN-Oriented processing 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.

Original languageEnglish (US)
Article numbera12
JournalACM Transactions on Spatial Algorithms and Systems
Issue number3
StatePublished - Sep 2016

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Modeling and Simulation
  • Computer Science Applications
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Social influence-aware reverse nearest neighbor search'. Together they form a unique fingerprint.

Cite this