Index compression using 64‐bit words

Abstract

Abstract Modern computers typically make use of 64‐bit words as the fundamental unit of data access. However the decade‐long migration from 32‐bit architectures has not been reflected in compression technology, because of a widespread assumption that effective compression techniques operate in terms of bits or bytes, rather than words. Here we demonstrate that the use of 64‐bit access units, especially in connection with word‐bounded codes, does indeed provide the opportunity for improving the compression performance. In particular, we extend several 32‐bit word‐bounded coding schemes to 64‐bit operation and explore their uses in information retrieval applications. Our results show that the Simple‐8b approach, a 64‐bit word‐bounded code, is an excellent self‐skipping code, and has a clear advantage over its competitors in supporting fast query evaluation when the data being compressed represents the inverted index for a large text collection. The advantages of the new code also accrue on 32‐bit architectures, and for all of Boolean, ranked, and phrase queries; which means that it can be used in any situation. Copyright © 2010 John Wiley & Sons, Ltd.