Efficient reverse k-nearest neighbor estimation |
| |
Authors: | Elke Achtert Christian B?hm Peer Kr?ger Peter Kunath Alexey Pryakhin and Matthias Renz |
| |
Institution: | (1) Institute for Computer Science, Ludwig-Maximilians-Universit?t M?nchen, Oettingenstr. 67, 80538 Munich, Germany; |
| |
Abstract: | The reverse k-nearest neighbor (RkNN) problem, i.e. finding all objects in a data set the k-nearest
neighbors of which include a specified query object, has received increasing attention recently. Many
industrial and scientific applications call for solutions of the RkNN problem in arbitrary metric spaces
where the data objects are not Euclidean and only a metric distance function is given for specifying
object similarity. Usually, these applications need a solution for the generalized problem where the
value of k is not known in advance and may change from query to query. In addition, many applications
require a fast approximate answer of RkNN-queries. For these scenarios, it is important to generate
a fast answer with high recall. In this paper, we propose the first approach for efficient approximative
RkNN search in arbitrary metric spaces where the value of k is specified at query time. Our approach
uses the advantages of existing metric index structures but proposes to use an approximation of the
nearest-neighbor-distances in order to prune the search space. We show that our method scales significantly
better than existing non-approximative approaches while producing an approximation of the true query
result with a high recall. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|