huggingface / huggingface/datatrove
Minhash mersenne hashing overflow issues.
- 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