research-article

ANS-Based Index Compression

Authors:

Alistair Moffat,

Matthias PetriAuthors Info & Claims

CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

Pages 677 - 686

https://doi.org/10.1145/3132847.3132888

Published: 06 November 2017 Publication History

Abstract

Techniques for effectively representing the postings lists associated with inverted indexes have been studied for many years. Here we combine the recently developed "asymmetric numeral systems" (ANS) approach to entropy coding and a range of previous index compression methods, including VByte, Simple, and Packed. The ANS mechanism allows each of them to provide markedly improved compression effectiveness, at the cost of slower decoding rates. Using the 426 GB GOV2 collection, we show that the combination of blocking and ANS-based entropy-coding against a set of 16 magnitude-based probability models yields compression effectiveness superior to most previous mechanisms, while still providing reasonable decoding speed.

References

[1]

V. N. Anh and A. Moffat. Inverted index compression using word-aligned binary codes. Inf. Retr., 8 (1): 151--166, 2005.

Digital Library

[2]

V. N. Anh and A. Moffat. Index compression using 64-bit words. Soft. Prac. & Exp., 40 (2): 131--147, 2010.

Digital Library

[3]

, Navarro, and Esteller}bfne03spireN. R. Brisaboa, A. Fari na, G. Navarro, and M. F. Esteller. $(S, C)$-Dense coding: An optimized compression code for natural language text databases. In Proc. SPIRE, pages 122--136, 2003.

[4]

, Ladra, and Navarro}bfln08sigirN. R. Brisaboa, A. Fari na, S. Ladra, and G. Navarro. Reorganizing compressed text. In Proc. SIGIR, pages 139--146, 2008.

Digital Library

[5]

Y. Choueka, A. S. Fraenkel, and S. T. Klein. Compression of concordances in full-text retrieval systems. In Proc. SIGIR, pages 597--612, 1988.

Digital Library

[6]

J. S. Culpepper and A. Moffat. Enhanced byte codes with restricted prefix properties. In Proc. SPIRE, pages 1--12, 2005.

Digital Library

[7]

C. Dimopoulos, S. Nepomnyachiy, and T. Suel. Optimizing top-k document retrieval strategies for block-max indexes. In Proc. WSDM, pages 113--122, 2013.

Digital Library

[8]

S. Ding and T. Suel. Faster top-k document retrieval using block-max indexes. In Proc. SIGIR, pages 993--1002, 2011.

Digital Library

[9]

J. Duda. Asymmetric numeral systems. CoRR, abs/0902.0271, 2009. URL http://arxiv.org/abs/0902.0271.

[10]

J. Duda. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. CoRR, abs/1311.2540, 2013. URL http://arxiv.org/abs/1311.2540.

[11]

A. S. Fraenkel and S. T. Klein. Novel compression of sparse bit-strings: Preliminary report. In Combinatorial Algorithms on Words, Volume 12, NATO ASI Series F, pages 169--183. Springer, 1985.

[12]

F. Giesen. Interleaved entropy coders. CoRR, abs/1402.3392, 2014.

[13]

D. Lemire and L. Boytsov. Decoding billions of integers per second through vectorization. Soft. Prac. & Exp., 45 (1): 1--29, 2015.

Digital Library

[14]

A. Moffat and L. Stuiver. Binary interpolative coding for effective index compression. Inf. Retr., 3 (1): 25--47, 2000.

Digital Library

[15]

A. Moffat and A. Turpin. Compression and Coding Algorithms. Kluwer, Boston, 2002.

Digital Library

[16]

A. Moffat and J. Zobel. Parameterised compression for sparse bitmaps. In Proc. SIGIR, pages 274--285, 1992.

Digital Library

[17]

G. Ottaviano and R. Venturini. Partitioned Elias-Fano indexes. In Proc. SIGIR, pages 273--282, 2014.

Digital Library

[18]

G. Ottaviano, N. Tonellotto, and R. Venturini. Optimal space-time tradeoffs for inverted indexes. In Proc. WSDM, pages 47--56, 2015.

Digital Library

[19]

A. Trotman. Compressing inverted files. Inf. Retr., 6 (1): 5--19, 2003.

Digital Library

[20]

A. Trotman. Compression, SIMD, and postings lists. In Proc. Aust. Doc. Comp. Symp., page 50, 2014.

Digital Library

[21]

A. Trotman, M. Albert, and B. Burgess. Optimal packing in Simple-family codecs. In Proc. ICTIR, pages 337--340, 2015.

Digital Library

[22]

J. Wang, C. Lin, R. He, M. Chae, Y. Papakonstantinou, and S. Swanson. MILC: Inverted list compression in memory. PVLDB, 10 (8): 853--864, 2017.

Digital Library

[23]

H. E. Williams and J. Zobel. Compressing integers for fast file access. Comp. J., 42 (3): 193--201, 1999.

[24]

I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 1999.

Digital Library

[25]

H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In Proc. WWW, pages 401--410, 2009.

Digital Library

[26]

J. Zhang, X. Long, and T. Suel. Performance of compressed inverted list caching in search engines. In Proc. WWW, pages 387--396, 2008.

Digital Library

[27]

Z. Zhang, J. Tong, H. Huang, J. Liang, T. Li, R. J. Stones, G. Wang, and X. Liu. Leveraging context-free grammar for efficient inverted index compression. In Proc. SIGIR, pages 275--284, 2016.

Digital Library

[28]

an, Nes, and Boncz}zhnb06icdeM. Zukowski, S. Héman, N. Nes, and P. A. Boncz. Super-scalar RAM-CPU cache compression. In Proc. ICDE, page 59, 2006.

Digital Library

Cited By

Yamamoto HIwata K(2024)An Asymmetric Encoding - Decoding Scheme for Lossless Data Compression2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619702(55-60)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619702
Strutz T(2023)Rescaling of Symbol Counts for Adaptive rANS Coding2023 31st European Signal Processing Conference (EUSIPCO)10.23919/EUSIPCO58844.2023.10289961(585-589)Online publication date: 4-Sep-2023
https://doi.org/10.23919/EUSIPCO58844.2023.10289961
Li MLiu YWang N(2023)A Novel ANS Coding with Low Computational Complexity2023 IEEE/CIC International Conference on Communications in China (ICCC Workshops)10.1109/ICCCWorkshops57813.2023.10233773(1-6)Online publication date: 10-Aug-2023
https://doi.org/10.1109/ICCCWorkshops57813.2023.10233773
Show More Cited By

Index Terms

ANS-Based Index Compression
1. Information systems

Recommendations

Index Compression Using Byte-Aligned ANS Coding and Two-Dimensional Contexts
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining

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 ...
Improved index compression techniques for versioned document collections
CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge management

Current Information Retrieval systems use inverted index structures for efficient query processing. Due to the extremely large size of many data sets, these index structures are usually kept in compressed form, and many techniques for optimizing ...
Optimizing partitioning strategies for faster inverted index compression

The inverted index is a key component for search engines to manage billions of documents and quickly respond to users' queries.Whereas substantial effort has been devoted to reducing space occupancy and decoding speed, the encoding speed when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

November 2017

2604 pages

ISBN:9781450349185

DOI:10.1145/3132847

General Chairs:
Ee-Peng Lim
Singapore Management University, Singapore
,
Marianne Winslett
University of Illinois at Urbana-Champaign, USA, and Advanced Digital Sciences Center, Singapore
,
Program Chairs:
Mark Sanderson
RMIT, Australia
,
Ada Fu
Chinese University of Hong Kong, Hong Kong
,
Jimeng Sun
Georgia Tech, USA
,
Shane Culpepper
RMIT, Australia
,
Eric Lo
Chinese University of Hong Kong, Hong Kong
,
Joyce Ho
Emory University, USA
,
Debora Donato
Mix Tech, Inc., USA
,
Rakesh Agrawal
Data Insights Laboratories, USA
,
Yu Zheng
Microsoft Research Asia, China
,
Carlos Castillo
Qatar Computing Research Institute, Qatar
,
Aixin Sun
Nanyang Technological University, Singapore
,
Vincent S. Tseng
National Cheng Kung University, Taiwan
,
Chenliang Li
Wuhan University, China

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council

Conference

CIKM '17

Sponsor:

CIKM '17: ACM Conference on Information and Knowledge Management

November 6 - 10, 2017

Singapore, Singapore

Acceptance Rates

CIKM '17 Paper Acceptance Rate 171 of 855 submissions, 20%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
1,103
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yamamoto HIwata K(2024)An Asymmetric Encoding - Decoding Scheme for Lossless Data Compression2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619702(55-60)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619702
Strutz T(2023)Rescaling of Symbol Counts for Adaptive rANS Coding2023 31st European Signal Processing Conference (EUSIPCO)10.23919/EUSIPCO58844.2023.10289961(585-589)Online publication date: 4-Sep-2023
https://doi.org/10.23919/EUSIPCO58844.2023.10289961
Li MLiu YWang N(2023)A Novel ANS Coding with Low Computational Complexity2023 IEEE/CIC International Conference on Communications in China (ICCC Workshops)10.1109/ICCCWorkshops57813.2023.10233773(1-6)Online publication date: 10-Aug-2023
https://doi.org/10.1109/ICCCWorkshops57813.2023.10233773
Hsieh PWu J(2022)A Review of the Asymmetric Numeral System and Its Applications to Digital ImagesEntropy10.3390/e2403037524:3(375)Online publication date: 7-Mar-2022
https://doi.org/10.3390/e24030375
Brisaboa NFariña AGalaktionov DRodeiro TRodriguez M(2022)Improved structures to solve aggregated queries for trips over public transportation networksInformation Sciences: an International Journal10.1016/j.ins.2021.10.079584:C(752-783)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.ins.2021.10.079
Blanes IHernandez-Cabronero MSerra-Sagrista JMarcellin M(2021)Redundancy and Optimization of tANS Entropy EncodersIEEE Transactions on Multimedia10.1109/TMM.2020.304054723(4341-4350)Online publication date: 2021
https://doi.org/10.1109/TMM.2020.3040547
Pibiri GVenturini R(2020)Techniques for Inverted Index CompressionACM Computing Surveys10.1145/341514853:6(1-36)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.1145/3415148
Moffat A(2019)Huffman CodingACM Computing Surveys10.1145/334255552:4(1-35)Online publication date: 30-Aug-2019
https://dl.acm.org/doi/10.1145/3342555
Pibiri GPetri MMoffat ACulpepper JMoffat ABennett PLerman K(2019)Fast Dictionary-Based Compression for Inverted IndexesProceedings of the Twelfth ACM International Conference on Web Search and Data Mining10.1145/3289600.3290962(6-14)Online publication date: 30-Jan-2019
https://dl.acm.org/doi/10.1145/3289600.3290962
Dube DYokoo H(2019)Fast Construction of Almost Optimal Symbol Distributions for Asymmetric Numeral Systems2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849430(1682-1686)Online publication date: Jul-2019
https://doi.org/10.1109/ISIT.2019.8849430
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents