Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model

Takashi ISHIMIZU; Akihiro FUJIWARA; Michiko INOUE; Toshimitsu MASUZAWA; Hideo FUJIWARA

Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model

Takashi ISHIMIZU, Akihiro FUJIWARA, Michiko INOUE, Toshimitsu MASUZAWA, Hideo FUJIWARA

Full Text Views

0

Cite this

Summary :

In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n n binary image on the Bulk-Synchronous Parallel(BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for L_p distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n²/p + L) computation time and in O(g(n/p) + L) communication time using p (1 p n) processors and in O(n²/p + (d+L)(log(p/n)/log(d+1))) computation time and in O(g(n/p) + (gd+L)(log(p/n)/log(d+1))) communication time using p (n< p n²) processors on the BSP model, for any integer d(1 dp/n).

Publication: IEICE TRANSACTIONS on Information Vol.E83-D No.2 pp.151-158

Publication Date: 2000/02/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms

Cite this

Copy

Takashi ISHIMIZU, Akihiro FUJIWARA, Michiko INOUE, Toshimitsu MASUZAWA, Hideo FUJIWARA, "Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model" in IEICE TRANSACTIONS on Information, vol. E83-D, no. 2, pp. 151-158, February 2000, doi: .
Abstract: In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n n binary image on the Bulk-Synchronous Parallel(BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for L_p distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n²/p + L) computation time and in O(g(n/p) + L) communication time using p (1 p n) processors and in O(n²/p + (d+L)(log(p/n)/log(d+1))) computation time and in O(g(n/p) + (gd+L)(log(p/n)/log(d+1))) communication time using p (n< p n²) processors on the BSP model, for any integer d(1 dp/n).
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_2_151/_p

Copy

@ARTICLE{e83-d_2_151,
author={Takashi ISHIMIZU, Akihiro FUJIWARA, Michiko INOUE, Toshimitsu MASUZAWA, Hideo FUJIWARA, },
journal={IEICE TRANSACTIONS on Information},
title={Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model},
year={2000},
volume={E83-D},
number={2},
pages={151-158},
abstract={In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n n binary image on the Bulk-Synchronous Parallel(BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for L_p distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n²/p + L) computation time and in O(g(n/p) + L) communication time using p (1 p n) processors and in O(n²/p + (d+L)(log(p/n)/log(d+1))) computation time and in O(g(n/p) + (gd+L)(log(p/n)/log(d+1))) communication time using p (n< p n²) processors on the BSP model, for any integer d(1 dp/n).},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
T2 - IEICE TRANSACTIONS on Information
SP - 151
EP - 158
AU - Takashi ISHIMIZU
AU - Akihiro FUJIWARA
AU - Michiko INOUE
AU - Toshimitsu MASUZAWA
AU - Hideo FUJIWARA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2000
AB - In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n n binary image on the Bulk-Synchronous Parallel(BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for L_p distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n²/p + L) computation time and in O(g(n/p) + L) communication time using p (1 p n) processors and in O(n²/p + (d+L)(log(p/n)/log(d+1))) computation time and in O(g(n/p) + (gd+L)(log(p/n)/log(d+1))) communication time using p (n< p n²) processors on the BSP model, for any integer d(1 dp/n).
ER -