Scholarlink

<p>Adding rank support to strings over a fixed-sized alphabet has numerous applications. Prominent among those is the (bidirectional) FM-Index which is commonly utilized to index and analyze genomic data. At its core lies the <i>rank</i> operation on the Burrows-Wheeler-Transform (BWT) which, given a position in the BWT and a character, answers how often the specified character appears from the start to that position. Implementing those rank queries is usually based on bit vectors with rank support. In this work, we discuss three implementation improvements. First, a novel approach named <i>paired-blocks</i> that reduces the space overhead of the support structure by half to a total of only <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(1.6\%\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1.6</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation>. Second, a method for masking bits for the population count (also known as popcount) which greatly improves the runtime of 512-bit wide blocks in conjunction with AVX512 SIMD extensions. Third, a revised method for EPR-dictionaries (Pockrandt et al. in International conference on research in computational molecular biology. Springer, New York, 2017) called <i>flattened bit vectors</i> (fBV) with less space consumption and faster rank operations on strings, which is competitive in size and depending on the parameters between <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(2\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(9\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>9</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> faster than Wavelet Trees (Gog et al. in 13th International Symposium on Experimental Algorithms. Springer, New York, 2014).</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Engineering rank queries on bit vectors and strings

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月11日

查看全文
  • Simon Gene Gottlieb,
  • Knut Reinert

摘要

Adding rank support to strings over a fixed-sized alphabet has numerous applications. Prominent among those is the (bidirectional) FM-Index which is commonly utilized to index and analyze genomic data. At its core lies the rank operation on the Burrows-Wheeler-Transform (BWT) which, given a position in the BWT and a character, answers how often the specified character appears from the start to that position. Implementing those rank queries is usually based on bit vectors with rank support. In this work, we discuss three implementation improvements. First, a novel approach named paired-blocks that reduces the space overhead of the support structure by half to a total of only \(1.6\%\) 1.6 % . Second, a method for masking bits for the population count (also known as popcount) which greatly improves the runtime of 512-bit wide blocks in conjunction with AVX512 SIMD extensions. Third, a revised method for EPR-dictionaries (Pockrandt et al. in International conference on research in computational molecular biology. Springer, New York, 2017) called flattened bit vectors (fBV) with less space consumption and faster rank operations on strings, which is competitive in size and depending on the parameters between \(2\times \) 2 × and \(9\times \) 9 × faster than Wavelet Trees (Gog et al. in 13th International Symposium on Experimental Algorithms. Springer, New York, 2014).