AbstractMotivationHigh throughput sequencing technologies generate massive amounts of biological sequence datasets as costs fall. One of the current algorithmic challenges for exploiting these data on a global scale consists in providing efficient query engines on these petabyte-scale datasets. Most methods indexing those datasets rely on indexing words of fixed lengthk, calledk-mers. Many applications, such as metagenomics, require the abundance of indexedk-mers as well as their simple presence or absence, but no method scales up to petabyte-scaled datasets. This deficiency is primarily because storing abundance requires explicit storage of thek-mers in order to associate them with their counts. Using counting Approximate Membership Queries (cAMQ) data structures, such as counting Bloom filters, provides a way to index large amounts ofk-mers with their abundance, but at the expense of a sensible false positive rate.ResultsWe propose a novel algorithm, calledfimpera, that enables the improvement of any cAMQ performance. Applied to counting Bloom filters, our proposed algorithm reduces the false positive rate by two orders of magnitude and it improves the precision of the reported abundances. Alternatively,fimperaallows for the reduction of the size of a counting Bloom filter by two orders of magnitude while maintaining the same precision.fimperadoes not introduce any memory overhead and may even reduces the query time.Availability and implementationhttps://github.com/lrobidou/fimpera.