Stream-Based Lossless Data Compression Hardware Using Adaptive Frequency Table Management

详细信息    查看全文

• 关键词：Lossless data compression ; Communication protocol ; Dynamic histogram creation
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9495
• 期：1
• 页码：133-146
• 全文大小：1,436 KB
• 参考文献：1. http://​pizzachili.​dcc.​uchile.​cl/​
  2.Apostolico, A., Lonardi, S.: Off-line compression by greedy textual substitution. Proc. IEEE 88(11), 1733–1744 (2000)CrossRef
  3.Grossi, R., Gupta, A., Vitter, J.S.: High-order Entropy-compressed Text Indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms / SODA 2003, pp. 841–850. ACM (2003)
  4.Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of 30th IEEE Annual Symposium on Foundations of Computer Science, pp. 549–554. IEEE (1989)
  5.Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28(1), 51–55 (2003)CrossRef
  6.Kieffer, J., Hui Yang, E.: Grammar-based codes: a new class of universallossless source codes. IEEE Trans. Inf. Theor. 46(3), 737–754 (2000)MATH CrossRef
  7.Kuon, I., Rose, J.: Measuring the gap between FPGAs and ASICs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 26(2), 203–215 (2007)CrossRef
  8.Larsson, N., Moffat, A.: Offline dictionary-based compression. In: Proceedings of Data Compression Conference (DCC 1999), pp. 296–305. IEEE, March 1999
  9.Manku, G.S., Motwani, R.: Approximate frequency counts over data streams. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 346–357. VLDB Endowment (2002)
  10.Maruyama, S., Sakamoto, H., Takeda, M.: An online algorithm for lightweight grammar-based compression. Algorithms 5(2), 214–235 (2012)MathSciNet CrossRef
  11.Metwally, A., Agrawal, D., Abbadi, A.E.: An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Database Syst. 31(3), 1095–1133 (2006)CrossRef
  12.Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: A linear-time algorithm. J. Artif. Intell. Res. 7(1), 67–82 (1997)MATH
  13.Vitter, J.S.: Design and analysis of dynamic huffman codes. J. ACM 34(4), 825–845 (1987)MATH MathSciNet CrossRef
  14.Yamagiwa, S., Aoki, K., Wada, K.: Performance enhancement of inter-cluster communication with software-based data compression in link layer. Proc. IASTED PDCS 2005, 325–332 (2005)
  15.Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. 23(3), 337–343 (1977)MATH MathSciNet CrossRef
  16.Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. 24(5), 530–536 (1978)MATH MathSciNet CrossRef
  
• 作者单位：Shinichi Yamagiwa (16)
  Koichi Marumo (16)
  Hiroshi Sakamoto (17)
  
  16. Faculty of Engineering, Information and Systems/Department of Computer Science, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, Japan
  17. Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka-shi, Fukuoka, Japan
  
• 丛书名：Big Data Benchmarks, Performance Optimization, and Emerging Hardware
• ISBN：978-3-319-29006-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In order to treat BigData efficiently, the communication speed of the inter or the intra data path equipped on high performance computing systems that needs to treat BigData management has been reaching to very high speed. In spite of fast increasing of the BigData, the implementation of the data communication path has become complex due to the electrical difficulties such as noises, crosstalks and reflections of the high speed data connection via a single cupper-based physical wire. This paper proposes a novel hardware solution to implement it by applying a stream-based data compression algorithm called the LCA-DLT. The compression algorithm is able to treat continuous data stream without exchanging the symbol lookup table among the compressor and the decompressor. The algorithm includes a dynamic frequency management of data patterns. The management is implemented by a dynamic histogram creation optimized for hardware implementation. When the dedicated communication protocol is combined with the LCA-DLT, it supports remote data migration among the computing systems. This paper describes the algorithm design and its hardware implementation of the LCA-DLT, and also shows the compression performance including the required hardware resources.