Determination of the Shortest Hamiltonian Paths in an Arbitrary Graph of Distributed Databases
https://doi.org/10.32362/2500-316X-2019-7-4-7-20
Abstract
A method has been developed for finding the shortest Hamiltonian path in an arbitrary graph based on the rank approach, which provides high efficiency and a significant reduction in the error in solving the problem of organizing the process of managing multiple transactions and queries when they are implemented in network databases. In many cases, existing solutions do not provide the necessary results in terms of access time and accuracy of the found solution. Using the developed method allows minimizing the idle time of computing devices, reducing the volume and time of data transfer from one device to another, increases overall scalability, minimizes data access time, etc. An important advantage of the proposed method is to reduce the number of elementary operations and the number of vectors being processed the queue of the operations of the request, which leads to a significant reduction in time to implement the procedures for the formation of echer di operations in the requests. Methods of graph theory were used in this paper. The effectiveness of the task solution was evaluated using a systems approach, system analysis and the theory of operations research. Processing of experimental data obtained during the work was carried out in accordance with the provisions of mathematical statistics.
About the Authors
E. G. Andrianova
MIREA – Russian Technological University
Russian Federation
Russian Federation
Cand. of Sci. (Engineering), Associate Professor of the Chair of Corporate Information Systems, Institute of Information Technology,
78, Vernadskogo pr., Moscow 119454, Russia
Scopus author ID 57200555430
ResearcherID T-7908-2018,
V. K. Raev
MIREA – Russian Technological University
Russian Federation
Russian Federation
Dr. of Sci. (Engineering), Professor of the Chair of Instrumental and Applied Software, Institute of Information Technology
78, Vernadskogo pr., Moscow 119454, Russia
D. I. Filgus
MIREA – Russian Technological University
Russian Federation
Russian Federation
Postgraduate Student of the Chair of Instrumental and Applied Software, Institute of Information Technology
78, Vernadskogo pr., Moscow 119454, Russia
References
1. Filgus D.I., Andrianova E.G., Raev V.K. Development of parallel computing methods for fragmentation of network database data based on the rank approach. Cloud of Science. 2018; 5(3):532-559, (in Russ.). URL: https://cloudofscience.ru/sites/default/files/pdf/CoS_5_532.pdf
2. Abbasov M. Optimization Methods. St. Petersburg: «VVM» Publ., 2014. 64 p., (in Russ.).
3. Listrovoy S.V., Golubnichiy D.Y, Listrovaya E.S. Solutioon Method for the linear programming problems with boolean variables. Engineering Simulation. 1999; 16(6): 707-725.
4. Buy D.B., Skobelev V.G. Models, methods and algorithms for query optimization in databases (a survey). Радіоелектронні і комп’ютерні системи [Radioelectronic and Computer Systems]. 2014; 2 (66):43-58 (in Russ.). http://nbuv.gov.ua/UJRN/recs_2014_2_8
5. Listrovoy S.V., Tretiak V.F., Listrovaya E.S. Parallel algorithms of calculation process optimization for the boolean programming problems. Engineering Simulation. 1999; 16(5):569-579.
6. Berdnikov V.P. Modified algorithm for determination of full stability areas in nonstationary nonlinear systems. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2018; 6(3):39-53, (in Russ.). https://doi.org/10.32362/2500-316X-2018-6-3-39-53
7. Fedorin A.N. Multi-criteria tasks of the backpack type: development and comparative analysis of algorithms: dis. ... Cand. of Sci. (Engineering). N.I. Lobachevsky Nizhny Novgorod: Nizhny Novgorod State University, 2010. 132 p., (in Russ.).
8. Pastushkov A.A., Batovrin V.K. Selection of solutions for designing open systems based on analysis of variants with random weights. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2018; 6(4):78-88, (in Russ.). https://doi.org/10.32362/2500-316X-2018-6-4-78-88/
9. Lyfar D.A. Parallel GPU algorithms of relational databases processing. Vestnik NGU. Seriya: Informatsionnye tekhnologii [Herald of NSU. Series: Information Technologies]. 2010; 8(4):72-80, (in Russ.). URI: http://www.nsu.ru/xmlui/handle/nsu/307
10. Gorobets V.V. Cloud model of on-line transaction processing system. Vestnik kompʼiuternykh i informatsionnykh tekhnologii [Herald of Computer and Information Technologies]. 2013; 4:19-24, (in Russ.).
11. Fralenko V.P., Agronik A.Yu. Tools, methods and algorithms for efficient parallelization of computational loading in heterogeneous environments. Programmnye sistemy: teoriya i primenenie [Program Systems: Theory and Applications]. 2015; 6(3(26)):73-92, (in Russ.). https://doi.org/10.25209/2079-3316-2015-6-3-73-92
12. Mendkovich N.A., Kuznetsov S.D. Overview of evolution of lexical query optimization techniques. Trudy Instituta sistemnogo programmirovaniya RAN [Proceedings of the Institute for System Programming RAS]. 2012; 23: 195-214, (in Russ.) https://doi.org/10.15514/ISPRAS-2012-23-12
13. Zhukov V.S. Study of methods for optimal placement of a database on nodes of a computer network. Siberian Journal of Life Sciences and Agriculture. 2010; 4(10):75-76, (in Russ.).
14. Listrovoy S.V., Minukhin S.V., Listrovaya E.S. Monitoring distributed computing systems on the basis of the determined shortest paths and shortest Hamiltonian cycles in a graph. Eastern-European Journal of Enterprise technologies. 2015; 6/4(78):32-4,. (in Russ.). https://doi.org/10.15587/1729-4061.2015.56247
15. Zambitsky D.K., Lozovanu D.D. Algorithms for solving optimization problems on networks. Chisinau:
16. Shtinitsa Publ., 1983. 116 p., (in Russ.).
17. Filgus D.I., Andrianova E.G., Raev V.K. Development of parallel computing methods for fragmentation of network database data based on the rank approach. Cloud of Science. 2018; 5(3):532-559, (in Russ.). URL: https://cloudofscience.ru/sites/default/files/pdf/CoS_5_532.pdf
18. Listrovoy S.V., Golubnichiy D.Y, Listrovaya E.S. Solutioon Method for the linear programming problems with boolean variables. Engineering Simulation. 1999; 16(6): 707-725.
19. Listrovoy S.V., Tretiak V.F., Listrovaya E.S. Parallel algorithms of calculation process optimization for the boolean programming problems. Engineering Simulation. 1999; 16(5):569-579.
20. Fedorin A.N. Multi-criteria tasks of the backpack type: development and comparative analysis of algorithms: dis. ... Cand. of Sci. (Engineering). N.I. Lobachevsky Nizhny Novgorod: Nizhny Novgorod State University, 2010. 132 p., (in Russ.).
21. Lyfar D.A. Parallel GPU algorithms of relational databases processing. Vestnik NGU. Seriya: Informatsionnye tekhnologii [Herald of NSU. Series: Information Technologies]. 2010; 8(4):72-80, (in Russ.). URI: http://www.nsu.ru/xmlui/handle/nsu/307
22. Fralenko V.P., Agronik A.Yu. Tools, methods and algorithms for efficient parallelization of computational loading in heterogeneous environments. Programmnye sistemy: teoriya i primenenie [Program Systems: Theory and Applications]. 2015; 6(3(26)):73-92, (in Russ.). https://doi.org/10.25209/2079-3316-2015-6-3-73-92
23. Zhukov V.S. Study of methods for optimal placement of a database on nodes of a computer network. Siberian Journal of Life Sciences and Agriculture. 2010; 4(10):75-76, (in Russ.).
Supplementary files
|
|
1. Fig.1. Short tree of all D paths of G(V, E) graph. | |
| Subject | ||
| Type | Research Instrument | |
View
(38KB)
|
Indexing metadata ▾ | |
Review
For citations:
Andrianova E.G., Raev V.K., Filgus D.I. Determination of the Shortest Hamiltonian Paths in an Arbitrary Graph of Distributed Databases. Russian Technological Journal. 2019;7(4):7-20. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-4-7-20
Views:
695
Email this article 