Citations
Altmetric:
Alternative Title
Abstract
The Reverse k-Nearest Neighbors (RkNN) queries are important in profile-based marketing, information retrieval, decision support and data mining systems. However, they are very expensive and existing algorithms are not scalable to queries in high dimensional spaces or of large values of k. This paper describes an efficient estimation-based RkNN search algorithm (ERkNN) which answers RkNN queries based on local kNN-distance estimation methods. The proposed approach utilizes estimation-based filtering strategy to lower the computation cost of RkNN queries. The results of extensive experiments on both synthetic and real life datasets demonstrate that ERkNN algorithm retrieves RkNN efficiently and is scalable with respect to data dimensionality, k, and data size. Copyright 2005 ACM.
Keywords
KNN distance estimation, Reverse k-nearest neighbours
Source Title
International Conference on Information and Knowledge Management, Proceedings
Publisher
Series/Report No.
Collections
Rights
Date
2005
DOI
Type
Conference Paper