HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Multi-dimensional reverse kNN search
Authors: Papadias, Dimitris
Tao, Yufei
Lian, Xiang
Xiao, Xiaokui
Keywords: Spatial databases
Reverse nearest neighbors
Issue Date: 2007
Citation: The VLDB journal : the international journal on very large data bases, July 2007, v.16, no. 3, p. 293-316
Abstract: 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
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
VLDBJ07RNN1.pdfpre-published version531KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.