HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: Reverse kNN search arbitrary dimensionality
Authors: Tao, Yufei
Papadias, Dimitris
Lian, Xiang
Keywords: Reverse nearest neighbors
Arbitrary dimensionality
Dynamic multidimensional datasets
Issue Date: Aug-2004
Citation: Proceedings of the Very Large Data Bases Conference, Aug. 30-Sept. 3, 2004, Toronto, Canada, p. 744-755
Abstract: Given a 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: (i) they do not support arbitrary values of k (ii) they cannot deal efficiently with database updates, (iii) they are applicable only to 2D data (but not to higher dimensionality), and (iv) they retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact processing of RkNN with arbitrary values of k on dynamic multidimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. In addition to their flexibility, we experimentally verify that the proposed algorithms outperform the existing ones even in their restricted focus.
Rights: The original publication is available at
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
VLDB04RNN.pdfpre-published version231KbAdobe PDFView/Open

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