#moonhnsw

#Features

• HNSW graph index with incremental add, deterministic search(top-k), approximate search_radius, and binary save / load.
• Tombstone deletion: delete(id) hides vectors from all searches while keeping the graph connected; compact() rebuilds a tombstone-free index and hands you an old-id → new-id mapping.
• Introspection: stats() reports per-layer node counts, average degree and a rough memory estimate; get_vector(id) and contains(id) expose the stored data; export_dot(layer) renders any layer as Graphviz DOT; Neighbor and HnswStats derive Eq / Debug / ToJson, so results drop straight into assertions, logs and JSON pipelines.
• External labels: add_labeled(vector, label) tags each vector with a UInt64 key (a document or chunk id); labels persist through save / load and compact.
• Composable: absorb() merges another index (keeping labels), copy() deep-clones, and save_bytes() / load_bytes() wrap the payload as Bytes for binary pipelines.
• SQ8 scalar quantization: storage=SQ8 learns per-dimension bounds from the first 256 vectors and then stores one byte per dimension. The vector store is about 4x smaller; retrieval quality depends on the data. Stored vectors added after freezing clamp to the learned range; queries keep their original values when distances are calculated.
• MMR diverse search: search_mmr(query, k, lambda) re-ranks a wide candidate pool for relevance-vs-redundancy, the de-duplication step RAG contexts need.
• Empirical ef calibration: calibrate_ef measures recall@k against an exact scan of representative queries and recommends the smallest tested beam width meeting your target.
• Adaptive filtered retrieval: search_filtered_adaptive widens an unfiltered candidate pool until it contains k filter matches or reaches a configured cap; it reports rounds and distance work.
• Guaranteed exact retrieval: search_exact and search_radius_exact scan the live stored vectors with stable distance/id ties. Use them for small collections, strict completeness, and a trustworthy recall baseline; SQ8 results are exact over its quantized store.
• Integrity-checked persistence: payloads carry a CRC-32 trailer, so flipped bits and silent truncation are rejected on load instead of surfacing as degraded searches.
• Three metrics with a smaller-is-closer convention: L2 (squared Euclidean), InnerProduct (negated dot product), Cosine (vectors normalized once on insertion).
• Tunable m, ef_construction, and per-query ef — the standard recall/speed trade-off knobs.
• Allocation-aware storage: Float32 vectors live in one flattened FixedArray[Float], while frozen SQ8 vectors live in a byte array; traversal marks visited nodes with generation stamps instead of hash sets. Common Float32 distances accumulate in f32, with a Double fallback for extreme finite values.
• Self-contained serialization: one save() call produces a byte buffer you can write anywhere; load() restores an index that answers searches identically and keeps accepting insertions.
• Typed errors (HnswError) with readable messages.
• Finite-input checks: NaN and infinite vectors/queries are rejected before graph mutation; loading also validates stored values after checksum verification.

#Quick start

moon add yiwnagmolu/moonhnsw@0.12.4

import {
  "yiwnagmolu/moonhnsw" @moonhnsw,
}

pkgtype(kind: "executable")

///|
fn main raise {
  let index = @moonhnsw.Hnsw::new(2, @moonhnsw.Distance::L2)
  let vector : FixedArray[Float] = FixedArray::from_array([1.0, 2.0])
  let _ = index.add(vector)
  let hits = index.search(vector, 1, ef=64)
  println("nearest id=\{hits[0].id} distance=\{hits[0].distance}")
}

#API

• L2 — squared Euclidean distance.
• InnerProduct — negated inner product.
• Cosine — negated inner product after L2 normalization; the index normalizes stored vectors once and each query on entry, and distance(Cosine, a, b) normalizes both arguments. Zero vectors are kept as-is.

#Choosing search width

///|
let calibration = index.calibrate_ef(sample_queries, 10, 0.95, [16, 32, 64, 128])

///|
let hits = index.search(query, 10, ef=calibration.selected_ef)

///|
let result = index.search_filtered_adaptive(
  query,
  10,
  ef_start=32,
  ef_max=512,
  filter=fn(id) { id % 2 == 0 },
)

///|
let hits = result.neighbors

#Parameters

#Benchmarks

moon run --target wasm-gc examples/benchmark
moon run --target wasm-gc examples/benchmark-large

#When to use / production readiness

#Implementation notes

• The graph is a hierarchy of proximity subgraphs. Every node lives on layer 0; each node's top layer is drawn from a geometric distribution, so upper layers hold roughly 1/m of the nodes below them:

layer 2   e──────────────              (entry, a handful of nodes)
layer 1   a───b─────g───────           (greedy descent)
layer 0   a─b─c─d─e─f─g─h─i─...        (all nodes, beam search)

• New nodes keep m links per layer; overflowing neighbor lists of existing nodes are re-selected with the same heuristic.
• Beam search uses a binary heap for candidates (min) and results (max), and an O(1) generation-stamp array for the visited set.
• Float32 storage accumulates distances in f32; frozen SQ8 decodes stored byte values and scores them against the original query using Double, including queries outside learned bounds.
• Storage layout: Float32 vectors use one flattened FixedArray[Float] of count * dim values, doubled geometrically; frozen SQ8 uses one byte per component. Graph edges use Array[Array[Array[Int]]].
• Serialization is little-endian with a magic header and version byte; every length and id is validated on load.

#Limitations & roadmap

• Deletion is tombstone-based: deleted nodes keep occupying memory (ids and graph slots are never reclaimed) and in-place vector update is not supported.
• Radius search shares the graph-approximation of top-k search: a neighbor inside the radius can be missed when it is only reachable through farther nodes.
• Single-threaded; indexes are not to be shared across concurrent writers.
• Ids are internal insertion order; map them to your own keys in application code.

#Development

moon test                 # run the test suite
moon test --target wasm-gc
moon check --target wasm-gc --deny-warn
moon info && moon fmt     # refresh generated interfaces, format
moon run --target wasm-gc examples/benchmark

On Windows the native backend additionally requires MSVC Build Tools (cl.exe or clang-cl); wasm-gc and js targets work out of the box.

#References

• Malkov, Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. TPAMI 2018 (arXiv:1603.09320).
• hnswlib and usearch for parameter conventions.

#License