Balanced Nearest Neighborhood Query in Spatial Database

摘要

In the spatial database, given a data set P of points, a query point q, the Nearest Neighborhood Query (NNH) retrieves the nearest group of points (i.e, a cluster) from P, where the group is assigned with a fixed scale. NNH is an important query processing problem, and it can be applied to many applications such as point of interests (POI) and location-based services (LBS). However, we observe that NNH requires a fixed scale of candidate groups. It is an unrealistic setting that all candidate groups have the same size. Moreover, fixing the scale also leads to the cases that NNH returns an empty result, which certainly restricts its application. In this paper, to make a general and realistic neighborhood retrieval, we propose a novel query problem named Balanced Nearest Neighborhood query (BNNH). In BNNH, we allow the flexible scale of candidate groups hence guarantee a non-empty result. We also indicate that users' preferences should be taken into consideration as well when comparing clusters with different locations and scales. BNNH query carries out a balancing function to evaluate clusters with users' preferences, and returns a more appropriate neighborhood. We also proposed two solutions for efficient processing of BNNH query. We conduct sufficient experiments to confirm the superiorities of our proposed solutions.