Применение машинного обучения для оптимизации алгоритмов сортировки в больших данных
Автор: Абдумиталип Уулу К., Омаралиева Г.А., У Минг Ю., Бегали Уулу А.
Журнал: Бюллетень науки и практики @bulletennauki
Рубрика: Технические науки
Статья в выпуске: 11 т.11, 2025 года.
Бесплатный доступ
Современные системы обработки больших данных сталкиваются с существенными ограничениями производительности при выполнении операций сортировки, которые являются базовыми для широкого спектра аналитических и транзакционных задач. Классические алгоритмы сортировки, хотя и обладают строгими теоретическими оценками, часто не учитывают особенности реальных нагрузок: распределения ключей, неоднородность аппаратной архитектуры, вариативность профилей ввода-вывода и влияние кэшной и NUMA-топологии. В статье предлагается подход к оптимизации сортировки с применением методов машинного обучения, в котором МЛ-модели выполняют мета-задачи выбора и параметризации алгоритмов, прогнозируют стоимость вычислений и динамически адаптируют план выполнения с учётом характеристик данных и платформы. Обсуждаются стратегии обучения на основе метрик времени отклика и пропускной способности, использование байесовской оптимизации и методов обучения с подкреплением для настройки гибридных схем (например, слияние Timsort, Radix и Sample Sort), а также интеграция с фреймворками распределённой обработки. Представлены методологические аспекты построения датасетов профилей, механизмы онлайнового авто-тюнинга и валидации на реальных траекториях нагрузки. Отдельное внимание уделено воспроизводимости экспериментов, переносимости моделей и ограничителям, связанным с переобучением и стоимостью инференса. Предполагается включение обзора литературы с анализом результатов отечественных и международных исследований, включая работы сотрудников ОшГУ, посвящённые алгоритмам и системам обработки данных.
Большие данные, алгоритмы сортировки, машинное обучение, авто-тюнинг, байесовская оптимизация, обучение с подкреплением, выбор алгоритмов, профилирование производительности, распределённые системы, gpu-ускорение, гибридные схемы сортировки, прогнозирование стоимости, адаптивные планы выполнения
Короткий адрес: https://sciup.org/14135364
IDR: 14135364 | УДК: 004.8 | DOI: 10.33619/2414-2948/120/13
Machine learning for optimizing sorting algorithms in big-data systems
Sorting is a performance-critical primitive across modern data platforms, underpinning indexing, joins, external merge phases, and large-scale ETL pipelines. Classical algorithms-quicksort, mergesort, heapsort, radix/Counting variants-offer strong asymptotics but underperform when confronted with real-world variability: skewed key distributions, heavy duplication, near-sorted inputs, heterogeneous hardware, and fluctuating I/O and network conditions. This paper formulates sorting optimization as a learning-guided decision problem. We design a lightweight feature-extraction layer that summarizes data and system state via sublinear sketches (cardinality, duplication ratio, approximate disorder, record-size distribution) and runtime telemetry (memory availability, I/O bandwidth, NUMA distances, CPU/GPU utilization). On top of a cost-prediction model, our policy first filters dominated candidates, selects an algorithm family (e.g., TimSort/QuickSort vs. radix-based vs. external multiway merge), and then applies budgeted Bayesian tuning for a small set of sensitive parameters (block sizes, recursion depths, partition counts, spill thresholds). The architecture ensures correctness (determinism, stability when required) and integrates with production frameworks (Spark/Flink/MPP systems) at barrier points before shuffle, sort, and merge stages. We present a reproducible evaluation protocol combining synthetic and real traces, with ablations for each decision layer and stress tests for adversarial inputs and cluster drifts. Results show consistent reductions in median and tail latencies, I/O and network volume, and energy per record, while keeping inference and feature costs within strict budgets and providing safe fallbacks under uncertainty. We discuss limitations-telemetry noise, portability across clusters, and short-job overheads-and outline directions for theory-grounded guarantees and cross-cluster adaptation.
