https://arxiv.org/abs/1603.06549

Skip to main content
Cornell University
We gratefully acknowledge support from the Simons Foundation, member
institutions, and all contributors. Donate
 
arxiv logo > cs > arXiv:1603.06549
[                    ]

Help | Advanced Search

[All fields        ]
Search
arXiv logo
Cornell University Logo
[                    ] GO
quick links

  * Login
  * Help Pages
  * About

Computer Science > Databases

arXiv:1603.06549 (cs)
[Submitted on 21 Mar 2016 (v1), last revised 2 Mar 2018 (this
version, v4)]

Title:Consistently faster and smaller compressed bitmaps with Roaring

Authors:Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser
View a PDF of the paper titled Consistently faster and smaller
compressed bitmaps with Roaring, by Daniel Lemire and 2 other authors
View PDF

    Abstract:Compressed bitmap indexes are used in databases and
    search engines. Many bitmap compression techniques have been
    proposed, almost all relying primarily on run-length encoding
    (RLE). However, on unsorted data, we can get superior performance
    with a hybrid compression technique that uses both uncompressed
    bitmaps and packed arrays inside a two-level tree. An instance of
    this technique, Roaring, has recently been proposed. Due to its
    good performance, it has been adopted by several production
    platforms (e.g., Apache Lucene, Apache Spark, Apache Kylin and
    Druid).
    Yet there are cases where run-length encoded bitmaps are smaller
    than the original Roaring bitmaps---typically when the data is
    sorted so that the bitmaps contain long compressible runs. To
    better handle these cases, we build a new Roaring hybrid that
    combines uncompressed bitmaps, packed arrays and RLE compressed
    segments. The result is a new Roaring format that compresses
    better.
    Overall, our new implementation of Roaring can be several times
    faster (up to two orders of magnitude) than the implementations
    of traditional RLE-based alternatives (WAH, Concise, EWAH) while
    compressing better. We review the design choices and
    optimizations that make these good results possible.

Subjects:          Databases (cs.DB)
Cite as:           arXiv:1603.06549 [cs.DB]
                   (or arXiv:1603.06549v4 [cs.DB] for this version)
                   https://doi.org/10.48550/arXiv.1603.06549
                   Focus to learn more
                   arXiv-issued DOI via DataCite
Journal reference: Software: Practice and Experience Volume 46, Issue
                   11, pages 1547-1569, November 2016
                   https://doi.org/10.1002/spe.2402
Related DOI:       Focus to learn more
                   DOI(s) linking to related resources

Submission history

From: Daniel Lemire [view email]
[v1] Mon, 21 Mar 2016 19:30:53 UTC (38 KB)
[v2] Tue, 19 Apr 2016 14:19:05 UTC (41 KB)
[v3] Sat, 8 Oct 2016 16:31:17 UTC (38 KB)
[v4] Fri, 2 Mar 2018 18:35:46 UTC (38 KB)
Full-text links:

Access Paper:

    View a PDF of the paper titled Consistently faster and smaller
    compressed bitmaps with Roaring, by Daniel Lemire and 2 other
    authors
  * View PDF
  * TeX Source
  * Other Formats

license icon view license
Current browse context:
cs.DB
< prev   |   next >
new | recent | 2016-03
Change to browse by:
cs

References & Citations

  * NASA ADS
  * Google Scholar
  * Semantic Scholar

DBLP - CS Bibliography

listing | bibtex
Daniel Lemire
Gregory Ssi Yan Kai
Owen Kaser
a export BibTeX citation Loading...

BibTeX formatted citation

x
[loading...          ]
Data provided by:

Bookmark

BibSonomy logo Reddit logo
(*) Bibliographic Tools

Bibliographic and Citation Tools

[ ] Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
[ ] Connected Papers Toggle
Connected Papers (What is Connected Papers?)
[ ] Litmaps Toggle
Litmaps (What is Litmaps?)
[ ] scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
( ) Code, Data, Media

Code, Data and Media Associated with this Article

[ ] alphaXiv Toggle
alphaXiv (What is alphaXiv?)
[ ] Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
[ ] DagsHub Toggle
DagsHub (What is DagsHub?)
[ ] GotitPub Toggle
Gotit.pub (What is GotitPub?)
[ ] Huggingface Toggle
Hugging Face (What is Huggingface?)
[ ] Links to Code Toggle
Papers with Code (What is Papers with Code?)
[ ] ScienceCast Toggle
ScienceCast (What is ScienceCast?)
( ) Demos

Demos

[ ] Replicate Toggle
Replicate (What is Replicate?)
[ ] Spaces Toggle
Hugging Face Spaces (What is Spaces?)
[ ] Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
( ) Related Papers

Recommenders and Search Tools

[ ] Link to Influence Flower
Influence Flower (What are Influence Flowers?)
[ ] Core recommender toggle
CORE Recommender (What is CORE?)

  * Author
  * Venue
  * Institution
  * Topic

( ) About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and
share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have
embraced and accepted our values of openness, community, excellence,
and user data privacy. arXiv is committed to these values and only
works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community?
Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is
MathJax?)

  * About
  * Help

  * Click here to contact arXiv Contact
  * Click here to subscribe Subscribe

  * Copyright
  * Privacy Policy

  * Web Accessibility Assistance
  * arXiv Operational Status
    Get status notifications via email or slack