File RowFingerprint.h

↰ Parent directory (ADS/dictionary)

The fingerprints of the rows of doubles, beyond the book: a hash of 64 bits of a dense row :math:` ( x_0 , dots , x_{n-1} ) ` or of a sparse one, its indices and values :math:` ( j_k , v_k ) ` in their order, for finding the rows already seen, e.g., a cut generated twice, by a table of the fingerprints; sameRow() then tells whether two rows with the same fingerprint are really equal.

Definition (ADS/dictionary/RowFingerprint.h)

Detailed Description

The values are compared as numbers, not as bit patterns: +0 and -0 are equal, and so are all the NaNs (whatever their sign and payload), which the comparison of the doubles does not do. A value is hence mapped to a canonical word before it is hashed: 0 for both zeros, the quiet NaN :math:` 7FF8 ldots 0_{16} ` for every NaN, its own bits otherwise; two rows equal in this sense have the same words, hence the same fingerprint. The words are canonical a block of 64 at a time, by comparisons and blends that the compiler turns into vector operations, and each block of 512 bytes goes through hashBytes() [see File FastHash.h], the hash of the previous block as its seed, so that a row costs about what its bytes cost to hash; a sparse row hashes its indices, as bytes, then its values.

Two rows with different words collide with probability about :math:` 2^{-64} ` for a hash that behaves at random, so that a table of :math:` k ` fingerprints holds a false match with probability about :math:` k^2 2^{-65} ` [the birthday bound]; but hashBytes() is not cryptographic, so a match is confirmed by sameRow(), in time linear in the row: first a comparison of the bytes of the two rows, which the library does by vectors and which settles the common case of two copies of the same row, then, if some byte differs, the comparison of the values as numbers. The fingerprint of a dense row differs from that of the same row as a sparse one, and the order of the indices of a sparse row counts.

The contracts [see File Contract.h]: a sparse row has pointers that are not nil when it has entries. The functions are defined in RowFingerprint.tpp.

    1. Rabin, Fingerprinting by random polynomials, Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981 (the identity of objects by short fingerprints)

IEEE Standard for Floating-Point Arithmetic, IEEE Std 754-2019, 2019, doi:10.1109/IEEESTD.2019.8766229 (the zeros and the NaNs)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/dictionary/FastHash.h (File FastHash.h)

  • ADS/dictionary/impl/RowFingerprint.tpp

  • bit

  • cstddef

  • cstdint

  • cstring

  • span

  • type_traits

Namespaces

Functions