ISSN:
1573-7624
Keywords:
spatial databases
;
nearest neighbor search
;
distributed/parallel databases
;
R-trees
;
performance evaluation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Geography
Notes:
Abstract In this paper, we propose an efficient solution to the problem of nearest neighbor query processing in declustered spatial databases. 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, during processing of a nearest neighbor query, if applied to a parallel environment, since it does not exploit any kind of parallelization. We develop an efficient query processing strategy for parallel nearest neighbor finding (P-NNF), assuming a shared nothing multi-processor architecture, where the processors communicate via a network. In our method, the relevant sites are activated simultaneously. In order to achieve this goal, statistical information is used. The efficiency measure is the response time of a given query. Experimental results, based on real-life and synthetic datasets, show that the proposed method outperforms the branch-and-bound method by factors.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009758427967
Permalink