Abstract
In recent years, the reverse k-nearest neighbor (RkNN) problem in metric spaces has attracted reasonable attention because it can be applied to business location planning, profile-based marketing, clustering and outlier detection. However, previous works on the RkNN problem in metric spaces cannot allow users to assign different distance functions for distinct queries. In this thesis, we define the problem on RkNN query with adjustable functions. That is, for each distinct query, it can have its own distance function. To the best of our knowledge, this thesis is the first work solving the problem of RkNN with adjustable distances in metric spaces. We propose a generic framework to handle the RkNN queries with different distance functions. In our framework, a new index structure is built by using multiple distance functions. Therefore, some pruning rules determined by calculating the correlation between the distance function assigned by the user and those used to build the index structure can be provided to prune the irrelevant data points and then, the remainder candidates are really checked to see whether they are real results. The correctness of our pruning strategies is proved and the experiment results demonstrate the efficiency and effectiveness of our approach.