This paper addresses the problem of searching the k aggregate farthest neighbours (AkFN query in short) on road networks. Given a query point set, AkFN is aimed at finding the top-k points from a dataset with the largest aggregate network distance. The challenge of the AkFN query on the road network is how to reduce the number of network distance evaluation which is an expensive operation. In our work, we propose a three-phase solution, including clustering points in dataset, network distance bound pre-computing and searching. By organizing the objects into compact clusters and pre-calculating the network distance bound from clusters to a set of reference points, we can effectively prune a large fraction of clusters without probing each individual point inside. Finally, we demonstrate the efficiency of our proposed approaches by extensive experiments on a real Point- of-Interest (POI) dataset.
展开▼
