Radiotekhnika
Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS


Тел.: +7 (495) 625-9241

 

Matching tables by graphs

DOI 10.18127/j19997493-201902-06

Keywords:

I.S. Druzhitsky – Undergraduate, Department «Software of Computer and Information Technologies», Bauman Moscow State Technical University
E-mail: idruzhitskiy@mail.ru
D.E. Bekasov – Senior Lecturer, Department «Software of Computer and Information Technologies», Bauman Moscow State Technical University
E-mail: bekasov@bmstu.ru
I.V. Rudakov – Ph.D.(Eng.), Associate Professor, Head of Department «Software of Computer and Information Technologies», Bauman Moscow State Technical University
E-mail: irudakov@yandex.ru


The area of comparison of tables, its formalization with the help of graph theory is considered. The existing method of factorized comparison of graphs, adapted to the peculiarities of the tabular presentation of information, is being implemented. The first of these is the presence of a priori known comparisons of indicators. In contrast to the algorithms that allow transferring such pairs to a result, the proposed algorithm uses the mapping data as reference points for further work, which improves accuracy. The second feature is the presence of a strong difference in the structures of many comparable tables, and, therefore, of graphs. The algorithm taken as a basis requires the presence of all vertices in its result, which leads to an increase in the number of false-positive comparisons. The proposed solution is to add dummy vertices. To study the characteristics of the obtained method, real and synthetic test data are used. Research of the influence of each feature is conducted. The study of dummy vertices influence on results is carried out on synthetic tests. On small graphs increase in precision was higher than original method only on small deviations. On large graphs proposed solution was better in most cases, which included almost half of the graph added as redundant vertices. The study of the influence of a priori information is carried out on real data, based on financial reports provided by banks or other public companies. Usage of such information reduced number of false-negatives, according to mathematical relations, to zero. In some cases, false-positives number was also reduced. Overall studies show that the modifications used reduce the number of false-positive and false-negative comparisons as a result. Further improvements include using other optimization techniques to increase performance and achieve faster convergence. Also method can be further modified to include information about a priori false comparisons, which can lead to reducing false-positives number.

References:
  1. International financial reporting standards (IAS) 1 «Presentation of financial statements». URL = http://www.consultant.ru/document /cons_doc_LAW_123175/ (last access: 30.11.2018).
  2. Kharari F. Teoriya grafov. Izdatelstvo «Mir». 1973.
  3. Zhou F., De la Torre F. Factorized graph matching. IEEE transactions on pattern analysis and machine intelligence. 2016. V. 38. № 9. P. 1774−1789.
  4. Zhou F., De la Torre F. Factorized graph matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2012. P. 127−134.
  5. Cho M., Lee J., Lee K.M. Reweighted random walks for graph matching. European conference on Computer vision. 2010. P. 492−505.
  6. Umeyama S. An eigendecomposition approach to weighted graph matching problems. IEEE transactions on pattern analysis and machine intelligence. 1988. V. 10. № 5. P. 695−703.
  7. Burkard R.E., Cela E., Pardalos P.M., Pitsoulis L.S. The quadratic assignment problem. Handbook of combinatorial optimization. 1998. P. 1713−1809.
  8. Sahni S. Computationally related problems. SIAM Journal on Computing. 1974. V. 3. № 4. P. 262−279.
  9. Frank M., Wolfe P. An algorithm for quadratic programming. Naval Research Logistics. 1956. V. 3. № 1−2. P. 95−110.
  10. Jonker R., Volgenant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing. 1987. V. 38. № 4. P. 325−340.

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio