Compact inverted index storage using general‐purpose compression libraries. (17th January 2018)

• Record Type: Journal Article
• Authors: Petri, Matthias; Moffat, Alistair
• Is Part Of: Software, practice & experience. Volume 48:Number 4(2018)
• Page Start: 974
• Page End: 982
• Publication Date: 2018-01-17
• Subjects: index compression -- inverted index -- web search; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2556
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Efficient storage of large inverted indexes is one of the key technologies that support current web search services. Here we re‐examine mechanisms for representing document‐level inverted indexes and within‐document term frequencies, including comparing specialized methods developed for this task against recent fast implementations of general‐purpose adaptive compression techniques. Experiments with theGov2‐URL collection and a large collection of crawled news stories show that standard compression libraries can provide compression effectiveness as good as or better than previous methods, with decoding rates only moderately slower than reference implementations of those tailored approaches. This surprising outcome means that high‐performance index compression can be achieved without requiring the use of specialized implementations.