loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
22nd International Conference on Data Engineering (ICDE'06)
Reverse Nearest Neighbors Search in Ad-hoc Subspaces
Atlanta, Georgia
April 03-April 07
ISBN: 0-7695-2570-9
Man Lung Yiu, University of Hong Kong
Nikos Mamoulis, University of Hong Kong
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.
Citation:
Man Lung Yiu, Nikos Mamoulis, "Reverse Nearest Neighbors Search in Ad-hoc Subspaces," icde, pp.76, 22nd International Conference on Data Engineering (ICDE'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.