MoonVector Similarity Search Library (MoonVector)

A pure MoonBit, zero-dependency high-dimensional Vector Similarity Search and Indexing Engine (Vector Database). It is designed to support client-side and server-side retrieval (Wasm, JS, Native), making it ideal for modern LLM applications such as Retrieval-Augmented Generation (RAG), embedding similarity search, and semantic classification.

MoonVector implements multiple indexing algorithms (Flat, IVF-Flat, KD-Tree, LSH) alongside K-Means clustering, metadata filtering, and JSON serialization.

---

Features

• Zero Dependencies: Hand-crafted mathematical primitives and data structures in pure MoonBit.
• Multiple Distance Metrics: Cosine Similarity, L2 Euclidean Distance, L1 Manhattan Distance, and Dot Product.
• Advanced Spatial Indexing:
  • FlatIndex: Baseline linear exact search.
  • IvfIndex (Inverted File Index): Clustered space partitions using K-Means. Limits query scanning to the closest $nprobenprobe$ centroids, optimizing retrieval speeds for high-dimensional vectors.
  • KdTreeIndex: Spatial-partitioning binary tree for low-to-medium dimensional vectors, implementing exact nearest neighbor search with hyper-plane bounding pruning. Supports Euclidean (L2) and Manhattan (L1) metrics.
  • LshIndex (Locality Sensitive Hashing): Random projection hashing for fast approximate Cosine similarity search.
• Metadata Tag Filtering: Prunes search targets on-the-fly using key-value tag constraints.
• JSON Serialization: Built-in, zero-dependency parser for importing/exporting Document records to/from JSON.
• Index Analyzer: Retrieve structural analytics (IndexStats) such as tree depths, centroid count, and document size.
• Wasm & Native Optimized: Compiles cleanly without target-sensitive warnings.

---

Installation

Add this package to your MoonBit dependencies:

moon add ywz1314/vector

Or manually declare it in your moon.mod dependencies:

import {
  "ywz1314/vector@0.1.3",
}

Repositories

• GitHub: ywz1314/MoonVector
• GitLink: ywzywz/MoonVector
• Competition: OSC 2026 MoonBit Track 1

---

Quick Start

1. Simple Flat Indexing and Similarity Search

import "ywz1314/vector" as @vector

fn main {
  // Create a Flat index
  let index = @vector.FlatIndex::new()

  // Insert documents with 3-dimensional embeddings and tags
  index.add(@vector.Document::new("doc_1", [1.0, 2.0, 3.0], [("category", "ml")]))
  index.add(@vector.Document::new("doc_2", [4.0, 5.0, 6.0], [("category", "security")]))

  // Search Top 2 nearest neighbors using L2 Euclidean Distance
  let query = [1.2, 2.2, 3.2]
  let results = index.search(query, 2, @vector.Euclidean, [])
  
  for i = 0; i < results.length(); i = i + 1 {
    println("Rank " + (i + 1).to_string() + ": " + results[i].id + ", Score: " + results[i].score.to_string())
  }
}

2. High-Dimensional IVF-Flat Cluster Searching

import "ywz1314/vector" as @vector

fn main {
  // IVF Index with K=2 centroids evaluated under Cosine Metric
  let index = @vector.IvfIndex::new(2, @vector.Cosine)

  let docs = [
    @vector.Document::new("doc_1", [1.0, 2.0, 3.0], [("category", "ml")]),
    @vector.Document::new("doc_2", [1.5, 2.5, 3.5], [("category", "ml")]),
    @vector.Document::new("doc_3", [5.0, 5.0, 5.0], [("category", "security")]),
  ]

  // Build cluster index using K-Means
  index.build(docs)

  // Search the closest 1 cluster centroid (nprobe=1)
  let query = [1.1, 2.1, 3.1]
  let results = index.search(query, 2, 1, [])
}

3. Spatial Partitioning with KD-Trees

import "ywz1314/vector" as @vector

fn main {
  let index = @vector.KdTreeIndex::new(@vector.Euclidean)

  let docs = [
    @vector.Document::new("doc_1", [1.0, 2.0], []),
    @vector.Document::new("doc_2", [3.0, 4.0], []),
  ]

  index.build(docs)
  
  // Search nearest neighbor
  let query = [1.1, 2.1]
  let results = index.search(query, 1, [])
}

4. Approximate Cosine Search using LSH

import "ywz1314/vector" as @vector

fn main {
  // Set up LSH index with 4 random projection planes for 3D vectors
  let index = @vector.LshIndex::new(4, 3)

  index.add(@vector.Document::new("doc_1", [1.0, 2.0, 3.0], []))
  index.add(@vector.Document::new("doc_2", [-1.0, -2.0, -3.0], []))

  // Retrieve candidate neighbors sharing the same projection hash
  let query = [1.1, 2.1, 3.1]
  let results = index.search(query, 1, [])
}

5. Document JSON Serialization

import "ywz1314/vector" as @vector

fn main {
  let doc = @vector.Document::new("doc_1", [1.25, -2.5], [("tag", "a")])
  let json = doc.to_json()
  println("JSON: " + json)

  // Deserialization
  let parsed = @vector.Document::from_json(json)
  println("Parsed Document ID: " + parsed.id)
}

---

API Reference

1. Distance Metrics

• cosine_similarity(v1: Array[Double], v2: Array[Double]) -> Double raise VectorError
• euclidean_distance(v1: Array[Double], v2: Array[Double]) -> Double raise VectorError
• manhattan_distance(v1: Array[Double], v2: Array[Double]) -> Double raise VectorError
• dot_product(v1: Array[Double], v2: Array[Double]) -> Double raise VectorError

2. Unsupervised Clustering

• kmeans(vectors: Array[Array[Double]], k: Int, max_iters: Int) -> Array[Array[Double]] raise VectorError

3. Indexing Classes

• FlatIndex::new() -> FlatIndex

  • add(self: FlatIndex, doc: Document) -> Unit
  • search(self: FlatIndex, query: Array[Double], top_k: Int, metric: DistanceMetric, filters: Array[(String, String)]) -> Array[SearchResult] raise VectorError
  • stats(self: FlatIndex) -> IndexStats

• IvfIndex::new(k: Int, metric: DistanceMetric) -> IvfIndex

  • build(self: IvfIndex, docs: Array[Document]) -> Unit raise VectorError
  • search(self: IvfIndex, query: Array[Double], top_k: Int, nprobe: Int, filters: Array[(String, String)]) -> Array[SearchResult] raise VectorError
  • stats(self: IvfIndex) -> IndexStats

• KdTreeIndex::new(metric: DistanceMetric) -> KdTreeIndex

  • build(self: KdTreeIndex, docs: Array[Document]) -> Unit
  • search(self: KdTreeIndex, query: Array[Double], top_k: Int, filters: Array[(String, String)]) -> Array[SearchResult] raise VectorError
  • stats(self: KdTreeIndex) -> IndexStats

• LshIndex::new(num_planes: Int, dim: Int) -> LshIndex

  • add(self: LshIndex, doc: Document) -> Unit raise VectorError
  • search(self: LshIndex, query: Array[Double], top_k: Int, filters: Array[(String, String)]) -> Array[SearchResult] raise VectorError

Data-quality and application helpers

• validate_documents(docs) rejects empty corpora, blank/duplicate ids, empty vectors, and mixed dimensions before indexing.
• normalize_l2 and normalize_documents provide explicit embedding normalization without mutating the input arrays.
• VectorCollection supports validated upsert, remove, replace_all, rebuild, exact search, and batch search for in-memory applications.
• search_batch, recall_at_k, mean_recall, evaluate_ivf, and evaluate_lsh make approximate-index evaluation reproducible.
• paginate_results, merge_results, diversify_results, inspect_corpus, and summarize_workload cover common service-layer and monitoring needs.

Complete application workflows

The repository also includes reusable application-level paths rather than only isolated algorithms:

• KnowledgeBase manages validated upserts, deletes, revisions, exact search, approximate index fallback, batch requests, health reports, and tenant-safe metadata expressions.
• MetadataFilter and FilterExpression support equality, inequality, prefix, substring, membership, AND, OR, and NOT policies.
• hybrid_search combines embedding similarity with text metadata overlap; compose_retrieval_context produces bounded RAG context with source ids and citations.
• run_rag_scenario, run_catalog_scenario, and run_batch_scenario are deterministic application fixtures covering multi-tenant retrieval, filtered recommendations, and batch workload telemetry.
• Ranking quality helpers include precision@k, recall curves, MAP, NDCG, and coverage so approximate retrieval can be evaluated against Flat.

---

Testing

Run the full whitebox and blackbox test suite with:

moon test

The current local suite contains 21 tests covering metrics, clustering, all index types, JSON round-trips, filtering, malformed input, collection lifecycle, batch search, benchmark recall, multi-tenant RAG, catalog recommendation, and application-level retrieval policies. Expected output:

Total tests: 21, passed: 21, failed: 0.

For the strict CI-equivalent check, run:

moon fmt --check
moon check --deny-warn
moon test --deny-warn
moon build
moon info
git diff --exit-code

Reproducible benchmark

The repository includes a deterministic 48-document, 8-dimensional corpus and six query vectors in benchmark.mbt. It is intentionally synthetic but is structured into four semantic topic bands so that cluster locality, metadata filtering, and approximate recall can be checked without downloading private or copyrighted data.

The public helpers are benchmark_corpus, benchmark_queries, evaluate_ivf, and evaluate_lsh. The test suite compares IVF and LSH against the exact FlatIndex baseline using recall@k. This gives a repeatable quality signal rather than a claim based on a single hand-picked example.

Boundary and data-quality behavior

• Empty vectors are rejected by metric, normalization, and corpus-validation APIs.
• Mismatched dimensions raise VectorError::DimensionMismatch.
• Duplicate or blank document ids are rejected by validate_documents and reported by inspect_corpus.
• top_k <= 0 returns no results; requesting more results than available is safely truncated.
• Empty filters match every document. Multiple filters use AND semantics.
• Document::from_json rejects missing required fields; this lightweight serializer expects string values without embedded unescaped quotes.
• IVF nprobe is bounded to the number of clusters. LSH is approximate and must be evaluated against Flat when a recall target matters.

Application APIs

VectorCollection provides validated upsert/remove/replace/rebuild lifecycle operations for applications receiving documents over time. QueryPlan and recommend_strategy make the choice between exact Flat, IVF, KD-Tree, and LSH explicit. ResultPage, merge_results, diversify_results, and SearchTelemetry support common service-layer concerns without coupling the library to a network framework.

Original work and open-source compliance

MoonVector is an original MoonBit implementation. It is not a line-by-line port and has no vendored third-party source, generated source, private code, or external benchmark dataset. The repository depends only on MoonBit’s standard library and is released under Apache-2.0. The deterministic benchmark fixture is authored in benchmark.mbt; it contains no personal or proprietary data.

See docs/ARCHITECTURE.md for package boundaries, algorithm trade-offs, correctness guarantees, and known limitations.

OSC 2026 Submission Notes

• Repository layout: package root, CLI entrypoint in cmd/main, whitebox and blackbox tests, docs, and package metadata are all present.
• License: Apache-2.0.
• Validation: CI now checks moon check, moon fmt --deny-warn equivalent formatting enforcement, moon info --deny-warn interface generation, and moon test.
• Toolchain target: MoonBit toolchain 0.10.3-compatible workflow.
• Source scale: the project includes multiple MoonBit source modules, tests, and documentation artifacts rather than a minimal stub.

---

License

This project is licensed under the Apache 2.0 License - see the LICENSE file for details.