Highly Compressed Lists of Integers with Dense Padding Modes

Kun JIANG; Xingshen SONG; Yuexiang YANG

doi:10.1587/transinf.2015EDL8102

Highly Compressed Lists of Integers with Dense Padding Modes

Kun JIANG, Xingshen SONG, Yuexiang YANG

Full Text Views

0

Share
Cite this

Summary :

Index compression is partially responsible for the current performance achievements of Internet search engines. Among many latest compression techniques, Simple9 can pack as many integers as possible into a single 32-bit machine word using 9 different padding modes. However, the number of wasted bits in Simple9 remains large. In previous works, researchers have focused on reducing the unused trailing bits of the padding modes and have proposed various additional modes that make full use of the cases of the status bits. Instead, we focus on the wasted bits in the integer list, padding extra zeros for a complete dense mode when the number of integers is not enough to fit a complete mode. More precisely, we first propose a novel index compression method called SimpleD with dense padding modes to achieve a more compact storage compared with that of Simple9. We then design an innovative metric for extracting the inserted extra zero integers during the decoding phase. Experiments on the TREC WT2G and GOV2 datasets show that our encoder outperforms Simple9 while still retaining a very fast decompression speed.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.11 pp.1986-1989

Publication Date: 2015/11/01

Publicized: 2015/08/19

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015EDL8102

Type of Manuscript: LETTER

Category: Data Engineering, Web Information Systems

Authors

Kun JIANG
  National University of Defense Technology
Xingshen SONG
  National University of Defense Technology
Yuexiang YANG
  National University of Defense Technology

Keyword

inverted indexes, index compression, dense padding mode, compression ratio

Cite this

Copy

Kun JIANG, Xingshen SONG, Yuexiang YANG, "Highly Compressed Lists of Integers with Dense Padding Modes" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 11, pp. 1986-1989, November 2015, doi: 10.1587/transinf.2015EDL8102.
Abstract: Index compression is partially responsible for the current performance achievements of Internet search engines. Among many latest compression techniques, Simple9 can pack as many integers as possible into a single 32-bit machine word using 9 different padding modes. However, the number of wasted bits in Simple9 remains large. In previous works, researchers have focused on reducing the unused trailing bits of the padding modes and have proposed various additional modes that make full use of the cases of the status bits. Instead, we focus on the wasted bits in the integer list, padding extra zeros for a complete dense mode when the number of integers is not enough to fit a complete mode. More precisely, we first propose a novel index compression method called SimpleD with dense padding modes to achieve a more compact storage compared with that of Simple9. We then design an innovative metric for extracting the inserted extra zero integers during the decoding phase. Experiments on the TREC WT2G and GOV2 datasets show that our encoder outperforms Simple9 while still retaining a very fast decompression speed.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015EDL8102/_p

Copy

@ARTICLE{e98-d_11_1986,
author={Kun JIANG, Xingshen SONG, Yuexiang YANG, },
journal={IEICE TRANSACTIONS on Information},
title={Highly Compressed Lists of Integers with Dense Padding Modes},
year={2015},
volume={E98-D},
number={11},
pages={1986-1989},
abstract={Index compression is partially responsible for the current performance achievements of Internet search engines. Among many latest compression techniques, Simple9 can pack as many integers as possible into a single 32-bit machine word using 9 different padding modes. However, the number of wasted bits in Simple9 remains large. In previous works, researchers have focused on reducing the unused trailing bits of the padding modes and have proposed various additional modes that make full use of the cases of the status bits. Instead, we focus on the wasted bits in the integer list, padding extra zeros for a complete dense mode when the number of integers is not enough to fit a complete mode. More precisely, we first propose a novel index compression method called SimpleD with dense padding modes to achieve a more compact storage compared with that of Simple9. We then design an innovative metric for extracting the inserted extra zero integers during the decoding phase. Experiments on the TREC WT2G and GOV2 datasets show that our encoder outperforms Simple9 while still retaining a very fast decompression speed.},
keywords={},
doi={10.1587/transinf.2015EDL8102},
ISSN={1745-1361},
month={November},}

Copy

TY - JOUR
TI - Highly Compressed Lists of Integers with Dense Padding Modes
T2 - IEICE TRANSACTIONS on Information
SP - 1986
EP - 1989
AU - Kun JIANG
AU - Xingshen SONG
AU - Yuexiang YANG
PY - 2015
DO - 10.1587/transinf.2015EDL8102
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2015
AB - Index compression is partially responsible for the current performance achievements of Internet search engines. Among many latest compression techniques, Simple9 can pack as many integers as possible into a single 32-bit machine word using 9 different padding modes. However, the number of wasted bits in Simple9 remains large. In previous works, researchers have focused on reducing the unused trailing bits of the padding modes and have proposed various additional modes that make full use of the cases of the status bits. Instead, we focus on the wasted bits in the integer list, padding extra zeros for a complete dense mode when the number of integers is not enough to fit a complete mode. More precisely, we first propose a novel index compression method called SimpleD with dense padding modes to achieve a more compact storage compared with that of Simple9. We then design an innovative metric for extracting the inserted extra zero integers during the decoding phase. Experiments on the TREC WT2G and GOV2 datasets show that our encoder outperforms Simple9 while still retaining a very fast decompression speed.
ER -