Abstract
A Reverse k-Nearest-Neighbors (RkNN) query retrieves the data points which take the query point as one of their k nearest neighbors. A bi-chromatic reverse k-nearest neighbor (BRkNN) query is a variant of the RkNN query, considering two types of data. Given two types of datasets S and C, a BRkNN query regarding a data point q in S retrieves the data points from C that regard q as one of their corresponding k-nearest neighbors on S. Many existing approaches answer the BRkNN query regarding a data point q in S individually. However, for the real applications, people may hope to find some points from S that maximize the cardinality of the union of their BRkNN answer sets. Here, we call this problem the coverage maximization on spatial databases considering BRkNN (the coverage maximization problem in short). Computing the BRkNN answer set for each point in S and then choosing some of them with the largest BRkNN answer sets for solving the maximization problem may cause poor quality, since the BRkNN answer sets of the data points in S may overlap. In this thesis, we design two heuristic approaches to solve this problem, considering different criteria on time efficiency and answer set quality. A series of experiments on synthetic and real datasets are performed to evaluate these two approaches.