View in EDS

Zombit: Exploiting Runs in Bitvectors.

Saved in:
Bibliographic Details
Title: Zombit: Exploiting Runs in Bitvectors.
Authors: Gómez‐Brandón, Adrián1 (AUTHOR) adrian.gbrandon@udc.es
Source: Software: Practice & Experience. Dec2025, Vol. 55 Issue 12, p1975-1992. 18p.
Subjects: Data structures, Run-length encoding, Binary sequences, Encoding, Time complexity
Abstract: Introduction: Bitvectors are a fundamental building block of many compact data structures. In this work, we propose a new compressed representation for bitvectors, named zombit‐vector, which compresses bitvectors with k$$ k $$ runs by splitting the bitvector into fixed‐length blocks and classifying them into three possible types depending on their content. Methods: It supports the typical operations over bitvectors in O(1)$$ O(1) $$ time, but select in O(logn)$$ O\left(\log n\right) $$ time. The total space required for this structure is O(kn)+o(kn)$$ O\left(\sqrt{kn}\right)+o\left(\sqrt{kn}\right) $$ bits. In addition, we introduce an extension pzombit‐vector where the blocks have variable length. The variable‐length partitioning adapts better to the distribution of the data, reducing space needs but requiring O(logn)$$ O\left(\log n\right) $$ time for all operations. Results: We include experiments on synthetic data and over two real‐world scenarios. The synthetic scenario shows the competitiveness of our techniques against well‐known state‐of‐the‐art alternatives. That experiment confirms that pzombit‐vector is able to use one‐tenth of zombit‐vector, but becomes 5 times slower. Our experiments with real applications demonstrate that the proposed techniques are practical and applicable in real‐world scenarios. [ABSTRACT FROM AUTHOR]
Copyright of Software: Practice & Experience is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 190792919
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Zombit: Exploiting Runs in Bitvectors.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Gómez‐Brandón%2C+Adrián%22">Gómez‐Brandón, Adrián</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> adrian.gbrandon@udc.es</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Software%3A+Practice+%26+Experience%22">Software: Practice & Experience</searchLink>. Dec2025, Vol. 55 Issue 12, p1975-1992. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Run-length+encoding%22">Run-length encoding</searchLink><br /><searchLink fieldCode="DE" term="%22Binary+sequences%22">Binary sequences</searchLink><br /><searchLink fieldCode="DE" term="%22Encoding%22">Encoding</searchLink><br /><searchLink fieldCode="DE" term="%22Time+complexity%22">Time complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Introduction: Bitvectors are a fundamental building block of many compact data structures. In this work, we propose a new compressed representation for bitvectors, named zombit‐vector, which compresses bitvectors with k$$ k $$ runs by splitting the bitvector into fixed‐length blocks and classifying them into three possible types depending on their content. Methods: It supports the typical operations over bitvectors in O(1)$$ O(1) $$ time, but select in O(logn)$$ O\left(\log n\right) $$ time. The total space required for this structure is O(kn)+o(kn)$$ O\left(\sqrt{kn}\right)+o\left(\sqrt{kn}\right) $$ bits. In addition, we introduce an extension pzombit‐vector where the blocks have variable length. The variable‐length partitioning adapts better to the distribution of the data, reducing space needs but requiring O(logn)$$ O\left(\log n\right) $$ time for all operations. Results: We include experiments on synthetic data and over two real‐world scenarios. The synthetic scenario shows the competitiveness of our techniques against well‐known state‐of‐the‐art alternatives. That experiment confirms that pzombit‐vector is able to use one‐tenth of zombit‐vector, but becomes 5 times slower. Our experiments with real applications demonstrate that the proposed techniques are practical and applicable in real‐world scenarios. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Software: Practice & Experience is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=190792919
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1002/spe.70019
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 1975
    Subjects:
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: Run-length encoding
        Type: general
      – SubjectFull: Binary sequences
        Type: general
      – SubjectFull: Encoding
        Type: general
      – SubjectFull: Time complexity
        Type: general
    Titles:
      – TitleFull: Zombit: Exploiting Runs in Bitvectors.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Gómez‐Brandón, Adrián
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 12
              Text: Dec2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 00380644
          Numbering:
            – Type: volume
              Value: 55
            – Type: issue
              Value: 12
          Titles:
            – TitleFull: Software: Practice & Experience
              Type: main
ResultId 1