Geodesic
Parallel algorithm of geometrical hashing based on NumPy package and processes pool
Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 4 (2015), pp. 13-23

Voir la notice de l'article provenant de la source Math-Net.Ru

The article considers the problem of multi-dimensional geometric hashing. The paper describes a mathematical model of geometric hashing and considers an example of its use in localization problems for the point. A method of constructing the corresponding hash matrix by parallel algorithm is considered. In this paper an algorithm of parallel geometric hashing using a development pattern “pool processes” is proposed. The implementation of the algorithm is executed using the Python programming language and NumPy package for manipulating multidimensional data. To implement the process pool it is proposed to use a class Process Pool Executor imported from module concurrent.futures, which is included in the distribution of the interpreter Python since version 3.2. All the solutions are presented in the paper by corresponding UML class diagrams. Designed GeomNash package includes classes Data, Result, GeomHash, Job. The results of the developed program presents the corresponding graphs. Also, the article presents the theoretical justification for the application process pool for the implementation of parallel algorithms. It is obtained condition $$ t_2 > \frac{p}{p-1} t_1 $$ of the appropriateness of process pool. Here $t_1$—the time of transmission unit of data between processes, and $t_2$—the time of processing unit data by one processor.
Keywords: hashing, process pool, package NumPy, computational geometry, parallel algorithm. 
@article{VVGUM_2015_4_a2,
     author = {V. A. Klyachin},
     title = {Parallel algorithm of geometrical hashing based on {NumPy} package and processes pool},
     journal = {Matemati\v{c}eska\^a fizika i kompʹ\^uternoe modelirovanie},
     pages = {13--23},
     publisher = {mathdoc},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VVGUM_2015_4_a2/}
}
TY  - JOUR
AU  - V. A. Klyachin
TI  - Parallel algorithm of geometrical hashing based on NumPy package and processes pool
JO  - Matematičeskaâ fizika i kompʹûternoe modelirovanie
PY  - 2015
SP  - 13
EP  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VVGUM_2015_4_a2/
LA  - ru
ID  - VVGUM_2015_4_a2
ER  - 
%0 Journal Article
%A V. A. Klyachin
%T Parallel algorithm of geometrical hashing based on NumPy package and processes pool
%J Matematičeskaâ fizika i kompʹûternoe modelirovanie
%D 2015
%P 13-23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VVGUM_2015_4_a2/
%G ru
%F VVGUM_2015_4_a2
V. A. Klyachin. Parallel algorithm of geometrical hashing based on NumPy package and processes pool. Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 4 (2015), pp. 13-23. http://geodesic.mathdoc.fr/item/VVGUM_2015_4_a2/