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/

[1] Microsoft Academy: Parallel computing and multi-thread programming. Lecture 7: Thread Pool and Parallel Tasks Library, , Title from screen http://www.intuit.ru/studies/courses/10554/1092/lecture/21509

[2] P.\;N. Babishchevich, Computational methods in practice, LENAND Publ., M., 2015, 320 pp.

[3] V.\;P. Gergel, Theory and practice of parallel calculations, Internet-Universitet Informatsionnykh tekhnologiy; BINOM. Laboratoriya znaniy Publ., M., 2007, 423 pp.

[4] Yu.\;B. Gritsenko, V.\;Yu. Vishnyakov, S.\;S. Oshchepkov, “Addressing update spatial data in Oracle Spatial”, Dokl. TUSURa. Upravlenie, vychislitelnaya tekhnika i informatika, 2008, no. 2 (18), 76–79

[5] V.\;A. Klyachin, “Optimization of Calculus Mesh for Cryobiology Problem Based on Multidimensional Hashing Using NumPy”, Izv. Sarat. un-ta. Novaya seriya. Seriya Matematika. Mekhanika. Informatika, 14:3 (2014), 355–362

[6] Mathematical Python, , Title from screen http://jenyay.net/Programming/PyMath

[7] D.\;N. Nikolskiy, “Development of software for the numerical solution of the evolution of the interface between different fluids in porous media complex geological structure using the package NumPy”, Scientific notes of Oryol State University. Series: natural, technical and medical sciences, 2012, no. 6-1, 42–47

[8] T. Olifant, “Multidimensional iterators NumPy”, Beautiful Code, Piter Publ., SPb., 2011, 341–358

[9] F. Preparata, M. Sheymos, Computational geometry, Nauka Publ., M., 1989, 478 pp. | MR

[10] Pool of managed threads. MSDN—Microsoft, , Title from screen https://msdn.microsoft.com/ru-ru/library/0ka9477y(v=vs.110).aspx

[11] M. Sammerfild, Python in practice, DMK Press Publ., M., 2014, 338 pp.

[12] A.\;V. Skvortsov, N.\;S. Mirza, Analisys and algorithms of triangulations, Izd-vo Tom. un-ta Publ., Tomsk, 2006, 168 pp.

[13] E.\;V. Shikin, A.\;V. Boreskov, Computrer graphics. Polygon models, DIALOG-MIFI Publ., M., 2001, 464 pp.

[14] M. Ling, L. Yumin, J. Huiqin, W. Zhongyong, Z. Haofei, “An Improved Method of Geometric Hashing Pattern Recognition”, I. J. Modern Education and Computer Science, 3:3 (2011), 1–7 | DOI

[15] A.\;S. Mian, M. Bennamoun, R. Owens, “Three-dimensional model-based object recognition and segmentation in cluttered scenes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28:10 (2006), 1584–1601 | DOI

[16] Thread pool pattern, , Title from screen http://en.wikipedia.org/wiki/Thread_pool_pattern

[17] H.\;J. Wolfson, I. Rigoutsos, “Geometric Hashing: An Overview”, IEEE Computational Science and Engineering, 4:4 (1997), 10–21 | DOI