Rank and select operations on a word

DOI10.1016/J.IPL.2021.106148zbMATH Open1472.68047OpenAlexW3171930374MaRDI QIDQ2234779FDOQ2234779

Authors: Meng Zhang, Yi Zhang 

Publication date: 19 October 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106148

Recommendations

• Experimental and Efficient Algorithms
• Optimal indexes for sparse bit vectors
• Lower bounds on the size of selection and rank indexes
• Adaptive succinctness
• Optimal lower bounds for rank and select indexes

zbMATH Keywords

pattern matchingsuccinct data structuresword parallelism

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cites Work

• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Surpassing the information theoretic bound with fusion trees
• Towards optimal packed string matching
• Fast convolutions of packed strings and pattern matching with wildcards
• Title not available (Why is that?)
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• Title not available (Why is that?)
• Trans-dichotomous algorithms without multiplication — some upper and lower bounds

Cited In (3)

• Lower bounds on the size of selection and rank indexes
• High-order entropy compressed bit vectors with rank/select
• Experimental and Efficient Algorithms

This page was built for publication: Rank and select operations on a word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234779)