huggingface / huggingface/datatrove

Minhash mersenne hashing overflow issues.

Open
#198 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
3.3k
Forks
302
Avg merge
2h 18m
Merged PRs (30d)
2

Description

Seeing as this repo inherits lots of code from https://github.com/ekzhu/datasketch, it should be noted that the implementation of mersenne prime hashing used in both repos causes overflows, and potentially more hash collisions than intended:

```python
SEED = 0x5eed
_mersenne_prime_py = (1 << 61) - 1
_mersenne_prime = np.uint64(_mersenne_prime_py)
num_hashes=2
N=3

gen = np.random.RandomState(SEED)
a, b = (
gen.randint(1, _mersenne_prime, dtype=np.uint64, size=(1, num_hashes)),
gen.randint(0, _mersenne_prime, dtype=np.uint64, size=(1, num_hashes)),
)

shingles = gen.randint(0, (1<<32), dtype=np.uint64, size=(N, 1))

def h1(a, b, shingles):
# Numpy uint64, overflows
return (shingles * a + b) % _mersenne_prime

def h2(a, b, shingles):
# Native python, no overflow.
rows = []
for sj in shingles[:, 0].tolist():
rows.append([
(sj * ai + bi) % _mersenne_prime_py
for ai, bi in zip(a[0].tolist(), b[0].tolist())
])

return np.array(rows)

print(h1(a, b, shingles) == h2(a, b, shingles))
# False False False ...
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by locating the MinHash mersenne-prime hashing implementation and reproduce the provided NumPy and native-Python comparison. Check how uint64 multiplication and modulo are handled; done means the implementation avoids the reported overflow discrepancy and the two calculations agree for the example.

Written by the indexing model from the issue text.

Assessment

Tech stack
numpy, python
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.