🥮 mooncakes.io
README

#core/ann

Approximate Nearest Neighbor (ANN) search algorithms.

#Algorithms

  • Bruteforce: Exact nearest neighbor search via linear scan
  • HNSW: Hierarchical Navigable Small World graph for logarithmic search complexity
  • IVF: Inverted File Index with clustering for large-scale datasets

#Usage

// Create HNSW state
let params = @types.HNSWParams::default()
let state = HNSWState::new(params, @types.Cosine, 1024)

// Add vector (returns assigned level)
let level = state.add(0, store, dim)

// Search for k nearest neighbors
let results = state.search(query, k, store, dim)

#Key Types

  • HNSWState: HNSW graph state with configurable M and ef parameters
  • IVFState: IVF index with nlist clusters and nprobe search parameter

#
BruteforceState

source
pub struct BruteforceState {
  metric : 
Metric
}

Bruteforce ANN strategy implementation. Simple linear scan over all vectors - best for small datasets.

#
BruteforceState::new

source

Create bruteforce state

#
HNSWState

source
pub struct HNSWState {
  metric : 
Metric
  m : Int
  ef_construction : Int
  ef_search : Int
  level_mult : Double
  allow_replace_deleted : Bool
  enter_point : Int
  max_level : Int
  level_arr : Array[Int]
  tombstone : Array[Bool]
  links : Array[Array[Array[Int]]]
  rng : Rng
}

HNSW state

#
HNSWState::ensure_capacity

source
fn HNSWState::ensure_capacity(self : HNSWState, capacity : Int) -> Unit

Ensure capacity for HNSW state

#
HNSWState::new

source

Create HNSW state

#
IVFState

source
pub struct IVFState {
  metric : 
Metric
  nlist : Int
  nprobe : Int
  centroid_count : Int
  centroids : Array[Double]
  lists : Array[Array[
VectorId]]
  id_to_list : Map[
VectorId, Int]
}

IVF (Inverted File) index implementation. Uses k-means clustering for approximate nearest neighbor search.

#
IVFState::new

source

Create IVF state

#
Rng

source
type Rng

HNSW (Hierarchical Navigable Small World) graph-based ANN implementation. Provides high-performance similarity search with logarithmic complexity. XORShift random number generator

#
bf_add

source

Bruteforce add - no-op for bruteforce (no index structure)

#
bf_deserialize

source
fn bf_deserialize(_state : BruteforceState, _data : Bytes) -> Unit

Deserialize bruteforce state (no-op)

#
bf_find

source

Bruteforce find one - returns the best match

#
bf_remove

source

Bruteforce remove - no-op for bruteforce (no index structure)

Bruteforce search - linear scan over all vectors. Returns top-k results sorted by score (highest first). Query is normalized for cosine metric.

#
bf_serialize

source
fn bf_serialize(_state : BruteforceState) -> Bytes

Serialize bruteforce state (empty for bruteforce)

#
hnsw_add

source

Add a vector to HNSW

#
hnsw_compact_and_rebuild

source
fn hnsw_compact_and_rebuild(state : HNSWState, store : 
CoreStore) -> (HNSWState, Int)

Compact HNSW index by removing tombstoned entries and rebuilding Returns the number of removed entries

#
hnsw_deserialize

source
fn hnsw_deserialize(state : HNSWState, data : Bytes) -> Unit

Deserialize HNSW state from bytes

#
hnsw_find

source

Find single best match in HNSW

#
hnsw_rebuild

source

Rebuild HNSW index from scratch

#
hnsw_remove

source

Remove a vector from HNSW (mark as tombstone).

This is a soft-delete: the node's graph edges are preserved so that traversal can continue through it during search. The node is excluded from search results but still used as a relay in greedy descent.

Incremental update (replace old ID with new ID): Calling hnsw_remove(old) followed by hnsw_add(new) is supported. The new node is connected during hnsw_add even when tombstoned nodes act as bridging nodes in the existing graph. For high-throughput workloads that delete many entries before adding new ones, call hnsw_compact_and_rebuild periodically to fully evict tombstones and restore graph quality.

Search HNSW for k nearest neighbors

#
hnsw_serialize

source
fn hnsw_serialize(state : HNSWState) -> Bytes

Serialize HNSW state to bytes

#
hnsw_tombstone_stats

source
fn hnsw_tombstone_stats(state : HNSWState, store : 
CoreStore) -> (Int, Int)

Get statistics about HNSW tombstones

#
ivf_add

source

Add a vector to IVF

#
ivf_assign

source

Assign a vector to its nearest centroid WITHOUT bootstrap behavior Use this after training to reassign vectors to the trained centroids

#
ivf_deserialize

source
fn ivf_deserialize(state : IVFState, data : Bytes, dim : Int) -> Unit

Deserialize IVF state from bytes

#
ivf_find

source

IVF find one - returns the best match

#
ivf_rebuild

source

Rebuild IVF index with new parameters

#
ivf_remove

source
fn ivf_remove(state : IVFState, id : 
VectorId) -> Unit

Remove a vector from IVF

#
ivf_retrain

source
fn ivf_retrain(state : IVFState, store : 
CoreStore, iterations : Int) -> Int

Retrain IVF centroids using current vectors in store Returns the number of centroid updates

IVF search - find k nearest neighbors

#
ivf_serialize

source
fn ivf_serialize(state : IVFState, dim : Int) -> Bytes

Serialize IVF state to bytes

#
ivf_train

source
fn ivf_train(state : IVFState, store : 
CoreStore, iterations? : Int) -> Unit

Train IVF centroids using k-means++ initialization

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io