2006 | OriginalPaper | Buchkapitel
Efficient Parallel Processing for K-Nearest-Neighbor Search in Spatial Databases
verfasst von : Yunjun Gao, Ling Chen, Gencai Chen, Chun Chen
Erschienen in: Computational Science and Its Applications - ICCSA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Even though the problem of
k
nearest neighbor (
k
NN) query is well-studied in serial environment, there is little prior work on parallel
k
NN search processing in parallel one. In this paper, we present the first Best-First based Parallel
k
NN (BFP
k
NN) query algorithm in a multi-disk setting, for efficient handling of
k
NN retrieval with arbitrary values of
k
by parallelization. The core of our method is to access more entries from multiple disks simultaneously and enable several effective pruning heuristics to discard non-qualifying entries. Extensive experiments with real and synthetic datasets confirm that BFP
k
NN significantly outperforms its competitors in both efficiency and scalability.