Aggregate Farthest Neighbor Queries Over Spatial Data

In this paper, we study a new type of spatial query, namely aggregate k farthest neighbor (AkFN) search. Given a data point set P, a query point set Q, AkFN query returns k points in P with the largest aggregate distances to all points in Q. For instance, it is reasonable to open a new hotel where the aggregate distances to all existing hotels are maximized.Our investigation of the AkFN query focuses on three aggregate functions, Sum, Max and Min. Assuming data set is indexed by R-tree and the query set fit in memory, we propose two algorithms for solving all three kinds of AkFN efficiently, minimum bounding (MB) algorithm and best first (BF) algorithm, which is incremental and 10 optimal. Moreover, we develop novel convex hull based (CHB) algorithm for both SUM and MAX aggregate functions by utilizing the convex hull of data set. When the query set becomes very large and disk resident, we extend the algorithms above to disk minimum bounding (DMB) algorithm, disk best first (DBF) algorithm and disk convex hull based (DCHB) algorithm, respectively.Extensive experiments on both synthetic and real data sets confirm the efficiency and effectiveness of our proposed algorithms. The BF algorithm is the best under almost all circumstance.