Conference Proceedings

Index compression using byte-ALIGNED ANS coding and two-dimensional contexts

A Moffat, M Petri

Association for Computing Machinery (ACM) | Published : 2018


© 2018 Association for Computing Machinery, Inc. All rights reserved. We examine approaches used for block-based inverted index compression, such as the OptPFOR mechanism, in which fixed-length blocks of postings data are compressed independently of each other. Building on previous work in which asymmetric numeral systems (ANS) entropy coding is used to represent each block, we explore a number of enhancements: (i) the use of two-dimensional conditioning contexts, with two aggregate parameters used in each block to categorize the distribution of symbol values that underlies the ANS approach, rather than just one; (ii) the use of a byte-friendly strategic mapping from symbols to ANS codeword ..

View full abstract


Awarded by Australian Research Council

Funding Acknowledgements

This work was supported under the Australian Research Council's Discovery Projects funding scheme (project number DP140103256). We thank Giulio Pibiri and Rossano Venturini for assisting us with the use of their software.