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

A Moffat; M Petri

Conference Proceedings

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

A Moffat, M Petri

Association for Computing Machinery (ACM) | Published : 2018

DOI: 10.1145/3159652.3159663

Abstract

© 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

University of Melbourne Researchers

Alistair Moffat Author Computing and Information Systems

Related Projects (1)

Data retrieval from massive information structures

Information search is an essential tool. But most current services regard the data as unstructured collections of independent documents, fre..

Grants

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.