Publications
Search

Publications :: Search

Dictionary-based Order-preserving String Compression for Main Memory Column Stores

Show publication

On this page you see the details of the selected publication.

    Publication properties
    Title: Dictionary-based Order-preserving String Compression for Main Memory Column Stores
    Rating: (1)
    Discussion: 0 comments
    Date: 2009
    Publication type: Conference paper
    Authors:
    No. First name Last name Show
    1. Carsten Binnig
    2. Stefan Hildenbrand
    3. Franz Färber
    Download (by DOI): 10.1145/1559845.1559877
    BibTeX: conf/sigmod/BinnigHF09
    DBLP: db/conf/sigmod/sigmod2009.html#BinnigHF09
    Bookmark:

    The following keywords have been assigned to this publication so far. If you have logged in, you can tag this publication with additional keywords.

    Keywords
    No keywords have been assigned to this publication yet.

    If you log in you can tag this publication with additional keywords

    A publication can refer to another publication (outgoing references) or it can be referred to by other publications (incoming references).

    Incoming References
    No incoming references have been assigned to this publication yet.
    Outgoing References
    No outgoing references have been assigned to this publication yet.

    If you log in you can add references to other publications

    A publication can be assigned to a conference, a journal or a school.

    Conference Track
    Conference Name: ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009 2009
    Track Name: Research
    URL: http://www.sigmod09.org/

    Abstract

    Column-oriented database systems have shown to perform better than traditional row-oriented database systems on analytical workloads found in decision support and business intelligence applications. Moreover, lightweight compression schemes have shown to significantly improve the query processing performance in these systems. One such a lightweight compression scheme is to use a dictionary in order to replace long (variable-length) values of a certain domain with shorter (fixed-size) integer codes. In order to further improve expensive query operations such as sorting and searching, column-stores often use order-preserving encoding schemes for a dictionary.

    In contrast to the existing work, we argue that a dictionary-based order-preserving compression scheme does not only pay-off for attributes with a small fixed domain size but also for long string attributes with a large domain size which might change over time. Consequently, in this paper we introduce new data structures that efficiently support a dictionary-based order-preserving compression for (variable-length) string attributes with a large domain size that is likely to change over time. The main idea is that we model a dictionary as a table that specifies a mapping from string-values to arbitrary integer codes (and vice versa). Moreover, we introduce a new indexing approach that provides efficient access paths to such a dictionary while compressing the index data. Our experiments show that our data structures are as fast as (or in some cases even faster than) other state-of-the-art data structures for dictionaries while being less memory intensive.