Bit-sampling LSH in Python
LSH for Hamming distance that hashes on randomly chosen bit positions.
- File
bit_sampling_lsh.py, 61 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bit-sampling-lsh/. The authors are listed in prov/PZGBBJ.jsonl.
import random
from collections.abc import Sequence
def hamming(x: int, y: int) -> int:
"""Return the number of bit positions where x and y differ."""
return (x ^ y).bit_count()
class BitSamplingLSH:
"""LSH for the Hamming distance on d-bit integers, keyed by k sampled bits in each of L tables.
Build: O(nLk) time, O(nL) space. Query: O(Lk) time for the keys and at most 3L
distance computations of O(d / w) word operations each.
"""
def __init__(
self,
points: Sequence[int],
d: int,
k: int,
L: int,
rng: random.Random | None = None,
positions: list[list[int]] | None = None,
) -> None:
if d < 1 or k < 1 or L < 1:
raise ValueError("d, k and L must be at least 1")
rng = rng if rng is not None else random.Random()
self.points = list(points)
self.L = L
self.pos: list[list[int]] = []
self.tables: list[dict[tuple[int, ...], list[int]]] = []
for j in range(L): # @line L1
if positions is not None:
idx = list(positions[j])
else:
idx = [rng.randrange(d) for _ in range(k)] # @line L2
self.pos.append(idx)
table: dict[tuple[int, ...], list[int]] = {}
for i, x in enumerate(self.points):
table.setdefault(self.key(j, x), []).append(i) # @line L3
self.tables.append(table)
def key(self, j: int, x: int) -> tuple[int, ...]:
"""Return the bits of x at the k sampled positions of table j."""
return tuple((x >> i) & 1 for i in self.pos[j])
def query(self, q: int, c: float, r: float) -> int | None:
"""Return the index of a point within Hamming distance c*r of q, or None."""
count = 0 # @line L4
for j in range(self.L): # @line L5
for i in self.tables[j].get(self.key(j, q), []):
count += 1 # @line L6
if hamming(q, self.points[i]) <= c * r:
return i
if count >= 3 * self.L: # @line L7
return None
return None # @line L8
test_bit_sampling_lsh.py 75 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bit-sampling-lsh/. The authors are listed in prov/PZGBBJ.jsonl.
import itertools
import math
import random
from fractions import Fraction
from bit_sampling_lsh import BitSamplingLSH, hamming
def to_int(s: str) -> int:
"""Bit i of the result is character i of s."""
return sum(1 << i for i, ch in enumerate(s) if ch == "1")
P = [to_int(s) for s in ["00010111", "11100000", "11010010", "01011011", "00111100", "10110100"]]
Q = to_int("10110001")
def test_example() -> None:
idx = BitSamplingLSH(P, 8, 3, 2, positions=[[0, 2, 5], [4, 6, 7]])
assert idx.key(0, Q) == (1, 1, 0)
assert idx.tables[0][(1, 1, 0)] == [1]
assert idx.key(1, Q) not in idx.tables[1]
assert idx.query(Q, 2, 1) is None
assert idx.query(Q, 2, 2) == 1
def test_collision_probability_exact() -> None:
d = 6
for x, y in itertools.product(range(1 << d), repeat=2):
if (x * 7 + y) % 37:
continue
same = sum(((x >> i) & 1) == ((y >> i) & 1) for i in range(d))
assert Fraction(same, d) == 1 - Fraction(hamming(x, y), d)
def test_rho_at_most_one_over_c() -> None:
for d in range(2, 60):
for r in range(1, d):
for c in (1.1, 1.5, 2, 3, 4.5):
if c * r < d:
rho = math.log(1 / (1 - r / d)) / math.log(1 / (1 - c * r / d))
assert rho <= 1 / c + 1e-12
def test_answers_are_valid_against_brute_force() -> None:
rng = random.Random(31337)
for _ in range(500):
d = rng.randint(1, 20)
pts = [rng.randrange(1 << d) for _ in range(rng.randint(0, 25))]
q = rng.randrange(1 << d)
idx = BitSamplingLSH(pts, d, rng.randint(1, 4), rng.randint(1, 4), rng)
r, c = rng.randint(0, 3), 2
got = idx.query(q, c, r)
if got is not None:
assert hamming(q, pts[got]) <= c * r
if not pts or min(hamming(q, p) for p in pts) > c * r:
assert got is None
def test_success_rate() -> None:
rng = random.Random(5)
d, n, r, c = 32, 60, 2, 2
p1, p2 = 1 - r / d, 1 - c * r / d
k = math.ceil(math.log(n) / math.log(1 / p2))
L = math.ceil(n ** (math.log(1 / p1) / math.log(1 / p2)) / p1)
ok = 0
for _ in range(300):
pts = [rng.randrange(1 << d) for _ in range(n)]
q = pts[0] ^ (1 << rng.randrange(d)) ^ (1 << rng.randrange(d))
got = BitSamplingLSH(pts, d, k, L, rng).query(q, c, r)
ok += got is not None
assert ok / 300 >= 2 / 3 - 1 / math.e
What the next level needs
- the tests did not run in this build