Compression can sometimes improve performance by making more of the data available to the processors faster. We consider the compression of integer keys in a B+-tree index. For this purpose, systems such as IBM DB2 use variable-byte compression over differentially coded keys. We revisit this problem with various compression alternatives such as Google's VarIntGB, Binary Packing and Frame-of-Reference. In all cases, we describe algorithms that can operate directly on compressed data. Many of our alternatives exploit the single-instruction-multiple-data (SIMD) instructions supported by modern CPUs. We evaluate our techniques in a database environment provided by Upscaledb, a production-quality key-value database. Our best techniques are SIMD accelerated: they simultaneously reduce memory usage while improving single-threaded speeds. In particular, a differentially coded SIMD binary-packing techniques (BP128) can offer a superior query speed (e.g., 40 better than an uncompressed database) while providing the best compression (e.g., by a factor of ten). For analytic workloads, our fast compression techniques offer compelling benefits. Our software is available as open source.
Random access in differentially-coded compressed arrays is often made possible with auxiliary data structures that allow skipping @cite_9 @cite_5 . However, there are alternatives to differential coding that offer more convenient random access. @cite_3 propose differentially encoded search trees; Teuhola @cite_19 adapts interpolative coding @cite_7 so that it can support logarithmic search. @cite_38 modify variable-byte encoding to create Directly Addressable Codes (DACs)---so that one can have access to individual coded value in constant time using rank select dictionaries. This strategy is applied to other compression schemes by K "ulekci @cite_44 . There has also been much interest in variations on the Elias-Fano representation @cite_39 @cite_37 , as it can provide good compression and fast random access to the encoded values. Other techniques such as wavelet trees @cite_2 or bitmap indexes @cite_4 @cite_22 @cite_31 @cite_21 can also be used for similar purposes.
@cite_38 @cite_37 @cite_4 @cite_22 @cite_7 @cite_9 @cite_21 @cite_3 @cite_39 @cite_44 @cite_19 @cite_2 @cite_5 @cite_31
2093408358 2037892395 2131143419 2053518549
Sequences of integers are common data types, occurring either as primary data or ancillary structures. The sizes of sequences can be large, making compression an interesting option. Effective compression presupposes variable-length coding, which destroys the regular alignment of values. Yet it would often be desirable to access only a small subset of the entries, either by position (ordinal number) or by content (element value), without having to decode most of the sequence from the start. Here such a random access technique for compressed integers is described, with the special feature that no auxiliary index is needed. The solution applies a method called interpolative coding, which is one of the most efficient non-statistical codes for integers. Indexing is avoided by address calculation guaranteeing sufficient space for codes even in the worst case. The additional redundancy, compared to regular interpolative coding, is only about 1bit per source integer for uniform distribution. The time complexity of random access is logarithmic with respect to the source size for both position-based and content-based retrieval. According to experiments, random access is faster than full decoding when the number of accessed integers is not more than approximately 0.75.n log"2n for sequence length n. The tests also confirm that the method is quite competitive with other approaches to random access coding, suggested in the literature. We investigate the usage of the wavelet tree and the rank select-dictionary data structures on hybrid-structured variable-length codes, which represent an integer in the form of a unary code section followed by a binary section. We propose to handle unary and binary partitions as separate streams and create wavelet trees or R S dictionaries over the unary streams, which grants us the opportunity to directly access any codeword. Particularly concentrating on Elias and Rice schemes, we introduce several solutions that i) improve the compression significantly, and ii) provide random access in constant or logarithmic time. Experiments are conducted to compare the performances of the proposed codes against Elias Rice schemes and more recent state-of-the-art codings such as Simple9, PForDelta,DACs, and improved-AC techniques. We observed that the newly introduced methods outperform the original Elias Rice codecs by approximately 30 and the others by approximately 10 in terms of compression ratios. The methods described in this study are generic and may further be extended to some other hybrid structure (unary binary) variable-length codes as well. Sorted lists of integers are commonly used in inverted indexes and database systems. They are often compressed in memory. We can use the single-instruction, multiple data SIMD instructions available in common processors to boost the speed of integer compression schemes. Our S4-BP128-D4 scheme uses as little as 0.7CPU cycles per decoded 32-bit integer while still providing state-of-the-art compression. However, if the subsequent processing of the integers is slow, the effort spent on optimizing decompression speed can be wasted. To show that it does not have to be so, we 1 vectorize and optimize the intersection of posting lists; 2 introduce the SIMD GALLOPING algorithm. We exploit the fact that one SIMD instruction can compare four pairs of 32-bit integers at once. We experiment with two Text REtrieval Conference TREC text collections, GOV2 and ClueWeb09 category B, using logs from the TREC million-query track. We show that using only the SIMD instructions ubiquitous in all modern CPUs, our techniques for conjunctive queries can double the speed of a state-of-the-art approach. Copyright © 2015 John Wiley & Sons, Ltd. Let X=x"1,x"2,...,x"n be a sequence of non-decreasing integer values. Storing a compressed representation of X that supports access and search is a problem that occurs in many domains. The most common solution to this problem uses a linear list and encodes the differences between consecutive values with encodings that favor small numbers. This solution includes additional information (i.e. samples) to support efficient searching on the encoded values. We introduce a completely different alternative that achieves compression by encoding the differences in a search tree. Our proposal has many applications, such as the representation of posting lists, geographic data, sparse bitmaps, and compressed suffix arrays, to name just a few. The structure is practical and we provide an experimental evaluation to show that it is competitive with the existing techniques.