ERkNN: Efficient Reverse k-Nearest Neighbors Retrieval with Local kNN-Distance Estimation
No Thumbnail Available
Date
2006-07-31T09:01:26Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Algorithms, Performance, Design, Experimentation