Talk: [Overview] [Papers and Talks] [Source Code] [Dataset] [Contacts]
Given a set of points P and a query point q, the reverse furthest neighbor (rfn) query fetches the set of points p \in P such that q is their furthest neighbor among all points in P \cup {q}. This is the monochromatic rfn (mrfn) query. Another interesting version of rfn query is the bichromatic reverse furthest neighbor (brfn) query. Given a set of points P, a query set Q and a query point q \in Q, a brfn query fetches the set of points p \in P such that q is the furthest neighbor of p among all points in Q. The rfn query has many interesting applications in spatial databases and beyond. For instance, given a large residential database (as P) and a set of potential sites (as Q) for building a chemical plant complex, the construction site should be selected as the one that has the maximum number of reverse furthest neighbors. This is an instance of the brfn query. This paper presents the challenges associated with such queries and proposes efficient, R-tree based algorithms for both monochromatic and bichromatic versions of the trfn queries. We analyze properties of the rfn query that differentiate it from the widely studied reverse nearest neighbor queries and enable the design of novel algorithms. Our approach takes advantage of the furthest Voronoi diagrams as well as the convex hulls of either the data set P (in the mrfn case) or the query set Q (in the brfn case). For the brfn queries, we also extend the analysis to the situation when Q is large in size and becomes disk-resident. Experiments on both synthetic and real data sets confirm the efficiency and scalability of proposed algorithms over the brute-force search based approach.
1. Reverse Furthest Neighbors in Spatial Databases,
Full version:
Talk:
Important Notice
Please cite our paper if you use this library for your work. Thanks!
If you find any bugs or any suggestions/comments, we are very happy to hear from you!
Library Description
The library is developed in GNU C++. For installation and usage, please refer to the README files in the subfolders. Before compilation you must install another two libraries: CGAL and CORESET.
Download
Reverse Furthest Neighbors in Spatial Databases Library [tar.gz]
We have generated and experimented with the datasets described in the paper. For real data sets, please follow the description in our paper. In the source-code released above, it also contains the generator for the synthetic data sets.
