2D Synthetic Dataset: Exploring SearchGraph

by: Eric S. Téllez

This demonstration shows SearchGraph on a 2D synthetic dataset. Being 2D, we can visualize the kNN neighborhoods directly, giving intuition about how the index behaves in regions of different density. We also demonstrate closestpair and neardup, two useful dataset-level operations.

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

n = 100_000
M = randn(Float16, 2, n)
db = MatrixDatabase(M)
dist = Dist.SqL2()   # evaluates in Float32 internally
size(M)

Index construction

1G = SearchGraph(dist, db)
ctx = SearchGraphContext(hyperparameters_callback=OptimizeParameters(MinRecall(0.99)))
2index!(G, ctx)
3optimize_index!(G, ctx, MinRecall(0.9))

1: Positional constructor: SearchGraph(dist, db). The context controls caches and the hyperparameter-tuning callback.
2: Indexes all items in db.
3: Rebalances beam-search hyperparameters to target 90 % recall.

Batch search

We define a small set of queries at various density regions and search their 30 nearest neighbors.

Q = VectorDatabase([Float32[-2,-2], Float32[2,-2], Float32[-2,0],
                    Float32[0, 2], Float32[0,0],  Float32[-3,3],
                    Float32[4, 4], Float32[1,0.5]])
ids, dists = searchbatch(G, ctx, Q, 30)   # returns (ids, dists) — each (30 × |Q|)

Please note how queries in low and high dense regions get very different neighborhood radii.

scatter(view(M, 1, :), view(M, 2, :); fmt=:png, c=:cyan, ma=0.3, ms=1, msw=0, label="data")
scatter!(getindex.(Q, 1), getindex.(Q, 2); c=:red, ma=0.9, ms=6, msw=0, label="queries")

for i in axes(ids, 2)
    col_ids = ids[:, i]
    X = M[:, col_ids]
    scatter!(view(X, 1, :), view(X, 2, :); c=:blue, ma=0.5, ms=2, msw=0, label="")
end

plot!(legend=:topright)

Since points are distributed across regions with disparate density, the 30-NN radius varies widely:

query	x	y	radius (30-NN)
1	-2.0	-2.0	0.1826
2	2.0	-2.0	0.1938
3	-2.0	0.0	0.1046
4	0.0	2.0	0.0768
5	0.0	0.0	0.0320
6	-3.0	3.0	1.0361
7	4.0	4.0	2.4688
8	1.0	0.5	0.0402

Closest pair

closestpair finds the globally closest pair of distinct items in the dataset in sub-quadratic time using the indexed graph.

i, j, d = closestpair(G, ctx)
println("Closest pair: items $i and $j, squared-L2 distance = ", d)
println("  item $i = ", G[i])
println("  item $j = ", G[j])

Closest pair: items 55698 and 1073, squared-L2 distance = 0.0
  item 55698 = Float16[0.576, 1.294]
  item 1073 = Float16[0.576, 1.294]

Near-duplicate detection

neardup partitions the dataset into groups of near-duplicates: each group has a representative (center) and all items within ε of it. We use a radius derived from the 1-NN distance distribution.

# estimate a reasonable ε from a sample of 1-NN distances
sample_ids, sample_dists = searchbatch(G, ctx, SubDatabase(db, rand(1:n, 500)), 2)
ε = quantile(vec(sample_dists[2, :]), 0.01)   # very tight: ~1% of pairs

sel = neardup(dist, db, ε)
println("Groups (centers): ", length(sel.centers))
println("ε = ", ε)

# visualize: color by group assignment
ncolors = length(sel.centers)
group_colors = [HSL(360 * i / ncolors, 0.7, 0.5) for i in 1:ncolors]

pt_colors = [group_colors[min(a, ncolors)] for a in sel.assign]
scatter(view(M, 1, :), view(M, 2, :); color=pt_colors, fmt=:png,
        ms=1.5, msw=0, ma=0.5, label="", title="Near-duplicate groups (ε=$(round(ε, digits=4)))",
        xticks=nothing, yticks=nothing)

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`