On multi-type reverse nearest neighbor search

Xiaobin Ma, Chengyang Zhang, Shashi Shekhar, Yan Huang, Hui Xiong

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


This paper presents a study of the Multi-Type Reverse Nearest Neighbor (MTRNN) query problem. Traditionally, a reverse nearest neighbor (RNN) query finds all the objects that have the query point as their nearest neighbor. In contrast, an MTRNN query finds all the objects that have the query point in their multi-type nearest neighbors. Existing RNN queries find an influence set by considering only one feature type. However, the influence from multiple feature types is often critical for strategic decision making in many business scenarios, such as site selection for a new shopping center. To that end, we first formalize the notion of the MTRNN query by considering the influence of multiple feature types. We also propose R-tree based algorithms to find the influence set for a given query point and multiple feature types. Finally, experimental results are provided to show the strength of the proposed algorithms as well as design decisions related to performance tuning.

Original languageEnglish (US)
Pages (from-to)955-983
Number of pages29
JournalData and Knowledge Engineering
Issue number11
StatePublished - Nov 1 2011


  • Location-based service
  • Reverse nearest neighbor search
  • Spatial database

Fingerprint Dive into the research topics of 'On multi-type reverse nearest neighbor search'. Together they form a unique fingerprint.

Cite this