Term frequency quantization for compressing an inverted index

Lei Zheng; Ingemar J Cox

Term frequency quantization for compressing an inverted index

Abstract

In this paper, we investigate the lossy compression of term frequencies in an inverted index based on quantization. Firstly, we examine the number of bits to code term frequencies with no or little degradation of retrieval performance. Both term-independent and term-specific quantizers are investigated. Next, an iterative technique is described for learning quantization step sizes. Experiments based on standard TREC test sets demonstrate that nearly no degradation of retrieval performance can be achieved by allocating only 2 or 3 bits for the quantized version of term frequencies. This is comparable to lossless coding techniques such as unary, γ and δ-codes. However, if lossless coding is applied to the quantized term frequency values, then around 26% (or 12%) savings can be achieved over lossless coding alone, with less than 2.5% (or no measurable) degradation in retrieval performance.

Original language	English
Title of host publication	Active Media Technology
Number of pages	11
Publisher	Springer Science+Business Media
Publication date	2010
Pages	277-287
Publication status	Published - 2010
Externally published	Yes

Cite this

@inbook{1a7eac6c4524413ebb2c90509279b008,

title = "Term frequency quantization for compressing an inverted index",

abstract = "In this paper, we investigate the lossy compression of term frequencies in an inverted index based on quantization. Firstly, we examine the number of bits to code term frequencies with no or little degradation of retrieval performance. Both term-independent and term-specific quantizers are investigated. Next, an iterative technique is described for learning quantization step sizes. Experiments based on standard TREC test sets demonstrate that nearly no degradation of retrieval performance can be achieved by allocating only 2 or 3 bits for the quantized version of term frequencies. This is comparable to lossless coding techniques such as unary, γ and δ-codes. However, if lossless coding is applied to the quantized term frequency values, then around 26% (or 12%) savings can be achieved over lossless coding alone, with less than 2.5% (or no measurable) degradation in retrieval performance.",

author = "Lei Zheng and Cox, {Ingemar J}",

year = "2010",

language = "English",

pages = "277--287",

booktitle = "Active Media Technology",

publisher = "Springer Science+Business Media",

address = "Singapore",

}

TY - CHAP

T1 - Term frequency quantization for compressing an inverted index

AU - Zheng, Lei

AU - Cox, Ingemar J

PY - 2010

Y1 - 2010

N2 - In this paper, we investigate the lossy compression of term frequencies in an inverted index based on quantization. Firstly, we examine the number of bits to code term frequencies with no or little degradation of retrieval performance. Both term-independent and term-specific quantizers are investigated. Next, an iterative technique is described for learning quantization step sizes. Experiments based on standard TREC test sets demonstrate that nearly no degradation of retrieval performance can be achieved by allocating only 2 or 3 bits for the quantized version of term frequencies. This is comparable to lossless coding techniques such as unary, γ and δ-codes. However, if lossless coding is applied to the quantized term frequency values, then around 26% (or 12%) savings can be achieved over lossless coding alone, with less than 2.5% (or no measurable) degradation in retrieval performance.

AB - In this paper, we investigate the lossy compression of term frequencies in an inverted index based on quantization. Firstly, we examine the number of bits to code term frequencies with no or little degradation of retrieval performance. Both term-independent and term-specific quantizers are investigated. Next, an iterative technique is described for learning quantization step sizes. Experiments based on standard TREC test sets demonstrate that nearly no degradation of retrieval performance can be achieved by allocating only 2 or 3 bits for the quantized version of term frequencies. This is comparable to lossless coding techniques such as unary, γ and δ-codes. However, if lossless coding is applied to the quantized term frequency values, then around 26% (or 12%) savings can be achieved over lossless coding alone, with less than 2.5% (or no measurable) degradation in retrieval performance.

M3 - Book chapter

SP - 277

EP - 287

BT - Active Media Technology

PB - Springer Science+Business Media

ER -

Term frequency quantization for compressing an inverted index

Abstract

Fingerprint

Cite this