Top

Published in:

2018 | OriginalPaper | Chapter

Solving CSS-Sprite Packing Problem Using a Transformation to the Probabilistic Non-oriented Bin Packing Problem

Authors : Soumaya Sassi Mahfoudh, Monia Bellalouna, Leila Horchani

Published in: Computational Science – ICCS 2018

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

CSS-Sprite is a technique of regrouping small images of a web page, called tiles, into images called sprites in order to reduce network transfer time. CSS-sprite packing problem is considered as an optimization problem. We approach it as a probabilistic non-oriented two-dimensional bin packing problem (2PBPP|R). Our main contribution is to allow tiles rotation while packing them in sprites. An experimental study evaluated our solution, which outperforms current solutions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Fast Vertex-Swap Operator for the Prize-Collecting Steiner Tree Problem

next chapter Optimization of Resources Selection for Jobs Scheduling in Heterogeneous Distributed Computing Environments

Fast rollovers without preload. http://wellstyled.com/css-nopreload-rollovers.html. Accessed 29 September 2017

A thousand ways to pack the bin - a practical approach to two-dimensional rectangle bin packing. http://clb.demon.fi/files/RectangleBinPack.pdf Accessed 10 July 2017

Alakuijala, J., Vandevenne, L.: Data compression using Zopfli.Google inc. (2013). https://github.com/google/zopfli. Accessed 08 January 2017

Baker, B., Coffman, E., Rivest, R.: Orthogonal packing in two dimensions. SIAM J. Comput. 9(4), 846–855 (1980)MathSciNetCrossRef

Bellalouna, M.: Problèmes d’optimisation combinatoires probabilistes. Ph.D. thesis, Ecole Nationale des Ponts et Chaussees (1993)

Chazelle, B.: The bottom-left bin-packing heuristic: an efficient implementation. IEEE Trans. Comput. 32(8), 697–707 (1983)CrossRef

Chen, P.H., Chen, Y., Goel, M., Mang, F.: Approximation of two-dimensional rectangle packing. Technical report (1999)

Chen, T.C., Chang, Y.W.: Modern floorplanning based on b*-tree and fast simulated annealing. Trans. Comp.-Aided Des. Integr. Circ. Sys. 25, 637–650 (2006)MathSciNetCrossRef

El Hayek, J., Moukrim, A., Nègre, S.: New resolution algorithm and pretreatments for the two-dimensional bin-packing problem. Comput. Oper. Res, 35(10), 3184–3201 (2008)CrossRef

10.

Framework, N.: Rectangle packing. http://nuclexframework.codeplex.com/. Accessed 25 January 2018

11.

Gordon, J.: Binary tree bin packing algorithm. https://codeincomplete.com/posts/bin-packing/. Accessed 08 September 2017

12.

Habib, A., Rahman, M.S.: Balancing decoding speed and memory usage for Huffman codes using quaternary tree. Appl. Inform. 4(1), 39–55 (2017)CrossRef

13.

Huang, E., Korf, R.: Optimal rectangle packing: an absolute placement approach. J. Artif. Intell. Res. 46, 47–87 (2013)MathSciNetMATH

14.

Jaillet, P.: A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6), 929–936 (1988)MathSciNetCrossRef

15.

Jaillet, P.: Analysis of probabilistic combinatorial optimization problems in euclidean spaces. Math. Oper. Res. 18(1), 51–70 (1993)MathSciNetCrossRef

16.

Jeon, M., Kim, Y., Hwang, J., Lee, J., Seo, E.: Workload characterization and performance implications of large-scale blog servers. ACM Trans. Web (TWEB) 6, 16 (2012)

17.

Korf, R.: Optimal rectangle packing: new results. In. Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling, ICAPS 2004, pp. 142–149 (2004)

18.

Lodi, A.: Algorithms for two-dimensional bin packing and assignment problems. Ph.D. thesis, Université de bologne (1999)

19.

Lodi, A., Martello, S., Vigo, D.: Recent advances on two-dimensional bin packing problems. Discret. Appl. Math. 123(1–3), 379–396 (2002)MathSciNetCrossRef

20.

Marszalkowski, J., Mizgajski, J., Mokwa, D., Drozdowski, M.: Analysis and solution of CSS-sprite packing problem. ACM Trans. Web (TWEB) 10(1), 283–294 (2015)

21.

Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: Rectangle-packing-based module placement. In: Kuehlmann, A. (ed.) The Best of ICCAD, pp. 535–548. Springer, Boston (2003). https://doi.org/10.1007/978-1-4615-0292-0_42CrossRef

22.

Rehman, M., Sharif, M., Raza, M.: Image compression: a survey. Res. J. Appl. Sci. Eng. Technol. 7(4), 656–672 (2014)

23.

Shea, D.: CSS sprites: image slicings kiss of death. A List Apart (2013)

24.

Stefanov, S.: Image optimization, part 3 : four steps to file size reduction. http://yuiblog.com/blog/2008/11/14/imageopt-3/. Accessed 29 Jan 2017

25.

Taubman, D., Marcellin, M.: JPEG2000 Image Compression Fundamentals, Standards and Practice: Image Compression Fundamentals, Standards and Practice, vol. 642. Springer Science & Business Media, Boston (2012). https://doi.org/10.1007/978-1-4615-0799-4CrossRef

26.

Velho, P., Schnorr, M., Casanova, H., Legrand, A.: On the validity of flow-level TCP network models for grid and cloud simulations. ACM Trans. Model. Comput. Simul. (TOMACS) 23, 23 (2013)MathSciNetCrossRef

27.

Wium Lie, H., Bos, B.: Cascading style sheets. World Wide Web J. 2, 75–123 (1997)

Title: Solving CSS-Sprite Packing Problem Using a Transformation to the Probabilistic Non-oriented Bin Packing Problem
Authors: Soumaya Sassi Mahfoudh
Monia Bellalouna
Leila Horchani
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2018
Print ISBN: 978-3-319-93700-7

Electronic ISBN: 978-3-319-93701-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93701-4_44

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner