Systems and Means of Informatics
2025, Volume 35, Issue 4, pp pp 54-163
COMPLEXITY OF THE ALGORITHM FOR FINDING COINCIDENCES IN SEVERAL SEQUENCES
- A. A. Grusho
- M. I. Zabezhailo
- V. V. Kulchenkov
- E. E. Timonina
Abstract
Analysis of data for the presence of effects of an unknown but present cause arises in many tasks and one of the examples given in the work is related to the search for signs of fraud among many recipients of a consumer loan in a bank.
To build the initial data, a method was chosen in which signs of fraud appear in transactional activity after receiving a loan, namely, the signs are based on how the funds are withdrawn. The example given is a special case of situations when in a limited set of precedents of data having a large dimension, the effects of one cause are present and repeated. Under these conditions, the task of finding repetitions of consequences of effects is of great importance. An algorithm for such a search has been built, which has a complexity less than quadratic. The complexity of the constructed algorithm for finding all coincidences in m ordered precedents does not exceed mN where N is the length of all precedents. Given the complexity of ordering each precedent when there is the initial ordering of the entire set of characteristics, the complexity of solving the problem does not exceed mN log2 N.
[+] References (14)
- Grusho, A. A., N. A. Grusho, M. I. Zabezhailo, V. V. Kulchenkov, and E. E. Timonina. 2025. Klassifikatsiya malykh naborov dannykh bol'shoy razmernosti [Classification of small sets of data of large dimension]. Informatika i ee Primeneniya - Inform. Appl. 19(3):67{72. doi: 10.14357/19922264250308. EDN: SUSRRC.
- Fahd, E., A. Fahad, and A. Amal. 2023. Enhancing loan fraud detection process in the banking sector using data mining techniques. Indonesian J. Electrical Engineering Computer Science 32(2):956{967. doi: 10.11591/ijeecs.v32.i2.pp956-967.
- Akinjole, A., O. Shobayo, J. Popoola, O. Okoyeigbo, and B. Ogunleye. 2024. Ensemble-based machine learning algorithm for loan default risk prediction. Mathematics 12(21):3423. 31 p. doi: 10.3390/math12213423.
- Vorobyev, I. A. 2024. Issledovaniya po razrabotke metodov protivodeystviya moshennichestvu v finansovykh organizatsiyakh s primeneniem mashinnogo obucheniya [Research on the development of methods for combating fraud in financial organizations using machine learning]. Moscow: HSE University. PhD Thesis. 103 p.
- Glymour, C., K. Zhang, and P. Spirtes. 2019. Review of causal discovery methods based on graphical models. Frontiers Genetics 10:524. 15 p. doi: 10.3389/fgene. 2019.00524.
- Richens, J. G., C. M. Lee, and S. Johri. 2020. Improving the accuracy of medical diagnosis with causal machine learning. Nat. Commun. 11:3923. 9p. doi: 10.1038/s41467- 020-17419-7.
- Grusho, A., N. Grusho, M. Zabezhailo, and E. Timonina. 2021. Localization of the root cause of the anomaly. Autom. Control Comp. S. 55(8):978{983. doi: 10.3103/ S0146411621080137. EDN: YALOOQ.
- Grusho, A. A., N. A. Grusho, M.I. Zabezhailo, V.V. Kulchenkov, E.E. Timonina, and S.Ya. Shorgin. 2023. Prichinno-sledstvennye svyazi v zadachakh klassifikatsii [Causal relationships in classification problems]. Informatika i ee Primeneniya - Inform. Appl. 17(1):43{49. doi: 10.14357/19922264230106. EDN: DTQZPIK
- Grusho, A. A., M.I. Zabezhailo, V.V. Kulchenkov, D.V. Smirnov, E.E. Timonina, and S.Ya. Shorgin. 2023. Prichinno-sledstvennye svyazi v zadachakh analiza nenablyudaemykh svoystv protsessov [Cause-and-effect relationships in analysis of unobservable process properties]. Sistemy i Sredstva Informatiki - Systems and Means of Informatics 33(2):7G78. doi: 10.14357/08696527230207.EDN: HMOFPG.
- Grusho, A. A., N. A. Grusho, M.I. Zabezhailo, E.E. Timonina, and S.Ya. Shorgin. 2023. Slozhnye prichinno-sledstvennye svyazi [Complex cause-and-effect relationships]. Informatika i ee Primeneniya - Inform. Appl. 17(2):84{89. doi: 10.14357/19922264230212. EDN: TGXQIW.
- Grusho, A. A., N. A. Grusho, M.I. Zabezhailo, D.V. Smirnov, and E.E. Timonina. 2023. Klassifikatsiya s pomoshch'yu prichinno-sledstvennykh svyazey [Classification by cause-and-effect relationships]. Informatika i ee Primeneniya - Inform. Appl. 17(3):7G75. doi: 10.14357/19922264230310. EDN: AKWBZD.
- Hofler, M. 2005. Causal inference based on counter factuals. BMC Med. Res. Method- ol. 5:28. 12 p. doi: 10.1186/1471-2288-5-28.
- Nievergelt, J., J. C. Farrar, and E. M. Reingold. 1974. Computer approaches to mathematical problems. Englewood Cliffs, NJ: Prentice-Hall. 257 p.
- Aho, A. V., J. E. Hopkroft, and J. D. Ullman. 1983. Data structures and algorithms. Reading, MA: Addison-Wesley. 427 p.
[+] About this article
Title
COMPLEXITY OF THE ALGORITHM FOR FINDING COINCIDENCES IN SEVERAL SEQUENCES
Journal
Systems and Means of Informatics
Volume 35, Issue 4, pp 154-163
Cover Date
2025-12-25
DOI
10.14357/08696527250411
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
complexity of the classification task; machine learning; cause and effect relationships; searching for coincidences in the sequence of sets
Authors
A. A. Grusho  , M. I. Zabezhailo , V. V. Kulchenkov  , and E. E. Timonina
Author Affiliations
Federal Research Center "Computer Science and Control", Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
VTB Bank, 43-1 Vorontsovskaya Str., Moscow 109147, Russian Federation
|