Reverse nearest neighbors in large graphs

Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis, Yufei Tao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

80 Citations (Scopus)

Abstract

A reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph.
Original languageEnglish
Pages (from-to)540-553
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume18
Issue number4
DOIs
Publication statusPublished - 1 Apr 2006
Externally publishedYes

Keywords

  • Graphs and networks
  • Query processing
  • Spatial databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this