Reverse nearest neighbors search in ad-hoc subspaces

Man Lung Yiu, Nikos Mamoulis

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

20 Citations (Scopus)


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 (i) the dimensionality might be too high for the result of a regular RNN query to be useful, (ii) missing values may implicitly define a meaningful subspace for RNN retrieval, and (iii) 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. Our methods are experimentally evaluated with real and synthetic data.
Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Data Engineering, ICDE '06
Number of pages1
Publication statusPublished - 17 Oct 2006
Externally publishedYes
Event22nd International Conference on Data Engineering, ICDE '06 - Atlanta, GA, United States
Duration: 3 Apr 20067 Apr 2006


Conference22nd International Conference on Data Engineering, ICDE '06
Country/TerritoryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


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

Cite this