MoonVector Similarity Search Library (moon-vector)

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 zhulaoban/vector

Or manually declare it in your moon.mod dependencies:

import {
  "zhulaoban/vector"
}

---

Quick Start

1. Simple Flat Indexing and Similarity Search

import "zhulaoban/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 "zhulaoban/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 "zhulaoban/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 "zhulaoban/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 "zhulaoban/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

---

Testing

Run the full whitebox and blackbox test suite with:

moon test

Expected output:

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

---

License

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