Reverse nearest neighbors search in ad hoc subspaces

Man Lung Yiu, Nikos Mamoulis

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)

Abstract

Given an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes), We consider a suitable storage scheme and develop appropriate algorithms for projected RNN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and RNN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data.
Original languageEnglish
Pages (from-to)412-426
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume19
Issue number3
DOIs
Publication statusPublished - 1 Mar 2007
Externally publishedYes

Keywords

  • Distributed databases
  • Query processing
  • Spatial databases

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Reverse nearest neighbors search in ad hoc subspaces'. Together they form a unique fingerprint.

Cite this