Effective construction of relative lempel-ziv dictionaries

Kewen Liao, Matthias Petri, Alistair Moffat, Anthony Wirth

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


Web crawls generate vast quantities of text, retained and archived by the search services that initiate them. To store such data and to allow storage costs to be minimized, while still providing some level of random access to the compressed data, efficient and effective compression techniques are critical. The Relative Lempel Ziv (RLZ) scheme provides fast decompression and retrieval of documents from within large compressed collections, and even with a relatively small RAM-resident dictionary, is competitive relative to adaptive compression schemes. To date, the dictionaries required by RLZ compression have been formed from concatenations of substrings regularly sampled from the underlying document collection, then pruned in a manner that seeks to retain only the high-use sections. In this work, we develop new dictionary design heuristics, based on effective construction, rather than on pruning; we identify dictionary construction as a (string) covering problem. To avoid the complications of string covering algorithms on large collections, we focus on k-mers and their frequencies. First, with a reservoir sampler, we efficiently identify the most common k-mers. Then, since a collection typically comprises regions of local similarity, we select in each "epoch" a segment whose k-mers together achieve, locally, the highest coverage score. The dictionary is formed from the concatenation of these epoch-derived segments. Our selection process is inspired by the greedy approach to the Set Cover problem. Compared with the best existing pruning method, CARE, our scheme has a similar construction time, but achieves better compression effectiveness. Over several multi-gigabyte document collections, there are relative gains of up to 27%.

Original languageEnglish
Title of host publication25th International World Wide Web Conference, WWW 2016
PublisherInternational World Wide Web Conferences Steering Committee
Number of pages10
ISBN (Electronic)9781450341431
Publication statusPublished - 2016
Externally publishedYes
Event25th International World Wide Web Conference, WWW 2016 - Montreal, Canada
Duration: 11 Apr 201615 Apr 2016


Conference25th International World Wide Web Conference, WWW 2016


Dive into the research topics of 'Effective construction of relative lempel-ziv dictionaries'. Together they form a unique fingerprint.

Cite this