A simplified variant of tabled asymmetric numeral systems with a smaller look-up table

Data storage is an indispensable part of data management system. Asymmetric numeral systems (ANS) is a widely used compression algorithm. A number of implementations, such as range asymmetric numeral systems (rANS) and tabled asymmetric numeral systems (tANS), were proposed. However, rANS requires s...

Full description

Saved in:
Bibliographic Details
Published in:Distributed and parallel databases : an international journal 2021-09, Vol.39 (3), p.711-732
Main Authors: Wang, Na, Wang, Chao, Lin, Sian-Jheng
Format: Article
Language:English
Subjects:
Algorithms
Asymmetry
Compression ratio
Computer Science
Data management
Data storage
Data Structures
Database Management
Decoding
Information Systems Applications (incl.Internet)
Integers
Lookup tables
Memory Structures
Operating Systems
Special Issue on Spatio-Temporal Data Driven Urban Computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Data storage is an indispensable part of data management system. Asymmetric numeral systems (ANS) is a widely used compression algorithm. A number of implementations, such as range asymmetric numeral systems (rANS) and tabled asymmetric numeral systems (tANS), were proposed. However, rANS requires some costly arithmetic operations (integer additions, multiplications and divisions), and tANS requires large space to store the entire behavior in a look-up table. When the integer addition is allowed, this paper proposes a variant of tANS, that requires much smaller look-up table than the conventional tANS. In addition, a decoding algorithm to decode multiple symbols at once is proposed. The simulation shows that with a slight loss of compression ratio (approximately 0.5 % lower), the proposed method has up to a 25 % ( 60 % ) better throughput than rANS in encoding (decoding).
ISSN:0926-8782
1573-7578
DOI:10.1007/s10619-020-07316-9