View in EDS

Engineering rank/select data structures for large-alphabet strings.

Saved in:
Bibliographic Details
Title: Engineering rank/select data structures for large-alphabet strings.
Authors: Arroyuelo, Diego1 (AUTHOR), Carmona, Gabriel2 (AUTHOR), Larrañaga, Héctor3 (AUTHOR), Riveros, Francisco3 (AUTHOR), Rojas-Morales, Carlos Eugenio3 (AUTHOR), Sepúlveda, Erick3 (AUTHOR)
Source: Computer Journal. Jan2026, Vol. 69 Issue 1, p108-132. 25p.
Subjects: Data structures, Run-length encoding, Natural language processing, Data compression, Information retrieval
Abstract: Large-alphabet strings, prevalent in information retrieval and natural language processing, pose unique storage and processing challenges. This paper explores the efficient implementation of the alphabet-partition approach, introducing a compressed data structure that efficiently supports the operations |${\mathsf{rank}}$| and |${\mathsf{select}}$|⁠. Our implementation significantly outperforms existing methods, improving the |${\mathsf{select}}$| operation speed by 80% with only 11% additional space. We demonstrate the utility of our structure in various applications, including inverted list intersections, run-length compressed strings, and distributed computation of |${\mathsf{rank}}$| and |${\mathsf{select}}$|⁠. Notably, for run-length compressed strings using the Burrows–Wheeler transform, our data structure requires only 0.98–1.09 times the space of state-of-the-art RLFM-indexes to achieve 1.23–2.33 times faster pattern occurrence counting while also providing better theoretical guarantees. [ABSTRACT FROM AUTHOR]
Copyright of Computer Journal is the property of Oxford University Press / USA 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: 191866089
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Engineering rank/select data structures for large-alphabet strings.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Arroyuelo%2C+Diego%22">Arroyuelo, Diego</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Carmona%2C+Gabriel%22">Carmona, Gabriel</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Larrañaga%2C+Héctor%22">Larrañaga, Héctor</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Riveros%2C+Francisco%22">Riveros, Francisco</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Rojas-Morales%2C+Carlos+Eugenio%22">Rojas-Morales, Carlos Eugenio</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Sepúlveda%2C+Erick%22">Sepúlveda, Erick</searchLink><relatesTo>3</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Computer+Journal%22">Computer Journal</searchLink>. Jan2026, Vol. 69 Issue 1, p108-132. 25p.
– 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="%22Natural+language+processing%22">Natural language processing</searchLink><br /><searchLink fieldCode="DE" term="%22Data+compression%22">Data compression</searchLink><br /><searchLink fieldCode="DE" term="%22Information+retrieval%22">Information retrieval</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Large-alphabet strings, prevalent in information retrieval and natural language processing, pose unique storage and processing challenges. This paper explores the efficient implementation of the alphabet-partition approach, introducing a compressed data structure that efficiently supports the operations |${\mathsf{rank}}$| and |${\mathsf{select}}$|⁠. Our implementation significantly outperforms existing methods, improving the |${\mathsf{select}}$| operation speed by 80% with only 11% additional space. We demonstrate the utility of our structure in various applications, including inverted list intersections, run-length compressed strings, and distributed computation of |${\mathsf{rank}}$| and |${\mathsf{select}}$|⁠. Notably, for run-length compressed strings using the Burrows–Wheeler transform, our data structure requires only 0.98–1.09 times the space of state-of-the-art RLFM-indexes to achieve 1.23–2.33 times faster pattern occurrence counting while also providing better theoretical guarantees. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Computer Journal is the property of Oxford University Press / USA 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=191866089
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1093/comjnl/bxaf102
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 25
        StartPage: 108
    Subjects:
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: Run-length encoding
        Type: general
      – SubjectFull: Natural language processing
        Type: general
      – SubjectFull: Data compression
        Type: general
      – SubjectFull: Information retrieval
        Type: general
    Titles:
      – TitleFull: Engineering rank/select data structures for large-alphabet strings.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Arroyuelo, Diego
      – PersonEntity:
          Name:
            NameFull: Carmona, Gabriel
      – PersonEntity:
          Name:
            NameFull: Larrañaga, Héctor
      – PersonEntity:
          Name:
            NameFull: Riveros, Francisco
      – PersonEntity:
          Name:
            NameFull: Rojas-Morales, Carlos Eugenio
      – PersonEntity:
          Name:
            NameFull: Sepúlveda, Erick
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 00104620
          Numbering:
            – Type: volume
              Value: 69
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Computer Journal
              Type: main
ResultId 1