Processing Global Nearest Neighbor Query

This paper presented a new kind of query, global nearest neighbors query, which is based on a special distance, global distance, between two objects during given time interval. According to the relationship with continuous nearest neighbor query, a native algorithm is proposed. In terms of the mobility of data set, global distances at different situation are refined and some heuristics are presented for data set indexed by data structure of R tree family. Based on branch and bound technique and proposed pruning, updating and visiting heuristics, recursive depth-first and heap-based best- first query processing algorithms are developed for both cases. An extensive study based on experiments performed with synthetic data sets shows that the best- first algorithms outperform the depth-first algorithms.