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)

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 (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
Pages76
Number of pages1
Volume2006
DOIs
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

Conference

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

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Cite this