|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/3246
|
| 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 http://www.springerlink.com/ |
| URI: | http://hdl.handle.net/1783.1/3246 |
| Appears in Collections: | CSE Journal/Magazine Articles
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| VLDBJ07RNN1.pdf | pre-published version | 531Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
