Abstract
Finding the nearest neighbors and finding the farthest neighbors are fundamental problems in spatial databases. Consider two sets of data points in a two-dimensional data space, which represent a set of favor locations F, such as libraries and schools, and a set of disfavor locations D, such as dumps and gambling houses. Given another set of data points C in this space as houses for rent, one who needs to rent a house may need a recommendation which takes into account the favor and disfavor locations. To solve this problem, a new two-dimensional data space is employed, in which dimension X describes the distance from a data point c in C to its nearest neighbor in D and dimension Y describes the distance from c to its farthest neighbor in F. Notice that the larger value is preferred in dimension X while the smaller value is preferred in dimension Y. Following the above dominance rule, the recommendation for the house renting can be achieved by a skyline query. A naïve method to processing this query is 1) to find the nearest neighbor from D and the farthest neighbor from F for each data point in C and then 2) to construct a new two-dimensional data space based on the results from 1) and to apply any of the existing skyline algorithms to get the answer. In this paper, based on the quad-tree index, we propose an efficient algorithm to answer this query by combining the above two steps. A series of experiments with synthetic data and real data are performed to evaluate this approach and the experiment results demonstrate the efficiency of the approach. Copyright 2014 ACM.