🥮 mooncakes.io

    #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 issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io