School of Computing

Permanent URI for this community

https://dl.comp.nus.edu.sg/handle/1900.100/1

Browse

Browsing School of Computing by Subject "Performance"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    ERkNN: Efficient Reverse k-Nearest Neighbors Retrieval with Local kNN-Distance Estimation
    (2006-07-31T09:01:26Z) XIA, Chenyi; HSU, Wynne; LEE, Mong Li
    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.