Application of Codes in Modular Metrics for Searching k-neighbors
https://doi.org/10.15514/ISPRAS-2025-37(5)-2
Abstract
This paper is devoted to the application of suffix codes in the modular metric for solving clustering and k-nearest neighbors (KNN) problems. The advantages of using the modular metric over the Euclidean metric are considered, especially in high-dimensional spaces. The main emphasis is placed on the development of efficient clustering and k-nearest neighbors algorithms using codes that can correct errors in the modular metric. The proposed approach provides polynomial complexity with respect to the training sample dimension, which makes it promising for machine learning applications with large datasets and high-performance requirements.
Supporting agencies: The article was prepared during the research conducted within the framework of the Fundamental Research Program of the National Research University Higher School of Economics (HSE).
About the Authors
Alexander Rauilovich SHARAPOV
National Research University Higher School of Economics
Russian Federation
Russian Federation
A postgraduate student at the Moscow Institute of Electronics and Mathematics named after A.N. Tikhonov, Department of Electronic Engineering. The topic of his research is "Development of a method for analyzing data using codes that correct errors in the l1 metric". His research interests include statistics, data analysis, information coding, networks and telecommunications.
Vyacheslav Anatolyevich DAVYDOV
National Research University Higher School of Economics
Russian Federation
Russian Federation
Cand. Sci. (Tech., Econ.). He is a visiting lecturer at the Moscow Institute of Electronics and Mathematics named after A.N. Tikhonov, Department of Information Security of Cyber-Physical Systems. His research interests include algebraic and combinatorial coding theory, active systems theory, blockchain technology.
References
1. В. А. Давыдов. Использование кодов в модульной метрике для решения задачи KNN. (в публикации).
2. В. А. Давыдов. Коды, исправляющие ошибки в модульной метрике, метрике Ли и ошибки оператора // Пробл. передачи информ. 1993. Глава 29:3. С. 209–217
3. V. Davydov, N. Zeulin, I. Pastushok, A. Turlikov. Coding Scheme for High-Order QAM Modulations in the Manhattan Metric // IEEE Communications Letters. 2020. Vol. 24. N. 11. P. 2387–2391.
4. T. Cover, P. Hart. Nearest neighbor pattern classification // IEEE Transactions on Information Theory. 1967. Vol. 13. N. 1. P. 21–27.
5. Fix. E, Hodges, J.L. Discriminatory analysis. Nonparametric discrimination; consistency properties // USAF School of Aviation Medicine. 1951. Technical Report 4.
6. P. Indyk, R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality // Proceedings of the Symposium on Theory of Computing. 1998.
7. E. Kushilevitz, R. Ostrovsky, Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces // Proceedings of the Thirtieth ACM Symposium on Theory of Computing. 1998. P. 614– 623.
8. J. Buhler, M. Tompa. Finding motifs using random projections // Proceedings of the Annual International Conference on Computational Molecular Biology. 2001.
9. J. Buhler. Provably sensitive indexing strategies for biosequence similarity search // Proceedings of the Annual International Conference on Computational Molecular Biology. 2002.
10. N. C. Jones, P. A. Pevzner. An Introduction to Bioinformatics Algorithms // The MIT Press Cambridge. 2004.
11. M. Namratha. IOSR Journal of Computer Engineering. 2012. Vol. 4(6). P 23–30.
12. A. V. Kumar, J. C. Selvaraj. Journal of Recent Research and Applied Studies. 2016. Vo_103.
13. M. Omran, A. Engelbrecht, A. A. Salman. Intelligent Data Analysis. 2007. Vol. 11(6). P. 583–605.
14. M. Wegmann, D. Zipperling, J. Hillenbrand, J. Fleischer. A review of systematic selection of clustering algorithms and their evaluation. 2021.
15. J. Gu. Journal of Physics: Conference Series. 2021. Vol. 1.
16. T. W. Liao. Pattern Recognition. 2005. Vol. 38(11). P. 1857–1874.
17. Τ. Gupta, S. Panda. International Journal of Engineering & Technology. 2018. Vol. 7(4). P. 4766–4768.
Review
For citations:
SHARAPOV A.R., DAVYDOV V.A. Application of Codes in Modular Metrics for Searching k-neighbors. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(5):33-42. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(5)-2
Email this article 