Abstract
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 \(\varvec{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 \(\varvec{K}\) when \(\varvec{m\ge K_c}\) 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 \(\varvec{1.036\%}\) margin and is approximately \(\varvec{6.5\times }\) faster, confirming their value for time-critical applications.
Data Availability
Source code for OnGP/OffGP and instance generation scripts are available at: https://github.com/sonoffreewind/fast-bin-packing-algorithms Experimental item lists were synthesized using the C++ random library for Uniform, Normal, Lognormal, and Weibull distributions, with Pareto distributions generated via inverse transform sampling. Full configuration parameters, the random seed, and the complete experimental data supporting Section 4—including the raw CSV outputs and the summary file “Experiments_2026.xlsx”—are provided in the same repository, under the data/Release folder.
References
Cui, Y., Lai, Z., Wang, X., Dai, N.: Quicksync: Improving synchronization efficiency for mobile cloud storage services. IEEE Trans. Mob. Comput. 16(12), 3513–3526 (2017). https://doi.org/10.1109/TMC.2017.2693370
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)
Hasan, Y., Chang, M.: A study of best-fit memory allocators. Comput. Lang. Syst. Struct. 31(1), 35–48 (2005). https://doi.org/10.1016/j.cl.2004.06.001
Karresand, M., Axelsson, S., Dyrkolbotn, G.O.: Disk cluster allocation behavior in windows and ntfs. Mobile Netw. Appl. 25(1), 248–258 (2020)
Coffman, E.G. Jr., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: Survey and classification. In: Handbook of Combinatorial Optimization vol. 1-5, pp. 455–531. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1_35
Coffman, E.G. Jr., Garey, M.R., Johnson, D.S.: Approximation Algorithms for Bin Packing: A Survey, pp. 46–93. PWS Publishing Co., USA (1996)
Douceur, J.R., Bolosky, W.J.: A large-scale study of file-system contents. ACM SIGMETRICS Performance Evaluation Review. 27(1), 59–70 (1999). https://doi.org/10.1145/301464.301480
Agrawal, N., Arpaci-Dusseau, A.C., Arpaci-Dusseau, R.H.: Generating realistic impressions for file-system benchmarking. ACM Trans. Stor. 5(4), 1–30 (2009). https://doi.org/10.1145/1629080.1629086
Li, Z., Wang, X., Huang, N., Kaafar, M.A., Li, Z., Zhou, J., Xie, G., Steenkiste, P.: An empirical analysis of a large-scale mobile cloud storage service. In: Proceedings of the 2016 Internet Measurement Conference. IMC ’16, pp. 287–301. Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2987443.2987465
Coffman, E.G. Jr., Lueker, G.S.: Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization, p. 192. John Wiley & Sons, Inc., New York, New York (1991)
Coffman, E.G., Jr., So, K., Hofri, M., Yao, A.C.: A stochastic model of bin-packing. Inf. Control 44(2), 105–115 (1980). https://doi.org/10.1016/S0019-9958(80)90050-9
Ramanan, P.: Average-case analysis of the smart next fit algorithm. Inform. Process. Lett. 31(5), 221–225 (1989). https://doi.org/10.1016/0020-0190(89)90077-X
Coffman, E.G., Jr., Johnson, D.S., Shor, P.W., Weber, R.R.: Bin packing with discrete item sizes, part ii: Tight bounds on first fit. Random Struct. Algo. 10(1–2), 69–101 (1997). https://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199701/03)10:1/2%3C69::AID-RSA4%3E3.0.CO;2-V
Shor, P.W.: The average-case analysis of some on-line algorithms for bin packing. Combinatorica. An International Journal of the János Bolyai Mathematical Society 6(2), 179–200 (1986). https://doi.org/10.1007/BF02579171
Lueker, G.S.: An average-case analysis of bin packing with uniformly distributed item sizes. 181 Technical report, Department of Information and Computer Science, University of California at Irvine (1982)
Shor, P.W.: How to pack better than best fit: tight bounds for average-case online bin packing. In: [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 752–759 (1991). https://doi.org/10.1109/SFCS.1991.185444
Gu, X., Chen, G., Xu, Y.: Deep performance analysis of refined harmonic bin packing algorithm. J. Comput. Sci. Tech. 17(2), 213–218 (2002). https://doi.org/10.1007/BF02962214
Ramanan, P., Tsuga, K.: Average-case analysis of the modified harmonic algorithm. Algorithmica. An International Journal in Computer Science. 4(4), 519–533 (1989). https://doi.org/10.1007/BF01553906
Hoffmann, U.: A class of simple stochastic online bin packing algorithms. Computing. Archives for Scientific Computing. 29(3), 227–239 (1982). https://doi.org/10.1007/BF02241699
Csirik, J., Galambos, G.: An \(O(n)\) bin-packing algorithm for uniformly distributed data. Computing. Archives for Scientific Computing. 36(4), 313–319 (1986). https://doi.org/10.1007/BF02240206
Karp, R.M., Luby, M., Marchetti-Spaccamela, A.: A probabilistic analysis of multidimensional bin packing problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing. STOC ’84, pp. 289–298. Association for Computing Machinery, New York, NY, USA (1984). https://doi.org/10.1145/800057.808693
Talagrand, M.: Matching theorems and empirical discrepancy computations using majorizing measures. J. Am. Math. Soc. 7(2), 455–537 (1994). https://doi.org/10.2307/2152764
Coffman, E.G., Jr., Shor, P.W.: Packings in two dimensions: asymptotic average-case analysis of algorithms. Algorithmica 9(3), 253–277 (1993). https://doi.org/10.1007/BF01190899
Johnson, D.S.: Near-optimal bin packing algorithms, PhD thesis. Massachusetts Institute of Technology (1973)
Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272–314 (1974). https://doi.org/10.1016/S0022-0000(74)80026-7
Lee, C.C., Lee, D.T.: A simple on-line bin-packing algorithm. J. Assoc. Comput. Mach. 32(3), 562–572 (1985). https://doi.org/10.1145/3828.3833
Ramanan, P., Brown, D.J., Lee, C.C., Lee, D.T.: On-line bin packing in linear time. J. Alg. Cogn. Inf. Logic. 10(3), 305–326 (1989). https://doi.org/10.1016/0196-6774(89)90031-X
Knödel, W.: A bin packing algorithm with complexity \(O(n{\rm log}\,n)\) and performance \(1\) in the stochastic limit. In: Mathematical Foundations of Computer Science, 1981 (Štrbské Pleso, 1981). Lecture Notes in Comput. Sci., vol. 118, pp. 369–378. Springer, Berlin, Heidelberg (1981). https://doi.org/10.1007/3-540-10856-4_104
Rényi, A.: The laws of chance. In: Foundations of Probability, pp. 234–236. Holden-Day, San Francisco (1970)
Knuth, D.E.: The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd edn. Addison-Wesley Professional, Reading, Massachusetts (1997)
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299–325 (1974). https://doi.org/10.1137/0203025
Wilson, P.R., Johnstone, M.S., Neely, M., Boles, D.: Dynamic storage allocation: A survey and critical review. In: Baler, H.G. (ed.) Memory Management, pp. 1–116. Springer, Berlin, Heidelberg (1995)
Castiñeiras, I., De Cauwer, M., O’Sullivan, B.: Weibull-based benchmarks for bin packing. In: Milano, M. (ed.) Principles and Practice of Constraint Programming, pp. 207–222. Springer, Berlin, Heidelberg (2012)
Funding
This work was partially supported by the National Key R&D Program of China (Nos. 2021YFA1000300 and 2021YFA1000302), the National Natural Science Foundation of China (No. 12331014), the Science and Technology Commission of Shanghai Municipality (No. 22DZ2229014), and the China Postdoctoral Science Foundation (No. 2024M750915).
Author information
Authors and Affiliations
Contributions
All authors contributed to the study conception and design. The problem to find linear time bin packing algorithms is generated in the discussion between Lifeng Guo and his tutor Changhong Lu. The two algorithms OnGP and OffGP are designed, modification, verified iteratively by Lifeng Guo, Changhong Lu, and Qingjie Ye. The revised manuscript was modified by Lifeng Guo and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Conflicts of interest/Competing interests
Lifeng Guo and Changhong Lu have the patent CN202110693560.X pending to East China Normal University. The authors declare that the publication of this article has no conflicts of interest with other people or organizations.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Guo, L., Lu, C. & Ye, Q. Fast Algorithms for a Large-Scale File Aggregation Problem. Theory Comput Syst 70, 47 (2026). https://doi.org/10.1007/s00224-026-10293-8
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s00224-026-10293-8