Bichromatic operations and metric joins

by: Eric S. Téllez

Bichromatic (cross-dataset) operations find closest pairs between two different collections under a shared metric. This is distinct from standard (monochromatic) nearest-neighbor search, which looks inside a single dataset.

SimilaritySearch.jl provides three bichromatic functions in its Bichromatic submodule (re-exported at the top level):

Function	What it computes
`bichromatic_closestpair`	The single globally closest pair `(a, b)` across `A × B`
`bichromatic_kclosestpairs`	The `k` closest pairs across `A × B`
`bichromatic_metricjoin`	Adaptive metric join: each `a ∈ A` gets all `b ∈ B` within a locally adaptive radius

using SimilaritySearch, SimSearchManifoldLearning
using Plots, StatsBase, LinearAlgebra, Markdown, Random, Printf

2D visual example

We start with a toy 2D dataset to make the operations visually concrete.

Random.seed!(1)

# A: 40 blue "facility" points — scattered across the plane
A_mat = 8f0 .* rand(Float32, 2, 40) .- 4f0
A_db  = MatrixDatabase(A_mat)

# B: 80 red "client" points — clustered in two dense regions
B_mat = hcat(randn(Float32, 2, 50) .* 0.6f0 .+ Float32[-2, 1],
             randn(Float32, 2, 30) .* 0.4f0 .+ Float32[2, -2])
B_db  = MatrixDatabase(B_mat)

dist  = Dist.L2()
idxA  = ExhaustiveSearch(dist, A_db)
ctx   = GenericContext()

# Baseline scatter
scatter(A_mat[1, :], A_mat[2, :]; ms=8, msw=1, mc=:royalblue, ma=0.8, label="A (facilities)")
scatter!(B_mat[1, :], B_mat[2, :]; ms=5, mc=:crimson, ma=0.6, label="B (clients)")
plot!(; legend=:topright, title="A vs B", xlabel="x", ylabel="y", fmt=:png, size=(600, 520))

`bichromatic_closestpair`

Finds the single pair (aᵢ, bⱼ) with the smallest distance across all of A × B.

i, j, d = bichromatic_closestpair(idxA, ctx, B_db)
println("Closest pair: A[$i] and B[$j], distance = $(@sprintf "%.4f" d)")

# Draw it
scatter(A_mat[1, :], A_mat[2, :]; ms=7, mc=:royalblue, ma=0.6, label="A")
scatter!(B_mat[1, :], B_mat[2, :]; ms=5, mc=:crimson, ma=0.5, label="B")
scatter!([A_mat[1,i]], [A_mat[2,i]]; ms=14, mc=:royalblue, msw=2, label="closest A[$i]")
scatter!([B_mat[1,j]], [B_mat[2,j]]; ms=11, mc=:crimson, msw=2, label="closest B[$j]")
plot!([A_mat[1,i], B_mat[1,j]], [A_mat[2,i], B_mat[2,j]]; lw=2, lc=:black, label="d=$(round(d,digits=3))")
plot!(; legend=:topright, title="Closest pair", fmt=:png, size=(600, 520))

Closest pair: A[26] and B[41], distance = 0.0440

`bichromatic_kclosestpairs`

Retrieves the k globally closest pairs across A × B.

k = 10
pairs = bichromatic_kclosestpairs(idxA, ctx, B_db; k)

scatter(A_mat[1, :], A_mat[2, :]; ms=6, mc=:royalblue, ma=0.5, label="A")
scatter!(B_mat[1, :], B_mat[2, :]; ms=4, mc=:crimson, ma=0.5, label="B")
for (ai, bi, di) in pairs
    plot!([A_mat[1,ai], B_mat[1,bi]], [A_mat[2,ai], B_mat[2,bi]];
          lw=1.5, lc=:black, la=0.5, label="")
end
plot!(; legend=:topright, title="Top-$k closest pairs", fmt=:png, size=(600, 520))

`bichromatic_metricjoin`

Standard joins use a fixed global radius r. In non-uniform datasets this produces too many matches in dense regions and none in sparse ones. bichromatic_metricjoin adapts the cutoff radius per query point from the local density of its k candidate neighbours.

# Use approximate bichromatic search (SearchGraph) for the join
idxA_approx, ctxA_approx = let
    G = SearchGraph(dist, A_db)
    gctx = SearchGraphContext(hyperparameters_callback=OptimizeParameters(MinRecall(0.95)))
    index!(G, gctx)
    G, gctx
end

join_pairs = bichromatic_metricjoin(idxA_approx, ctxA_approx, B_db; k=8)
println("Adaptive join produced $(length(join_pairs)) matched pairs")

scatter(A_mat[1, :], A_mat[2, :]; ms=7, mc=:royalblue, ma=0.7, label="A")
scatter!(B_mat[1, :], B_mat[2, :]; ms=5, mc=:crimson, ma=0.5, label="B")
for (ai, bi, di) in join_pairs
    plot!([A_mat[1,ai], B_mat[1,bi]], [A_mat[2,ai], B_mat[2,bi]];
          lw=0.8, lc=:gray, la=0.4, label="")
end
plot!(; legend=:topright, title="Adaptive metric join", fmt=:png, size=(600, 520))

Exact vs approximate bichromatic search

The convenience form bichromatic_closestpair(dist, A, B; recall=r) automatically builds an approximate SearchGraph when recall < 1.0:

# Exact
i_ex, j_ex, d_ex = bichromatic_closestpair(dist, A_db, B_db)

# Approximate (builds SearchGraph internally, targets 90% recall)
i_ap, j_ap, d_ap = bichromatic_closestpair(dist, A_db, B_db; recall=0.9)

println("Exact  : A[$i_ex] — B[$j_ex], d = $(@sprintf "%.4f" d_ex)")
println("Approx : A[$i_ap] — B[$j_ap], d = $(@sprintf "%.4f" d_ap)")
println("Same pair: $(i_ex == i_ap && j_ex == j_ap)")

LOG add! sp=1 ep=40 BeamSearch(bsize=4, Δ=1.0, maxvisits=1000000) n.size-quantiles=[0.0, 2.0, 2.0, 3.0, 4.0] mem=433MB max-rss=1338MB 2026-08-27T14:30:55.043
Exact  : A[26] — B[41], d = 0.0440
Approx : A[26] — B[41], d = 0.0440
Same pair: true

Word embedding example: cross-language closest pairs

Using the Wikipedia LSI word embeddings generated for this demo site, we can find the English words closest to a set of Spanish words — a zero-shot cross-lingual alignment experiment.

Note: requires demos/data/wiki-es-lsi.txt and demos/data/wiki-en-lsi.txt generated by generate_wiki_embeddings.jl.

# Helper to load GloVe-format embeddings
function load_glove(path; n=50_000, dtype=Float16)
    lines = readlines(path)
    n = min(n, length(lines))
    dim = length(split(lines[1])) - 1
    M   = Matrix{dtype}(undef, dim, n)
    voc = Vector{String}(undef, n)
    for i in 1:n
        parts   = split(lines[i])
        voc[i]  = parts[1]
        for (j, v) in enumerate(@view parts[2:end])
            M[j, i] = parse(Float32, v)
        end
    end
    M, voc
end

emb_es, voc_es = load_glove(joinpath(@__DIR__, "data", "wiki-es-lsi.txt"); n=80_000)
emb_en, voc_en = load_glove(joinpath(@__DIR__, "data", "wiki-en-lsi.txt"); n=80_000)
v2id_es = Dict(w => i for (i, w) in enumerate(voc_es))
v2id_en = Dict(w => i for (i, w) in enumerate(voc_en))

# Pick a set of Spanish words and find their closest English counterparts
# (Both embedding spaces are independent LSI spaces — alignment is approximate)
es_words = ["física", "historia", "computación", "música", "filosofía",
            "matemáticas", "biología", "química", "literatura", "medicina"]

es_ids   = [v2id_es[w] for w in es_words if haskey(v2id_es, w)]
A_words  = MatrixDatabase(Float32.(emb_es[:, es_ids]))

# Build English index
B_words  = MatrixDatabase(Float32.(emb_en))
dist_cos = Dist.NormCosine()
idx_en   = SearchGraph(dist_cos, B_words)
ctx_en   = SearchGraphContext(hyperparameters_callback=OptimizeParameters(MinRecall(0.95)))
index!(idx_en, ctx_en)

# For each Spanish word, find the 5 closest English words
res = knnqueue(ctx_en, 5)
L = [
    "## Spanish → English cross-lingual nearest neighbours (LSI-based)",
    "| Spanish | English neighbours |",
    "|---------|-------------------|"
]
for (es_w, eid) in zip(es_words, es_ids)
    haskey(v2id_es, es_w) || continue
    reuse!(res, 5)
    search(idx_en, ctx_en, Float32.(emb_es[:, eid]), res)
    en_nn = join(["$(voc_en[p.id]) ($(@sprintf "%.3f" p.dist))" for p in IdDistView(res)], ", ")
    push!(L, "| **$es_w** | $en_nn |")
end
Markdown.parse(join(L, "\n")) |> display

Spanish → English cross-lingual nearest neighbours (LSI-based)

Spanish	English neighbours
física	Andronikashvili (0.809), anglicized (0.815), Racha (0.818), Glynn (0.821), Saoirse (0.822)
historia	Evald (0.794), Estonia (0.795), Lembit (0.797), Toivo (0.804), Kielland (0.805)
computación	coped (0.767), west (0.780), east (0.786), south (0.789), embattled (0.794)
música	Pehrsson (0.717), Houten (0.736), Guthrum (0.736), Anglian (0.739), Timorese (0.744)
filosofía	Dorough (0.775), Darien (0.785), Heckart (0.787), Kristen (0.788), Staton (0.789)
matemáticas	west (0.751), east (0.757), north (0.758), approximately (0.758), south (0.763)
biología	Episode (0.750), Shannen (0.756), Felicity (0.757), Edie (0.761), Roseanne (0.773)
química	approximately (0.763), lies (0.769), Wrocław (0.773), west (0.774), east (0.780)
literatura	countries (0.774), across (0.785), Transcaucasia (0.793), bowstring (0.805), Truss (0.807)
medicina	Makin (0.780), Amazing (0.796), Episode (0.797), Loser (0.799), Supergirl (0.800)

Environment and dependencies

Julia Version 1.12.7
Commit 6d172b025e4 (2026-08-15 08:05 UTC)
Build Info:
  Official https://julialang.org release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 64 × Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz
  WORD_SIZE: 64
  LLVM: libLLVM-18.1.7 (ORCJIT, cascadelake)
  GC: Built with stock GC
Threads: 64 default, 1 interactive, 64 GC (on 64 virtual cores)
Environment:
  JULIA_PROJECT = @.
  JULIA_NUM_THREADS = auto
  JULIA_LOAD_PATH = @:@stdlib
Status `~/Research/SimilaritySearchDemos/Project.toml`
  [aaaa29a8] Clustering v0.15.8
  [944b1d66] CodecZlib v0.7.9
  [a93c6f00] DataFrames v1.8.2
  [f67ccb44] HDF5 v0.17.3
  [0f8b85d8] JSON3 v1.14.3
  [23fbe1c1] Latexify v0.16.12
  [eb30cadb] MLDatasets v0.7.21
  [06eb3307] ManifoldLearning v0.9.0
⌅ [ca7969ec] PlotlyLight v0.11.1
  [91a5bcdd] Plots v1.41.7
  [27ebfcd6] Primes v0.5.7
  [92933f4c] ProgressMeter v1.11.0
  [ca7ab67e] SimSearchManifoldLearning v0.4.0 `../SimSearchManifoldLearning.jl`
  [053f045d] SimilaritySearch v1.2.0 `../SimilaritySearch.jl`
⌅ [2913bbd2] StatsBase v0.33.21
  [f3b207a7] StatsPlots v0.15.8
  [7f6f6c8a] TextSearch v1.1.1 `../TextSearch.jl`
Info Packages marked with ⌅ have new versions available but compatibility constraints restrict them from upgrading. To see why use `status --outdated`