8 releases

0.3.0 Aug 1, 2022
0.2.0 Nov 29, 2021
0.1.5 Nov 6, 2021
0.1.3 Oct 13, 2021
0.1.0 Sep 19, 2021

#1416 in Algorithms

MIT license

26KB
608 lines

IDHash

Efficiently create an identifiable hash for a dataset that is independent of row ordering but dependent of column ordering. The core purpose of IDHash is to identify quickly if two datasets are the same without requiring them to both be on the same machine, but also expands to being able to check if one dataset is a modified version of the other dataset if the modification is known upfront.

IDHash is based upon UNFv6, and details around UNF can be found here, where the major differences are that UNF is column-invariant but row-dependent, and IDHash is column-dependent and row-invariant.

Method Drawbacks

Duplicate Identification

Due to the requirement for row-invariance, a dataset of

    A    B
    1    2
    1    2
    1    2

will produce the same hash as;

    A    B
    1    2

But not the same as;

    A    B
    1    2
    1    2

In practice, this is relatively unlikely, and for the core purpose of datasets within Machine Learning, it is not a primary issue.

Preprocessing

Each column has specific pre-processing according to the UNF definition. This mostly consists of ensuring that floating point values and timestamps (currently unsupported in IDHash) are representable consistently across datasets when taking into account floating point epsilon.

Hash Generation

Each row is taken as a single bytestream, and hashed using Murmurhash128. Murmurhash is a non-cryptographically secure hash function that produces a well distributed hash for each individual value. By summing the individual hashed primitives, a final hash can be produced for the final dataset that does not take into account duplicates.

Checking for Equality + Delta

As the hashed rows are XORed against each other to produce the final value, it is also possible to remove rows against the final hash by producing a row hash in the same manner as was originally performed.

Data Processing

IDHash operates over Apache Arrow RecordBatches and can process with zero-copy over the batches.

Dependencies

~11MB
~199K SLoC