Сжатие векторных представлений с использованием кластеризации с помощью ансамбля небрежных решающих деревьев и раздельного хранения центроидов

Введение. Современные подходы к поиску текстовых и мультимодальных данных в больших коллекциях предполагают преобразование документов в векторные представления. Для эффективного хранения этих векторов применяется квантизация, которая снижает точность представления и, как следствие, ухудшает качество поиска. Ранее был предложен метод, уменьшающий потери точности при квантизации, в котором векторы кластеризуются с помощью алгоритма k-средних, вычисляется смещение, или дельта, являющееся разницей между центроидом кластера и исходным вектором, после чего квантуется только смещение. В настоящей работе предлагается модификация этого метода, использующая другой алгоритм кластеризации — ансамбль небрежных решающих деревьев.

Метод. Разработанный метод основывается на обучении ансамбля бинарных небрежных решающих деревьев. Этот ансамбль используется для вычисления хэша каждого исходного векторного представления, после чего векторные представления с одинаковым хэшем рассматриваются как принадлежащие одному кластеру. В случае, если число результирующих кластеров слишком большое или слишком маленькое для используемого набора данных, производится процесс перекластеризации. Каждый кластер сохраняется в двух отдельных файлах: первый содержит смещения для каждого вектора, второй — идентификаторы и позиции данных в первом файле. Данные в первом файле подвергаются квантизации и затем сжимаются с помощью универсального алгоритма сжатия.

Основные результаты. Предложенный метод кластеризации протестирован на наборах данных fashion-mnist-784-euclidean и NYT-256-angular и сравнивался с кластеризацией методом k-средних. Метод показал лучшее качество сжатия, демонстрируя до 4,7 % меньшее занимаемое дисковое пространство при использовании квантизации NF4 и алгоритма сжатия Brotli. Для других алгоритмов сжатия увеличение пространства оказалось менее значительным. Однако представленный алгоритм кластеризации демонстрирует большее значение показателя ошибки квантизации по сравнению с методом k-средних, минимум до 16 %. По сравнению с форматом Parquet разработанный метод кластеризации продемонстрировал меньший показатель ошибки для набора данных fashion-mnist-784-euclidean при использовании квантизаций FP8 и NF4. Для набора данных NYT-256-angular по сравнению с Parquet предложенный метод при использовании алгоритма сжатия Brotli позволяет добиться лучшего качества сжатия для всех протестированных типов квантизации.

Обсуждение. Полученные результаты свидетельствуют о том, что разработанный метод кластеризации может быть использован не только в задачах поиска ближайших соседей, но и в задачах сжатия данных, когда увеличением ошибки квантизации можно пренебречь.

1. Grbovic 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.3219885

2. Korn F., Sidiropoulos N., Faloutsos C., Siegel E., Protopapas Z. Fast nearest neighbor search in medical image databases // Proc. of the 22th International Conference on Very Large Data Bases. 1996. P. 215–226. https://doi.org/10.5555/645922.673493

3. Zhou W., Lu Y., Li H., Tian Q. Scalar quantization for large scale image search // Proc. of the 20th ACM International Conference on M u l t i m e d i a . 2 0 1 2 . P. 1 6 9 – 1 7 8 . https://doi.org/10.5555/645922.673493

4. Zhang J., Yang J., Yuen H. Training with low-precision embedding tables // Systems for Machine Learning Workshop at NeurIPS. 2018. V. 2018.

5. Томилов Н.А., Туров В.П., Бабаянц А.А., Платонов А.В. Метод хранения векторных представлений в сжатом виде с применением кластеризации // Научно-технический вестник информационных технологий, механики и оптики. 2024. Т. 24. № 1. С. 112–117. https://doi.org/10.17586/2226-1494-2024-24-1-112-117

6. Tomilov N.A., Turov V.P., Babayants A.A., Platonov A.V. Vector search using method of clustering using ensemble of oblivious trees // Scientific and Technical Journal of Information Technologies, Mechanics and Optics. 2025. V. 25. N 2. P. 339–344. https://doi.org/10.17586/2226-1494-2025-25-2-339-344

7. Kanungo T., Mount D., Netanyahu N., Piatko Ch., Silverman R., Wu A. The analysis of a simple k-means clustering algorithm // Proc. of the 16th Annual Symposium on Computational Geometry. 2000. P. 100–109. https://doi.org/10.1145/336154.336189

8. Lou Y., Obukhov M. BDT: gradient boosted decision tables for high accuracy and scoring efficiency // Proc. of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017. P. 1893–1901. https://doi.org/10.1145/3097983.3098175

9. Kuzmin A., van Baalen M., Ren Y., Nagel M., Peters J., Blankevoort T. Fp8 quantization: The power of the exponent // Advances in Neural Information Processing Systems. 2022. V. 35. P. 1–10.

10. Dettmers T., Pagnoni A., Holtzman A., Zettlemoyer L. QloRA: efficient finetuning of quantized LLMs // Advances in Neural Information Processing Systems. 2023. V. 36. P. 1–5.

11. Alakuijala J., Farruggia A., Ferragina P., Kliuchnikov E., Obryk R., Szabadka Z., Vandevenne L. Brotli: A general-purpose data compressor // ACM Transactions on Information Systems (TOIS). 2018. V. 37. N 1. P. 1–30. https://doi.org/10.1145/3231935

12. Xiao 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.07747

13. 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_3

14. Zeng X., Hui Y., Shen J., Pavlo A., McKinney W., Zhang H. An empirical evaluation of columnar storage formats // Proc. of the VLDB Endowment. 2023. V. 17. N 2. P. 148–161. https://doi.org/10.14778/3626292.3626298

15. Туров В.П., Томилов Н.А., Бабаянц A.A. Разработка инструмента сравнения алгоритмов векторного поиска // XI Конгресс молодых учёных: cборник научных трудов. СПб: федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО». 2022. Т. 1. С. 446–450.

16. Laaber C., Leitner P. An evaluation of open-source software microbenchmark suites for continuous performance assessment // Proc. of the 15th International Conference on Mining Software Repositories (MSR ‘18). 2018. P. 119–130. https://doi.org/10.1145/3196398.3196407