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.

Originalsprog	Engelsk
Titel	Active Media Technology
Antal sider	11
Forlag	Springer Science+Business Media
Publikationsdato	2010
Sider	277-287
Status	Udgivet - 2010
Udgivet eksternt	Ja

Citationsformater

@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

Fingeraftryk

Citationsformater