Nearest Neighbor Queries in Shared-Nothing Environments |
| |
Authors: | Apostolos Papadopoulos Yannis Manolopoulos |
| |
Affiliation: | (1) Department of Informatics, Aristotle University, Thessaloniki, 54006, Greece |
| |
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. |
| |
Keywords: | spatial databases nearest neighbor search distributed/parallel databases R-trees performance evaluation |
本文献已被 SpringerLink 等数据库收录! |
|