ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2024-24-1-112-117ntv-105Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEМетод хранения векторных представлений в сжатом виде с применением кластеризацииA method of storing vector data in compressed form using clusteringhttps://orcid.org/0000-0001-9325-0356ТомиловН. А.TomilovN. A.

Томилов Никита Андреевич — аспирант

Санкт-Петербург, 197101

sc 57225127284

Nikita A. Tomilov — PhD Student

Saint Petersburg, 197101

sc 57225127284

programmer174@icloud.comhttps://orcid.org/0009-0009-1470-7633ТуровВ. П.TurovV. P.

Туров Владимир Павлович — аспирант

Санкт-Петербург, 197101

Vladimir P. Turov — PhD Student

Saint Petersburg, 197101

firemoon@icloud.comhttps://orcid.org/0009-0004-6367-6398БабаянцА. А.BabayantsA. A.

Бабаянц Александр Амаякович — аспирант

Санкт-Петербург, 197101

Alexander A. Babayants — PhD Student

Saint Petersburg, 197101

babayants.alexander@gmail.comhttps://orcid.org/0000-0002-8485-1296ПлатоновА. В.PlatonovA. V.

Платонов Алексей Владимирович — кандидат технических наук, доцент

Санкт-Петербург, 197101 

Alexey V. Platonov — PhD, Associate Professor

 Saint Petersburg, 197101

avplatonov@itmo.ruУниверситет ИТМОРоссияITMO UniversityRussian Federation202412122024241112117Copyright © Томилов Н.А., Туров В.П., Бабаянц А.А., Платонов А.В., 20242024Томилов Н.А., Туров В.П., Бабаянц А.А., Платонов А.В.Tomilov N.A., Turov V.P., Babayants A.A., Platonov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/105

Введение. Алгоритмы машинного обучения для информационного поиска позволяют представить текстовые и мультимодальные документы в виде векторов. Такие векторные представления (embeddings) сохраняют семантическое содержание документов и сводят задачу поиска к задаче определения расстояния между векторами. Сжатие векторных представлений позволяет уменьшить объем памяти, занимаемый ими, и повысить эффективность вычислений. В работе рассмотрены существующие способы сжатия векторных представлений без потери и с потерей точности. Предложен метод уменьшения ошибки путем кластеризации векторных представлений при использовании сжатия с потерей точности. Метод. Сущность метода состоит в предварительной кластеризации векторных представлений, сохранении центров каждого кластера и значений координат каждого векторного представления относительно центра его кластера. Центры каждого кластера сжимаются без потери точности, а получившиеся смещенные векторные представления с потерей точности. Основные результаты. Предложенный метод протестирован на наборах данных fashion-mnist-784-euclidean и NYT-256-angular. Проведено сравнение векторных представлений, сжатых с потерей точности при помощи уменьшения разрядности, с векторными представлениями, сжатыми по предложенному методу. При незначительном, около 10 %, увеличении размера сжатых данных средняя абсолютная величина ошибки от потери точности для наборов fashion-mnist-784-euclidean и NYT-256-angular снизилась в четыре и примерно в два раза соответственно. Обсуждение. Разработанный метод может быть применен для решения задач хранения и обработки векторных представлений мультимодальных документов, например, при разработке поисковых систем.

The development of the machine learning algorithms for information search in recent years made it possible to represent text and multimodal documents in the form of vectors. These vector representations (embeddings) preserve the semantic content of documents and allow the search to be performed as the calculation of distance between vectors. Compressing embeddings can reduce the amount of memory they occupy and improve computational efficiency. The article discusses existing methods for compressing vector representations without loss of accuracy and with loss of accuracy. A method is proposed to reduce error by clustering vector representations using lossy compression. The essence of the method is in performing the preliminary clustering of vector representations, saving the centers of each cluster, and saving the coordinate value of each vector representation relative to the center of its cluster. Then, the centers of each cluster are compressed without loss of accuracy, and the resulting shifted vector representations are compressed with loss of accuracy. To restore the original vector representations, the coordinates of the center of the corresponding cluster are added to the coordinates of the displaced representation. The proposed method was tested on the fashion-mnist-784-euclidean and NYT-256-angular datasets. A comparison has been made of compressed vector representations with loss of accuracy by reducing the bit depth with vector representations compressed using the proposed method. With a slight (around 10 %) increase in the size of the compressed data, the absolute value of the error from loss of accuracy decreased by four and two times, respectively, for the tested sets. The developed method can be applied in tasks where it is necessary to store and process vector representations of multimodal documents, for example, in the development of search engines.

векторные представленияэмбеддингкластеризацияk-meansсжатие векторных представленийvector representationsembeddingsclusteringk-meanscompression of vector representationsReferencesGrbovic M., Cheng H. Real-time personalization using embeddings for search ranking at airbnb // Proc. of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018. P. 311–320. https://doi.org/10.1145/3219819.3219885Grbovic M., Cheng H. Real-time personalization using embeddings for search ranking at airbnb // Proc. of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018. P. 311–320. https://doi.org/10.1145/3219819.3219885Berry M.W., Drmac Z., Jessup E.R. Matrices, vector spaces, and information retrieval // SIAM Review. 1999. V. 41. N 2. P. 335–362. https://doi.org/10.1137/S0036144598347035Berry M.W., Drmac Z., Jessup E.R. Matrices, vector spaces, and information retrieval // SIAM Review. 1999. V. 41. N 2. P. 335–362. https://doi.org/10.1137/S0036144598347035Micikevicius P., Narang S., Alben J., Diamos G., Elsen E., Garcia D., Ginsburg B., Houston M., Kuchaiev O., Venkatesh G., Wu H. Mixed precision training // arXiv. 2017. arXiv:1710.03740. https://doi.org/10.48550/arXiv.1710.03740Micikevicius P., Narang S., Alben J., Diamos G., Elsen E., Garcia D., Ginsburg B., Houston M., Kuchaiev O., Venkatesh G., Wu H. Mixed precision training // arXiv. 2017. arXiv:1710.03740. https://doi.org/10.48550/arXiv.1710.03740Zhang J., Yang J., Yuen H. Training with low-precision embedding tables // Systems for Machine Learning Workshop at NeurIPS. 2018. V. 2018.Zhang J., Yang J., Yuen H. Training with low-precision embedding tables // Systems for Machine Learning Workshop at NeurIPS. 2018. V. 2018.Moghadasi M.N., Zhuang Y. Sent2Vec: A new sentence embedding representation with sentimental semantic // Proc. of the 2020 IEEE International Conference on Big Data (Big Data). 2020. P. 4672– 4680. https://doi.org/10.1109/BigData50022.2020.9378337Moghadasi M.N., Zhuang Y. Sent2Vec: A new sentence embedding representation with sentimental semantic // Proc. of the 2020 IEEE International Conference on Big Data (Big Data). 2020. P. 4672– 4680. https://doi.org/10.1109/BigData50022.2020.9378337Parekar P.M., Thakare S.S. Lossless data compression algorithm–a review // International Journal of Computer Science & Information Technologies. 2014. V. 5. N 1. P. 276–278.Parekar P.M., Thakare S.S. Lossless data compression algorithm–a review // International Journal of Computer Science & Information Technologies. 2014. V. 5. N 1. P. 276–278.Manro A., Sinha S., Chaturvedi B., Mohan J. Index seek versus table scan performance and implementation of RDBMS // Lecture Notes in Electrical Engineering. 2019. V. 526. P. 411–420. https://doi.org/10.1007/978-981-13-2553-3_40Manro A., Sinha S., Chaturvedi B., Mohan J. Index seek versus table scan performance and implementation of RDBMS // Lecture Notes in Electrical Engineering. 2019. V. 526. P. 411–420. https://doi.org/10.1007/978-981-13-2553-3_40Kanungo T., Mount D., Netanyahu N., Piatko Ch., Silverman R., Wu A. The analysis of a simple k-means clustering algorithm // Proc. of the sixteenth annual symposium on Computational geometry. 2000. P. 100–109. https://doi.org/10.1145/336154.336189Kanungo T., Mount D., Netanyahu N., Piatko Ch., Silverman R., Wu A. The analysis of a simple k-means clustering algorithm // Proc. of the sixteenth annual symposium on Computational geometry. 2000. P. 100–109. https://doi.org/10.1145/336154.336189Xiao H., Rasul K., Vollgraf R. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms // arXiv. 2017. arXiv:1708.07747. https://doi.org/10.48550/arXiv.1708.07747Xiao H., Rasul K., Vollgraf R. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms // arXiv. 2017. arXiv:1708.07747. https://doi.org/10.48550/arXiv.1708.07747Bi C., China P.R. Research and application of SQLite embedded database technology // WSEAS Transactions on Computers. 2009. V. 8. N 1. P. 83–92.Bi C., China P.R. Research and application of SQLite embedded database technology // WSEAS Transactions on Computers. 2009. V. 8. N 1. P. 83–92.Туров В.П., Томилов Н.А., Бабаянц А.А. Разработка инструмента сравнения алгоритмов векторного поиска // XI Конгресс молодых учёных: сборник научных трудов. Т. 1. 2022. С. 446–450.Turov V.P., Tomilov N.A., Babaiantc A.A. Development of a tool for comparing vector search algorithms. Proc. of the XI Congress of Young Scientists. V. 1. 2022, pp. 446–450. (in Russian)Aumüller M., Bernhardsson E., Faithfull A. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms // Lecture Notes in Computer Science. 2017. V. 10609. P. 34–49. https://doi.org/10.1007/978-3-319-68474-1_3Aumüller M., Bernhardsson E., Faithfull A. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms // Lecture Notes in Computer Science. 2017. V. 10609. P. 34–49. https://doi.org/10.1007/978-3-319-68474-1_3Golomb S. Run-length encodings (Corresp.) // IEEE Transactions on Information Theory. 1966. V. 12. N 3. P. 399–401. https://doi.org/10.1109/TIT.1966.1053907Golomb S. Run-length encodings (Corresp.) // IEEE Transactions on Information Theory. 1966. V. 12. N 3. P. 399–401. https://doi.org/10.1109/TIT.1966.1053907

The authors declare that there are no conflicts of interest present.