摘要
An aggregate nearest neighbor （ANN） query returns a point of interest （POI） that minimizes an aggregate function for multiple query points. In this paper, we propose an e？cient approach to tackle ANN queries in road networks. Our approach consists of two phases： searching phase and pruning phase. In particular, we first continuously compute the nearest neighbors （NNs） for each query point in some specific order to obtain the candidate POIs until all query points find a common POI. Second, we filter out the unqualified POIs based on the pruning strategy for a given aggregate function. The two-phase process is repeated until there remains only one candidate POI, and the remained one is returned as the final result. In addition, we discuss the partition strategies for query points and the approximate ANN query for the case where the number of query points is huge. Extensive experiments using real datasets demonstrate that our proposed approach outperforms its competitors significantly in most cases.
An aggregate nearest neighbor （ANN） query returns a point of interest （POI） that minimizes an aggregate function for multiple query points. In this paper, we propose an e？cient approach to tackle ANN queries in road networks. Our approach consists of two phases： searching phase and pruning phase. In particular, we first continuously compute the nearest neighbors （NNs） for each query point in some specific order to obtain the candidate POIs until all query points find a common POI. Second, we filter out the unqualified POIs based on the pruning strategy for a given aggregate function. The two-phase process is repeated until there remains only one candidate POI, and the remained one is returned as the final result. In addition, we discuss the partition strategies for query points and the approximate ANN query for the case where the number of query points is huge. Extensive experiments using real datasets demonstrate that our proposed approach outperforms its competitors significantly in most cases.
基金
This research is supported in part by the Shanghai Natural Science Foundation of China under Grant No. 14ZR1403100, the Shanghai Science and Technology Development Funds of China under Grant Nos. 13dz2260200 and 13511504300, and the National Natural Science Foundation of China under Grant No. 61073001.
