Fast Algorithms for a Large-Scale File Aggregation Problem

Motivated by the strict latency constraints in high-throughput cloud storage, this article addresses the fundamental theoretical challenge of designing high-efficiency bin packing algorithms with near-linear-time complexity. While traditional approximation algorithms achieve high packing density, their super-linear runtime overheads often prohibit their use in real-time systems. To bridge this gap between time and space efficiency, we apply a novel grouping-based framework that discretizes the item space into K types. We present an online algorithm OnGP and an offline algorithm OffGP, both utilizing an equidistant grouping strategy. Theoretical analysis establishes that OnGP suppresses stochastic fluctuations via a resource pooling parameter, while OffGP reaches a matching fixed point with high probability for fixed K when m≥Kc and admits complementary instance-dependent residual certificates. Extensive experiments further demonstrate that OffGP substantially reduces the stochastic component of waste on the tested instances. Results show that OnGP provides a robust online solution with efficiencies close to the Best Fit algorithm, while OffGP matches the near-optimal performance of Best Fit Decreasing within a 1.036% margin and is approximately 6.5× faster, confirming their value for time-critical applications.