Please use this identifier to cite or link to this item:

Multi-dimensional reverse kNN search

Authors Tao, Yufei
Papadias, Dimitris View this author's profile
Lian, Xiang HKUST affiliated (currently or previously)
Xiao, Xiaokui
Issue Date 2007
Source The VLDB journal , v.16, (3), 2007, p. 293-316
Summary Given a multi-dimensional point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: they (i) do not support arbitrary values of k, (ii) cannot deal efficiently with database updates, (iii) are applicable only to 2D data but not to higher dimensionality, and (iv) retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact RkNN processing with arbitrary values of k on dynamic, multi-dimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. As a second step, we extend the proposed techniques to continuous RkNN search, which returns the RkNN results for every point on a line segment. We evaluate the effectiveness of our algorithms with extensive experiments using both real and synthetic datasets.
Rights The original publication is available at
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science
Files in this item:
File Description Size Format
VLDBJ07RNN1.pdf pre-published version 544305 B Adobe PDF