Sketching

Includes API to compute HyperLoglog sketches for the cardinality/size estimates for the layout algorithm. More...

Topics
	Toolbox
	Algorithms for union estimation and similarity rearrangement executed before computing the layout.

Classes
class	seqan::hibf::sketch::hyperloglog
	HyperLogLog estimates. More...

Functions
void	seqan::hibf::sketch::estimate_kmer_counts (std::vector< seqan::hibf::sketch::hyperloglog > const &sketches, std::vector< size_t > &kmer_counts)
	Estimates k-mer counts via sketches.
constexpr uint64_t	seqan::hibf::sketch::wyhash (uint64_t const value) noexcept
	Mixes the bits of value: the 128-bit product with a 64-bit constant, folded to 64 bits via XOR.

Detailed Description

Includes API to compute HyperLoglog sketches for the cardinality/size estimates for the layout algorithm.

Function Documentation

wyhash()

constexpr uint64_t seqan::hibf::sketch::wyhash ( uint64_t const value )

constexprnoexcept

Mixes the bits of value: the 128-bit product with a 64-bit constant, folded to 64 bits via XOR.

wyhash(0) == 0: the value 0 (e.g. the k-mer AA...A in a 2-bit encoding) always becomes the smallest possible hash. It is therefore the smallest value of the first MinHash sketch of every user bin that contains it, and it sets register 0 of a HyperLogLog sketch to the maximal rank. To avoid this, XOR value with a constant before the multiplication; the input that is mapped to 0 is then this constant. This changes every hash, so sketches computed before and after the change are not comparable.

See also

https://github.com/wangyi-fudan/wyhash

Simpler than murmur3: https://godbolt.org/z/bz7fd4aYz