Parallel processing of nearest neighbor queries in declustered spatial data
Apostolos N. Papadopoulos, Y. Manolopoulos · 1996
In this paper, we propose an &cient solution to the problem of nearest neighbor query processing in decluste red spatial data. Recently a branch-and-bound nearest neighbor finding (BB-NNF) algorithm has been designed to process nearest neighbor queries in R-trees. However, this algorithm is strictly serial (branch-and-bound oriented) and its performance degrades if applied to a parallel environment, since it does not exploit any kind of parallelization. We develop an eEicient query processing strategy tir parallel nearest neighbor finding (P-NNF), assuming a shared nothing multi-processor architecture, where the processors i communicate via a network. In our method, the relevant : sites are activated simultaneously. In order to achieve this goal, statistical information is used. The dTiciency mcasurc is the response time of a given query. E2cperimental results, based on real-life and synthetic datasets, show that the proposed method outperforms the branch-andbound method by factors. We focus on Zd space but generalizations to higher dimensions are straightforward.