build a reduced RAW/ANON candidate table by min-hash LSH blocking

A drop-in replacement for [join_raw_anon_data()] for a large set-valued column. Instead of the full cross join it keeps only the pairs that collide in at least one min-hash band, which is the standard way to make set matching tractable: the probability that a pair survives is `1 - (1 - J^r)^b` with `r = n_hash / bands` rows per band, an S-curve that is near 1 for similar pairs and near 0 for dissimilar ones.

Usage

lsh_candidates(
  raw,
  anon,
  target,
  row_number = "ROW_NUMBER",
  split = ":",
  n_hash = 128L,
  bands = 32L,
  seed = 0L,
  multiset = FALSE,
  raw_header = "RAW_",
  anon_header = "ANON_"
)

Arguments

raw, anon

data frames, as for [join_raw_anon_data()]

target

name of the set-valued column, present in both, **before** RAW_/ANON_ prefixing

row_number

name of the row-number column (default "ROW_NUMBER")

split

literal separator (default ":")

n_hash

number of min-hash components (default 128)

bands

number of LSH bands; must divide `n_hash` (default 32, i.e. 4 rows per band, which keeps roughly 90 J = 0.2)

seed

integer seed for the hash family (default 0L)

multiset

passed to the token splitting; see [score_jaccard()]

raw_header, anon_header

column prefixes, as for [join_raw_anon_data()]

Value

a data frame in raw_anon form holding a *subset* of the pairs [join_raw_anon_data()] would produce, carrying a `blocking` attribute (a [print()]able "reid_blocking" record; see [block_candidates()]).

Details

**THIS UNDER-REPORTS RISK, BY CONSTRUCTION.** Blocking is a *lossy* filter: if the true counterpart of an ANON record is dropped, that record can never be reidentified and the reported success rate falls. That is precisely the failure direction a safety-checking tool must not take quietly (docs/lessons-learned.md section 2), so this function is opt-in, never used by any other function in the package, and records what it discarded in the `blocking` attribute of its result – including the **recall**, the fraction of true pairs it kept, which it measures exactly against the shared `row_number` (Issue #36). It warns when that recall is below 1. Use it to make a large assessment feasible, then confirm the conclusion on the full join for a subsample – and read the resulting rate as a lower bound.

See also

[block_candidates()] for deterministic blocking on a key column.

Examples

raw <- data.frame(
  ROW_NUMBER = 1:4,
  ITEMS = c("a:b:c", "d:e:f", "g:h:i", "j:k:l"),
  stringsAsFactors = FALSE
)
blocked <- lsh_candidates(raw, raw, "ITEMS", n_hash = 32, bands = 8)
attr(blocked, "blocking")
#> blocking (minhash-lsh): 4 of 16 pair(s) kept (25% of the full 4 x 4 join)
#>   recall       : 1.0000  (4 of 4 true pair(s) retained)
#>   ANON records with no candidate at all: 0
#>   settings     : n_hash = 32, bands = 8