Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3246

Multi-dimensional reverse kNN search

Authors Papadias, Dimitris
Tao, Yufei
Lian, Xiang
Xiao, Xiaokui
Issue Date 2007
Source The VLDB journal : the international journal on very large data bases , v.16, (3), 2007, July , 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.
Subjects
Rights The original publication is available at http://www.springerlink.com/
Language English
Format Article
Access Find@HKUST
Files in this item:
File Description Size Format
VLDBJ07RNN1.pdf pre-published version 544305 B Adobe PDF