comet

KO | EN

gitlite — search

#javascript #hacktoberfest #ai #go #golang #machine-learning #rust #linux #docker #nodejs #macos #cli #pytorch #open-source

(★ 131)

A Vector Store written in Go - Supports hybrid retrieval over BM25, Flat, HNSW, IVF, PQ and IVFPQ Index with Quantization, Metadata Filtering, Reranking, Reciprocal Rank Fusion, Soft Deletes, Index Rebuilds and much much more

File Explorer

Download Latest Version (.zip)

- - static.yml
- API.md
- EXAMPLE.md
- INDEX.md
- PERSISTENCE.md
- cover.png
- index.html
.gitattributes
.gitignore
aggregation.go
aggregation_test.go
bm25_index.go
bm25_index_document_filter_test.go
bm25_index_search.go
bm25_index_search_test.go
bm25_index_test.go
clustering.go
clustering_test.go
distance.go
distance_test.go
doc.go
document_filter.go
document_filter_test.go
flat_index.go
flat_index_document_filter_test.go
flat_index_search.go
flat_index_search_test.go
flat_index_test.go
fusion.go
fusion_test.go
go.mod
go.sum
hnsw_index.go
hnsw_index_document_filter_test.go
hnsw_index_search.go
hnsw_index_search_test.go
hnsw_index_test.go
hybrid_search_index.go
hybrid_search_index_test.go
index.go
index_search.go
ivf_index.go
ivf_index_document_filter_test.go
ivf_index_search.go
ivf_index_search_test.go
ivf_index_test.go
ivfpq_index.go
ivfpq_index_document_filter_test.go
ivfpq_index_search.go
ivfpq_index_search_test.go
ivfpq_index_test.go
LICENSE
limiter.go
limiter_test.go
Makefile
metadata_index.go
metadata_index_search.go
metadata_index_search_test.go
metadata_index_test.go
node.go
node_test.go
pq_index.go
pq_index_document_filter_test.go
pq_index_search.go
pq_index_search_test.go
pq_index_test.go
quantizer.go
quantizer_test.go
README.md
reranker_test.go
storage.go
storage_compaction.go
storage_compaction_test.go
storage_memtable.go
storage_memtable_test.go
storage_merge.go
storage_merge_test.go
storage_provider.go
storage_provider_test.go
storage_segment.go
storage_segment_test.go
storage_test.go

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Comet

![Cover](https://raw.githubusercontent.com/0xnyn/comet/main/media/cover.png)

A high-performance hybrid vector store written in Go. Comet brings together multiple indexing strategies and search modalities into a unified, hackable package. Hybrid retrieval with reciprocal rank fusion, autocut, pre-filtering, semantic search, full-text search, and multi-KNN searches, and multi-query operations — all in pure Go.

Understand search internals from the inside out. Built for hackers, not hyperscalers. Tiny enough to fit in your head. Decent enough to blow it.

**Choose from:**

- **Flat** (exact), **HNSW** (graph), **IVF** (clustering), **PQ** (quantization), or **IVFPQ** (hybrid) storage backends
- **Full-Text Search**: BM25 ranking algorithm with tokenization and normalization
- **Metadata Filtering**: Fast filtering using Roaring Bitmaps and Bit-Sliced Indexes
- **Ranking Programmability**: Reciprocal Rank Fusion, Fixed size result sets, Threshold based result sets, Dynamic result sets etc.
- **Hybrid Search**: Unified interface combining vector, text, and metadata search

## Table of Contents

- [Overview](#overview)
- [Features](#features)
- [Installation](#installation)
- [Quick Start](#quick-start)
- [Architecture](#architecture)
- [Core Concepts](#core-concepts)
- [API Reference](docs/API.md)
- [Examples](docs/EXAMPLE.md)
- [Configuration](#configuration)
- [API Details](#api-details)
- [Use Cases](#use-cases)
- [Contributing](#contributing)
- [License](#license)

## Overview

Everything you need to understand how vector databases actually work—and build one yourself.

**What's inside:**

- **5 Vector Storage Types**: Flat, HNSW, IVF, PQ, IVFPQ
- **3 Distance Metrics**: L2, L2 Squared, Cosine
- **Full-Text Search**: BM25 ranking with Unicode tokenization
- **Metadata Filtering**: Roaring bitmaps + Bit-Sliced Indexes
- **Hybrid Search**: Combine vector + text + metadata with Reciprocal Rank Fusion
- **Advanced Search**: Multi-KNN queries, multi-query operations, autocut result truncation
- **Production Features**: Thread-safe, serialization, soft deletes, configurable parameters

Everything you need to understand how vector databases actually work—and build one yourself.

## Features

### Vector Storage

- **Flat**: Brute-force exact search (100% recall baseline)
- **HNSW**: Hierarchical navigable small world graphs (95-99% recall, O(log n) search)
- **IVF**: Inverted file index with k-means clustering (85-95% recall, 10-20x speedup)
- **PQ**: Product quantization for compression (85-95% recall, 10-500x memory reduction)
- **IVFPQ**: IVF + PQ combined (85-95% recall, 100x speedup + 500x compression)

### Search Modalities

- **Vector Search**: L2, L2 Squared, and Cosine distance metrics
- **Full-Text Search**: BM25 ranking with Unicode-aware tokenization
- **Metadata Filtering**: Boolean queries on structured attributes
- **Hybrid Search**: Combine all three with configurable fusion strategies

### Fusion Strategies

- **Weighted Sum**: Linear combination with configurable weights
- **Reciprocal Rank Fusion (RRF)**: Scale-independent rank-based fusion
- **Max/Min Score**: Simple score aggregation

### Data Structures (The Good Stuff)

- **HNSW Graphs**: Multi-layer skip lists for approximate nearest neighbor search
- **Roaring Bitmaps**: Compressed bitmaps for metadata filtering (array, bitmap, run-length encoding)
- **Bit-Sliced Index (BSI)**: Efficient numeric range queries without full scans
- **Product Quantization Codebooks**: Learned k-means centroids for vector compression
- **Inverted Indexes**: Token-to-document mappings for full-text search

### Other Capabilities

- **Quantization**: Full precision, half precision, int8 precision
- **Soft Deletes**: Fast deletion with lazy cleanup
- **Serialization**: Persist and reload indexes
- **Thread-Safe**: Concurrent read/write operations
- **Autocut**: Automatic result truncation based on score gaps

## Installation

```bash
go get github.com/wizenheimer/comet
```

## Quick Start

```go
package main

import (
    "fmt"
    "log"

"github.com/wizenheimer/comet"
)

func main() {
    // Create a vector store (384-dimensional embeddings with cosine distance)
    index, err := comet.NewFlatIndex(384, comet.Cosine)
    if err != nil {
        log.Fatal(err)
    }

// Add vectors
    vec1 := make([]float32, 384)
    // ... populate vec1 with your embedding ...
    node := comet.NewVectorNode(vec1)
    index.Add(*node)

// Search for similar vectors
    query := make([]float32, 384)
    // ... populate query vector ...
    results, err := index.NewSearch().
        WithQuery(query).
        WithK(10).
        Execute()

if err != nil {
        log.Fatal(err)
    }

// Process results
    for i, result := range results {
        fmt.Printf("%d. ID=%d, Score=%.4f\n", i+1, result.GetId(), result.GetScore())
    }
}
```

Output:

```
1. ID=123, Score=0.0234
2. ID=456, Score=0.0567
3. ID=789, Score=0.0823
...
```

## Architecture

### System Architecture

Comet is organized into three main search engines that can work independently or together:

#### Application Layer

```
┌─────────────────────────────────────────────────────────────┐
│                    Your Application                          │
│            (Using Comet as a Go Library)                     │
└──────────────────────┬──────────────────────────────────────┘
                       │
         ┌─────────────┼─────────────┐
         │             │             │
         ▼             ▼             ▼
    Vector         Text         Metadata
```

#### Search Engine Layer

```
┌─────────────┐    ┌─────────────┐    ┌─────────────┐
│   Vector    │    │    Text     │    │  Metadata   │
│   Search    │    │   Search    │    │  Filtering  │
│   Engine    │    │   Engine    │    │   Engine    │
└──────┬──────┘    └──────┬──────┘    └──────┬──────┘
       │                  │                  │
       │ Semantic         │ Keywords         │ Filters
       │ Similarity       │ + Relevance      │ + Boolean Logic
       ▼                  ▼                  ▼
```

#### Index Storage Layer

```
┌─────────────┐    ┌─────────────┐    ┌─────────────┐
│ HNSW / IVF  │    │ BM25 Index  │    │  Roaring    │
│ / PQ / Flat │    │ (Inverted)  │    │  Bitmaps    │
└─────────────┘    └─────────────┘    └─────────────┘
   Graph/Trees      Token→DocIDs       Compressed Sets
```

#### Hybrid Coordinator

```
                 All Three Engines
                       │
                       ▼
              ┌─────────────────┐
              │  Hybrid Search   │
              │  Coordinator     │
              │  (Score Fusion)  │
              └─────────────────┘
                       │
                       ▼
              Combined Results
```

### Component Details

#### Component A: Vector Storage Engine

Manages vector storage and similarity search across multiple index types.

**Common Interface:**

```
┌────────────────────────────────────┐
│  VectorIndex Interface             │
│                                    │
│  ├─ Train(vectors)                 │
│  ├─ Add(vector)                    │
│  ├─ Remove(vector)                 │
│  └─ NewSearch()                    │
└────────────────────────────────────┘
```

**Available Implementations:**

```
FlatIndex          → Brute force, 100% recall
HNSWIndex          → Graph-based, O(log n)
IVFIndex           → Clustering, 10-20x faster
PQIndex            → Quantization, 10-500x compression
IVFPQIndex         → Hybrid, best of IVF + PQ
```

**Responsibilities:**

- Vector preprocessing (normalization for cosine distance)
- Distance calculations (Euclidean, L2², Cosine)
- K-nearest neighbor search
- Serialization/deserialization
- Soft delete management with flush mechanism

**Performance Characteristics:**

- Flat: O(n×d) search, 100% recall
- HNSW: O(M×ef×log n) search, 95-99% recall
- IVF: O(nProbes×n/k×d) search, 85-95% recall

#### Component B: Text Search Engine

Full-text search using BM25 ranking algorithm.

**Inverted Index:**

```
┌────────────────────────────────────┐
│  term → RoaringBitmap(docIDs)      │
│                                    │
│  "machine"  →  {1, 5, 12, 45}      │
│  "learning" →  {1, 3, 12, 20}      │
│  "neural"   →  {3, 20, 45}         │
└────────────────────────────────────┘
```

**Term Frequencies:**

```
┌────────────────────────────────────┐
│  term → {docID: count}             │
│                                    │
│  "machine" → {1: 3, 5: 1, 12: 2}   │
└────────────────────────────────────┘
```

**Document Stats:**

```
┌────────────────────────────────────┐
│  docID → (length, token_count)     │
│                                    │
│  1  →  (250 chars, 45 tokens)      │
│  5  →  (180 chars, 32 tokens)      │
└────────────────────────────────────┘
```

**Responsibilities:**

- Text tokenization (UAX#29 word segmentation)
- Unicode normalization (NFKC)
- Inverted index maintenance
- BM25 score calculation
- Top-K retrieval with heap

**Performance Characteristics:**

- Add: O(m) where m = tokens
- Search: O(q×d_avg) where q = query terms, d_avg = avg docs per term
- Memory: Compressed inverted index, no original text stored

#### Component C: Metadata Filter Engine

Fast filtering using compressed bitmaps.

**Categorical Fields (Roaring Bitmaps):**

```
┌────────────────────────────────────┐
│  field:value → Bitmap(docIDs)      │
│                                    │
│  "category:electronics" → {1,5,12} │
│  "category:books"       → {2,8,15} │
│  "in_stock:true"        → {1,2,5}  │
└────────────────────────────────────┘
```

**Numeric Fields (Bit-Sliced Index):**

```
┌────────────────────────────────────┐
│  field → BSI (range queries)       │
│                                    │
│  "price"  → [0-1000, 1000-5000]    │
│  "rating" → [0-5 scale]            │
└────────────────────────────────────┘
```

**Document Universe:**

```
┌────────────────────────────────────┐
│  allDocs → Bitmap(all IDs)         │
│                                    │
│  Used for NOT operations           │
└────────────────────────────────────┘
```

**Responsibilities:**

- Bitmap index maintenance (Roaring compression)
- BSI for numeric range queries
- Boolean query evaluation (AND, OR, NOT)
- Existence checks
- Set operations (IN, NOT IN)

**Performance Characteristics:**

- Add: O(f) where f = fields
- Query: O(f×log n) with bitmap operations
- Memory: Highly compressed, 1-10% of uncompressed

### Data Flow

How a hybrid search request flows through the system:

#### Step 1: Query Input

```
User Query:
├─ Vector:    [0.1, 0.5, ...]
├─ Text:      "machine learning"
└─ Filters:   {category="ai", price<100}
```

#### Step 2: Validation

```
┌────────────┐
│ Validation │ ──✗──> Error Handler
└─────┬──────┘         (Invalid dimension, etc.)
      │
      ✓ Valid
```

#### Step 3: Metadata Pre-filtering

```
┌─────────────────────────┐
│ Metadata Filter Engine  │
│ Apply: category="ai"    │
│        price<100        │
└─────┬───────────────────┘
      │
      ▼
Candidates: {1, 5, 7, 12, 15}
```

#### Step 4: Parallel Search

```
Candidates → Split into both engines

┌────────────┐         ┌────────────┐
│  Vector    │         │   Text     │
│  Search    │         │  Search    │
│ (on cands) │         │ (on cands) │
└─────┬──────┘         └─────┬──────┘
      │                      │
      ▼                      ▼
Vec Results:           Text Results:
{1: 0.2,               {7: 8.5,
 5: 0.3,                1: 7.2,
 7: 0.4}                12: 6.8}
```

#### Step 5: Score Fusion

```
      Both Result Sets
              │
              ▼
      ┌───────────────┐
      │ Score Fusion  │
      │ (RRF/Weighted)│
      └───────┬───────┘
              │
              ▼
      Fused Rankings
```

#### Step 6: Final Ranking

```
      ┌───────────────┐
      │  Rank & Sort  │
      └───────┬───────┘
              │
              ▼
      ┌───────────────┐
      │  Top-K Filter │
      │  (k=10)       │
      └───────┬───────┘
              │
              ▼
      Final Results:
      [{1: 0.8},
       {7: 0.7},
       {5: 0.6}]
```

### Memory Layout

Understanding how different index types use memory:

#### HNSW Index Memory

**File Header (24 bytes):**

```
┌─────────────────────────────┐
│ Magic:      "HNSW" (4 B)    │
│ Version:    1 (4 B)          │
│ Dimensions: 384 (4 B)        │
│ M:          16 (4 B)         │
│ Max Level:  3 (4 B)          │
│ Entry Point: 42 (4 B)        │
└─────────────────────────────┘
```

**Per-Node Storage:**

```
Node ID:       4 bytes
Level:         4 bytes
Vector Data:   1536 bytes (384-dim × 4)
Graph Edges:   320 bytes (M connections × layers)
              ─────────────
Total:         ~1864 bytes per node
```

**Scaling Analysis:**

```
┌───────────────────┬──────────┬───────────┐
│ Component         │ Per Node │ 1M Nodes  │
├───────────────────┼──────────┼───────────┤
│ Vectors (raw)     │ 1536 B   │ 1.46 GB   │
│ Graph structure   │ 320 B    │ 305 MB    │
│ Metadata          │ 8 B      │ 7.6 MB    │
├───────────────────┼──────────┼───────────┤
│ Total             │ 1864 B   │ 1.78 GB   │
└───────────────────┴──────────┴───────────┘
```

#### Product Quantization Memory

**Compression Overview:**

```
Original Vector (384-dim):
384 × 4 bytes = 1536 bytes
         ↓
    Quantization
         ↓
PQ Codes (8 subspaces):
8 × 1 byte = 8 bytes
         ↓
192x smaller!
```

**Codebook Storage:**

```
8 codebooks × 256 centroids × 48 dims × 4 bytes
= 393 KB (shared across all vectors)
```

**1M Vectors Comparison:**

```
┌───────────────────┬────────────┬──────────┐
│ Format            │ Size       │ Ratio    │
├───────────────────┼────────────┼──────────┤
│ Original (float32)│ 1.46 GB    │ 1x       │
│ PQ-8              │ 7.6 MB     │ 192x     │
│ PQ-16             │ 15.3 MB    │ 96x      │
│ PQ-32             │ 30.5 MB    │ 48x      │
│ + Codebooks       │ +393 KB    │ -        │
└───────────────────┴────────────┴──────────┘
```

## Core Concepts

### Concept 1: Vector Storage and Distance Metrics

A vector store maintains high-dimensional embeddings and enables efficient similarity search. The choice of storage type determines the tradeoff between search speed, memory usage, and accuracy.

**Example: How vectors are stored and searched**

Given these input vectors:

```
Vector 1: [0.1, 0.5, 0.3, 0.8]
Vector 2: [0.2, 0.4, 0.7, 0.1]
Query:    [0.15, 0.45, 0.5, 0.5]
```

The index computes distances and returns nearest neighbors:

```
┌─────────────┬────────────────────────────────┬──────────┐
│ Vector ID   │ Distance to Query              │ Rank     │
├─────────────┼────────────────────────────────┼──────────┤
│ 1           │ 0.234 (closest)                │ 1st      │
│ 2           │ 0.567 (further)                │ 2nd      │
└─────────────┴────────────────────────────────┴──────────┘
```

**Visual Representation: Storage Types Comparison**

#### Flat Index (Brute Force)

```
Query → Compare with ALL vectors → Sort → Return K

✓ 100% Accuracy
✗ O(n) time complexity
✗ Slow for large datasets
```

#### HNSW Index (Graph-Based)

```
Layer 2: ●─────────────●    (highways - long jumps)
          │             │
Layer 1: ●───●───●───●    (roads - medium jumps)
          │   │ \ │ \ │
Layer 0: ●─●─●─●─●─●─●    (streets - all nodes)

Search: Start high → Navigate greedily → Descend

✓ O(log n) time complexity
✓ 95-99% recall
✗ 2-3x memory overhead
```

#### IVF Index (Clustering)

```
Cluster 1: ●●●●     Cluster 2: ●●●●
Cluster 3: ●●●●     Cluster 4: ●●●●

Query → Find nearest clusters → Search within

✓ Fast on large datasets
✗ Requires training
~ 85-95% recall
```

#### Product Quantization (Compression)

```
Original:  [0.123, 0.456, 0.789, ...]
                    ↓ Compress
Quantized: [17, 42, 89, ...]

4 bytes each → 1 byte each

✓ 4-32x memory reduction
✗ Slight accuracy loss
```

**Benefits of Different Storage Types:**

- **Flat Index**: Perfect recall, simple, no training. Use for small datasets (<100K vectors)
- **HNSW**: Excellent speed/accuracy tradeoff, no training. Use for most production workloads
- **IVF**: Fast filtering with clusters, scalable. Use for very large datasets (>10M vectors)
- **PQ**: Massive memory savings. Use when storage cost is a concern
- **IVFPQ**: Best of IVF + PQ. Use for extremely large, memory-constrained environments

### Concept 2: BM25 Full-Text Search Algorithm

BM25 (Best Matching 25) ranks documents by relevance to a text query using term frequency and inverse document frequency.

#### Setup

**Test Corpus:**

```
Doc 1: "the quick brown fox jumps over the lazy dog"  (9 words)
Doc 2: "the lazy dog sleeps"                           (4 words)
Doc 3: "quick brown rabbits jump"                      (4 words)
```

**Query:** `"quick brown"`

**Parameters:**

```
Average Document Length: 7 words
K1 = 1.2  (term frequency saturation)
B  = 0.75 (length normalization)
```

#### Step 1: Calculate IDF (Inverse Document Frequency)

**For term "quick":**

```
Appears in: 2 out of 3 documents

IDF = log((N - df + 0.5) / (df + 0.5) + 1)
    = log((3 - 2 + 0.5) / (2 + 0.5) + 1)
        = log(1.5 / 2.5 + 1)
        = log(1.6)
        = 0.470
```

**For term "brown":**

```
Appears in: 2 out of 3 documents
IDF = 0.470  (same calculation)
```

#### Step 2: Calculate TF Component for Each Document

**Doc 1** (9 words - longer than average):

```
Term "quick" (tf=1):
  TF_score = (tf × (K1 + 1)) / (tf + K1 × (1 - B + B × (docLen/avgLen)))
           = (1 × 2.2) / (1 + 1.2 × (1 - 0.75 + 0.75 × (9/7)))
             = 2.2 / 2.457
             = 0.895

Term "brown" (tf=1):
  TF_score = 0.895  (same calculation)
```

**Doc 2** (4 words):

```
Terms "quick" and "brown": tf=0 (not present)
    TF_score = 0
```

**Doc 3** (4 words - shorter than average):

```
Term "quick" (tf=1):
  TF_score = (1 × 2.2) / (1 + 1.2 × (1 - 0.75 + 0.75 × (4/7)))
             = 2.2 / 1.815
             = 1.212

Term "brown" (tf=1):
  TF_score = 1.212  (same calculation)
```

#### Step 3: Calculate Final BM25 Scores

**Combine IDF × TF for each document:**

```
Doc 1: (0.895 × 0.470) + (0.895 × 0.470) = 0.841
Doc 2: 0  (no matching terms)
Doc 3: (1.212 × 0.470) + (1.212 × 0.470) = 1.139
```

#### Final Ranking

```
┌─────────┬──────────┬────────┐
│ Rank    │ Doc ID   │ Score  │
├─────────┼──────────┼────────┤
│ 1st     │ Doc 3    │ 1.139  │
│ 2nd     │ Doc 1    │ 0.841  │
│ 3rd     │ Doc 2    │ 0.000  │
└─────────┴──────────┴────────┘
```

#### Why Doc 3 Ranks Higher

```
Doc 1 vs Doc 3:
├─ Same term frequencies (1 occurrence each)
├─ Doc 3 is shorter (4 words vs 9 words)
├─ BM25 length normalization penalizes longer docs
└─ Result: Doc 3 gets higher TF scores (1.212 vs 0.895)

Key Insight: Shorter documents with same term frequency
             are considered more relevant ✓
```

### Concept 3: Hybrid Search with Score Fusion

Hybrid search combines vector similarity, text relevance, and metadata filtering. Different fusion strategies handle score normalization differently.

#### Query Setup

```
INPUT:
├─ Query:   "machine learning tutorial"
├─ Vector:  [0.12, 0.45, 0.89, ...]  (embedding)
└─ Filter:  category="education" AND price<50
```

#### Step 1: Apply Metadata Filter

```
┌─────────────────────────────────┐
│  Metadata Filtering             │
│  category="education"           │
│  price<50                       │
└─────────────────────────────────┘
                │
                ▼
Candidate Docs: {1, 3, 5, 7, 9, 12, 15, 18, 20}
```

#### Step 2: Vector Search Results

```
Semantic Similarity (on candidates):

┌────────┬──────────┬──────┐
│ Doc ID │ Distance │ Rank │
├────────┼──────────┼──────┤
│   1    │  0.12    │  1   │  ← Closest
│   5    │  0.23    │  2   │
│   7    │  0.34    │  3   │
│  12    │  0.45    │  4   │
└────────┴──────────┴──────┘
```

#### Step 3: Text Search Results

```
BM25 Ranking (on candidates):

┌────────┬────────────┬──────┐
│ Doc ID │ BM25 Score │ Rank │
├────────┼────────────┼──────┤
│   7    │   8.5      │  1   │  ← Most relevant
│   1    │   7.2      │  2   │
│  12    │   6.8      │  3   │
│   5    │   4.1      │  4   │
└────────┴────────────┴──────┘
```

#### Step 4: Reciprocal Rank Fusion (RRF)

**Formula:** `RRF_score = sum(1 / (K + rank_i))` where K=60

**Doc 1 Calculation:**

```
  Vector rank: 1 → 1/(60+1) = 0.0164
Text rank:   2 → 1/(60+2) = 0.0161
                          ────────
Combined RRF score:         0.0325
```

**Doc 5 Calculation:**

```
  Vector rank: 2 → 1/(60+2) = 0.0161
Text rank:   4 → 1/(60+4) = 0.0156
                          ────────
Combined RRF score:         0.0317
```

**Doc 7 Calculation:**

```
  Vector rank: 3 → 1/(60+3) = 0.0159
Text rank:   1 → 1/(60+1) = 0.0164
                          ────────
Combined RRF score:         0.0323
```

**Doc 12 Calculation:**

```
  Vector rank: 4 → 1/(60+4) = 0.0156
Text rank:   3 → 1/(60+3) = 0.0159
                          ────────
Combined RRF score:         0.0315
```

#### Final Ranking

```
┌──────┬────────┬───────────┬──────────────────┐
│ Rank │ Doc ID │ RRF Score │ Why              │
├──────┼────────┼───────────┼──────────────────┤
│ 1st  │   1    │  0.0325   │ Best vector      │
│ 2nd  │   7    │  0.0323   │ Best text        │
│ 3rd  │   5    │  0.0317   │ Balanced         │
│ 4th  │  12    │  0.0315   │ Lower in both    │
└──────┴────────┴───────────┴──────────────────┘
```

#### Why RRF Over Weighted Sum?

```
Problem with Weighted Sum:
├─ Vector distances:    0-2 range
├─ BM25 scores:         0-100+ range
└─ Different scales need manual tuning ✗

RRF Advantages:
├─ ✓ Scale Independent  (uses ranks, not raw scores)
├─ ✓ Robust             (stable across score distributions)
├─ ✓ No Tuning          (no manual weight calibration)
└─ ✓ Industry Standard  (Elasticsearch, Vespa, etc.)
```

## Storage Type Deep Dive

**Choose your poison:** Flat (exact), HNSW (graph), IVF (clustering), PQ (quantization), or IVFPQ (hybrid). Each trades speed, memory, and accuracy differently.

> **Full Deep Dive:** See [INDEX.md](docs/INDEX.md) for complete algorithms, benchmarks, and implementation details.

### Flat Index (Brute Force)

**The Simplest Approach**: Compare query against EVERY vector. 100% recall, zero approximation.

#### How It Works

```
Query Vector
     ↓
┌────────────────────┐
│  Compare to ALL n  │
│     vectors        │  ← Every single one checked
└────────────────────┘   No shortcuts!
        ↓
   Sort by distance
        ↓
   Return top K
```

#### Implementation

```
1. Store vectors → Raw float32 arrays
2. Search step   → Compute distance to all vectors
3. Selection     → Keep top-k closest
4. Index struct  → None (just a list)
```

#### Complexity Analysis

```
┌─────────────┬──────────────────────────┐
│ Operation   │ Complexity               │
├─────────────┼──────────────────────────┤
│ Build       │ O(1) - just store        │
│ Search      │ O(n × d) - check all     │
│ Memory      │ O(n × d) - raw vectors   │
│ Recall      │ 100% - exhaustive        │
└─────────────┴──────────────────────────┘
```

#### When to Use

```
✓ Small datasets (<10K vectors)
✓ 100% recall required (fingerprinting, security)
✓ Benchmarking baseline
✗ Large datasets (too slow)
```

---

### HNSW Index (Hierarchical Graph)

**The Graph Navigator**: Build a multi-layer graph where each node connects to nearby vectors. Search by greedy navigation from layer to layer.

#### Graph Structure

```
Layer 2: [A]─────────[D]           ← Highways (long jumps)
          │           │              Few nodes

Layer 1: [A]──[B]────[D]──[E]      ← Roads (medium jumps)
          │   │ \    │ \  │          More nodes

Layer 0: [A]─[B]─[C]─[D]─[E]─[F]   ← Streets (short links)
                                      ALL vectors here
```

#### Search Process

```
1. Start at top layer    → Long-range navigation
2. Greedy best move      → Move to closest neighbor
3. Drop to next layer    → Refine search
4. Repeat steps 2-3      → Until Layer 0
5. Return k-nearest      → Final results
```

#### How Insertion Works

```
New Vector:
├─ 1. Add to Layer 0 (always)
├─ 2. Randomly assign to higher layers (exponential decay)
├─ 3. Connect to M nearest neighbors per layer
└─ 4. Update neighbors' connections (bidirectional)
```

#### Complexity Analysis

```
┌─────────────┬────────────────────────────────┐
│ Operation   │ Complexity                     │
├─────────────┼────────────────────────────────┤
│ Search      │ O(M × efSearch × log n)        │
│             │ Typically checks <1% of data   │
│ Insert      │ O(M × efConstruction × log n)  │
│ Memory      │ O(n × d + n × M × log n)       │
│ Recall      │ 95-99% with proper tuning      │
└─────────────┴────────────────────────────────┘
```

#### Key Parameters

```
M (Connections per layer):
├─ 4-8:   Low memory, lower recall
├─ 16:    Balanced (default)
└─ 32-48: High recall, more memory

efConstruction (Build quality):
├─ 100:   Fast build, lower quality
├─ 200:   Good balance (default)
└─ 400+:  Better graph, slower build

efSearch (Search quality):
├─ 50:    Fast search, ~85% recall
├─ 200:   Balanced (default), ~96% recall
└─ 400+:  High recall, slower search
```

#### When to Use

```
✓ Large datasets (10K-10M vectors)
✓ Need 95-99% recall
✓ Sub-millisecond latency required
✓ Can afford 2-3x memory overhead
✗ Memory constrained environments
```

---

### IVF Index (Inverted File with Clustering)

**The Clustering Approach**: Partition vectors into clusters using k-means. Search only the nearest clusters.

#### Build Phase (Training)

```
All Vectors (n)
      ↓
   k-means clustering
      ↓
┌────────────────────────────────────┐
│ [C1]  [C2]  [C3]  [C4]  ... [Cn]  │  ← Centroids
└────────────────────────────────────┘
   ↓      ↓     ↓     ↓         ↓
  {v1}   {v8}  {v3}  {v12}    {v7}     ← Vectors assigned
  {v5}   {v9}  {v6}  {v19}    {v11}      to nearest
  {v20}  ...   ...   ...      ...        centroid
```

#### Search Phase

```
Query Vector
      ↓
Find nProbe nearest centroids
      ↓
┌────────────────────────────┐
│ [C2] [C3]  (only these!)   │  ← Search 2 of 100 clusters
└────────────────────────────┘
   ↓     ↓
  {...} {...}  Search within clusters
      ↓
  Top-k results
```

#### Key Insight

```
Instead of:  Check all 1M vectors
Do this:     1. Find 8 nearest clusters  (O(nClusters))
             2. Search 80K vectors total  (10% of data)
             └─> 10-20x faster!
```

#### Complexity Analysis

```
┌─────────────┬────────────────────────────────┐
│ Operation   │ Complexity                     │
├─────────────┼────────────────────────────────┤
│ Build       │ O(iterations × n × k × d)      │
│             │ k-means clustering             │
│ Search      │ O(k × d + (n/k) × nProbe × d)  │
│             │ Typically checks 5-20% of data │
│ Memory      │ O(n × d + k × d)               │
│ Recall      │ 80-95% depending on nProbe     │
└─────────────┴────────────────────────────────┘
```

#### Key Parameters

```
nClusters (number of partitions):
├─ Rule of thumb: sqrt(n) to n/10
├─ 10K vectors   → 100 clusters
├─ 100K vectors  → 316 clusters
├─ 1M vectors    → 1,000 clusters
└─ More clusters → Faster search, slower build

nProbe (clusters to search):
├─ 1:   Fastest, ~60-70% recall
├─ 8:   Good balance, ~85% recall
├─ 16:  Better recall, ~92% recall
└─ 32+: High recall, ~96% recall
```

#### When to Use

```
✓ Large datasets (>100K vectors)
✓ Can tolerate 85-95% recall
✓ Want 10-20x speedup over Flat
✓ Have training data available
✗ Need 100% recall (use Flat)
✗ Dataset too small (<10K)
```

---

### PQ Index (Product Quantization)

**The Compression Master**: Split vectors into subvectors, quantize each subvector to 256 codes. Reduce memory by 16-32×.

#### Compression Process

```
Original Vector (384 dimensions):
  [0.23, 0.91, ..., 0.15, 0.44, ..., 0.73, 0.22, ...]
   \_____48D_____/  \_____48D_____/  \_____48D_____/
   Subspace 1       Subspace 2       Subspace 3
        ↓                ↓                ↓
   K-means on       K-means on       K-means on
   subspace 1       subspace 2       subspace 3
        ↓                ↓                ↓
 Codebook with    Codebook with    Codebook with
 256 centroids    256 centroids    256 centroids
        ↓                ↓                ↓
   Find nearest    Find nearest     Find nearest
   centroid ID     centroid ID      centroid ID
        ↓                ↓                ↓
      [12]             [203]            [45]
       1 byte          1 byte           1 byte
```

#### Result

```
Before: [0.23, 0.91, ...] → 384 × 4 bytes = 1536 bytes
After:  [12, 203, 45, ...]  → 8 × 1 byte  = 8 bytes

192x compression!
```

#### Search Process

```
1. Query arrives
        ↓
2. Split query into subspaces (like training)
        ↓
3. Precompute distance tables for each subspace
   (query_subspace to all 256 codebook centroids)
        ↓
4. For each vector:
   - Look up codes: [12, 203, 45, ...]
   - Table lookup: distances[12] + distances[203] + ...
   - No float operations! Just array lookups
        ↓
5. Return top-k
```

#### Complexity Analysis

```
┌─────────────┬────────────────────────────────┐
│ Operation   │ Complexity                     │
├─────────────┼────────────────────────────────┤
│ Training    │ O(M × iterations × K × n/M)    │
│             │ K-means on each subspace       │
│ Encoding    │ O(M × K × d/M) per vector      │
│ Search      │ O(M × K + n × M)               │
│             │ Super fast, cache-friendly     │
│ Memory      │ O(n × M) - massive savings!    │
│ Recall      │ 70-85% typical                 │
└─────────────┴────────────────────────────────┘
```

#### Memory Comparison

```
1M vectors, 384 dimensions:

Float32:  1M × 384 × 4 bytes = 1.46 GB
PQ-8:     1M × 8 × 1 byte    = 7.6 MB  (192x smaller!)
PQ-16:    1M × 16 × 1 byte   = 15.3 MB (96x smaller!)
PQ-32:    1M × 32 × 1 byte   = 30.5 MB (48x smaller!)

+ Codebooks: ~393 KB (shared across all vectors)
```

#### Key Parameters

```
M (nSubspaces):
├─ 8:   Maximum compression, lower accuracy
├─ 16:  Good balance
├─ 32:  Better accuracy, less compression
└─ 64:  High accuracy, moderate compression

bitsPerCode:
└─ 8:   Standard (256 centroids per subspace)
        Perfect for uint8 storage
```

#### When to Use

```
✓ Massive datasets (millions of vectors)
✓ Memory is the bottleneck
✓ Can tolerate 70-85% recall
✓ Want 30-200x memory reduction
✗ Need high recall (>95%)
✗ Have plenty of memory
```

---

### IVFPQ Index (Hybrid: Clustering + Quantization)

**Best of Both Worlds**: IVF clusters to reduce search space, PQ compression to reduce memory. The ultimate scalability index.

#### Build Process

**Step 1: IVF Clustering**

```
All Vectors
      ↓
  K-means clustering
      ↓
[C1]  [C2]  [C3]  [C4]  ... [Cn]
```

**Step 2: PQ Compression per Cluster**

```
Cluster 1:        Cluster 2:        Cluster 3:
  {vectors}         {vectors}         {vectors}
      ↓                 ↓                 ↓
  Apply PQ          Apply PQ          Apply PQ
      ↓                 ↓                 ↓
[12,203,45]      [91,34,178]       [56,211,19]
[88,9,101]       [23,156,88]       [199,44,73]
[...]            [...]             [...]
           uint8 codes      uint8 codes       uint8 codes
```

#### Search Process

```
Step 1: IVF Stage
  Query → Find nProbe nearest centroids
          ↓
     [C2] [C3] [C7]  (e.g., 3 of 100 clusters)
          ↓
     Search only 3% of the data!

Step 2: PQ Stage
  For each selected cluster:
    ├─ Precompute distance tables
    ├─ Fast table lookups on PQ codes
    └─ No float operations
          ↓
     Top-k results
```

#### The Magic Combination

```
IVF contributes:
└─ Speed:  10-100x faster (search only nProbe clusters)

PQ contributes:
└─ Memory: 30-200x smaller (compressed codes)

Combined:
└─ Fast + Tiny = Billion-scale capability!
```

#### Complexity Analysis

```
┌─────────────┬────────────────────────────────┐
│ Operation   │ Complexity                     │
├─────────────┼────────────────────────────────┤
│ Training    │ O(IVF_kmeans + PQ_kmeans)      │
│ Search      │ O(k×d + (n/k)×nProbe×M)        │
│             │ Searches ~1-10% of data        │
│ Memory      │ O(n×M + k×d)                   │
│             │ Massive compression            │
│ Recall      │ 70-90% depending on params     │
└─────────────┴────────────────────────────────┘
```

#### Memory Savings Example

```
1M vectors, 384 dimensions:

Float32 + IVF:   1.46 GB
IVFPQ (M=8):     7.6 MB + 400 KB (centroids)
                 = ~8 MB total

180x compression!
```

#### Key Parameters

```
nClusters (IVF):
├─ 100:   For 100K vectors
├─ 1K:    For 1M vectors
└─ 10K:   For 100M vectors

nProbe (IVF search):
├─ 1:     Fastest, lower recall
├─ 8:     Good balance
└─ 16:    Better recall

M (PQ subspaces):
├─ 8:     Maximum compression
├─ 16:    Good balance
└─ 32:    Better accuracy
```

#### When to Use

```
✓ Billion-scale datasets
✓ Need <10ms latency
✓ Severe memory constraints
✓ Can tolerate 70-90% recall
✓ Want 100x speed + 100x compression
✗ Need >95% recall (use HNSW)
✗ Small datasets (use Flat or HNSW)
```

#### Real-World Example

```
Use Case: 100M vectors, 768-dim

Flat Index:
├─ Memory: ~288 GB
├─ Search: ~10 seconds
└─ Not feasible! ✗

IVFPQ:
├─ Memory: ~800 MB
├─ Search: ~5 ms
└─ Practical! ✓
```

---

### Decision Matrix

| Index | Recall | Search Speed  | Memory   | Build Time | Best For                        |
| ----- | ------ | ------------- | -------- | ---------- | ------------------------------- |
| Flat  | 100%   | Slow O(n)     | High     | Instant    | <10k vectors, benchmarks        |
| HNSW  | 90-99% | Fast O(log n) | Highest  | Slow       | 10k-10M vectors, low latency    |
| IVF   | 80-95% | Medium        | High     | Medium     | >100k vectors, moderate recall  |
| PQ    | 70-85% | Fast          | Lowest   | Slow       | >1M vectors, memory-constrained |
| IVFPQ | 70-90% | Fastest       | Very Low | Slow       | >10M vectors, billion-scale     |

**Rules of thumb:**

- **Small data (<10k)**: Flat - brute force is fast enough
- **Medium data (10k-1M)**: HNSW - best recall/speed tradeoff
- **Large data (1M-100M)**: IVF or PQ - choose speed (IVF) vs memory (PQ)
- **Massive data (>100M)**: IVFPQ - only option that scales to billions

**Latency targets:**

- Flat: 1-100ms (depends on n)
- HNSW: 0.1-2ms (sub-millisecond possible)
- IVF: 0.5-5ms
- PQ: 1-10ms (fast scan but approximate)
- IVFPQ: 0.5-3ms (fastest for massive datasets)

## API Reference

For detailed API documentation, see [API.md](docs/API.md).

## Examples

For practical examples and code samples, see [EXAMPLE.md](docs/EXAMPLE.md).

## Configuration

### Basic Configuration

```go
// Flat Index - No configuration needed
flatIdx, _ := comet.NewFlatIndex(384, comet.Cosine)

// HNSW Index - Configure build and search parameters
hnswIdx, _ := comet.NewHNSWIndex(
    384,              // dimensions
    comet.Cosine,     // distance metric
    16,               // M: connections per layer
    200,              // efConstruction: build quality
    200,              // efSearch: search quality
)

// IVF Index - Configure clustering
ivfIdx, _ := comet.NewIVFIndex(
    384,              // dimensions
    comet.Cosine,     // distance metric
    100,              // nClusters: number of partitions
)

// Training required for IVF
trainingVectors := []comet.VectorNode{ /* ... */ }
ivfIdx.Train(trainingVectors)
```

### Configuration Options

#### HNSW Parameters

**M (Connections Per Layer)**

- Type: `int`
- Default: `16`
- Range: 4 to 64
- Description: Number of bidirectional connections per node at each layer (except layer 0 which uses 2×M)

Effects of different values:

```
┌─────────┬──────────────────────────────────────────┐
│ Value   │ Effect                                   │
├─────────┼──────────────────────────────────────────┤
│ 4-8     │ Low memory, faster build, lower recall   │
│ 12-16   │ Balanced (recommended for most cases)    │
│ 24-48   │ High recall, slower build, more memory   │
│ 64+     │ Diminishing returns, excessive memory    │
└─────────┴──────────────────────────────────────────┘
```

**efConstruction (Build-Time Candidate List Size)**

- Type: `int`
- Default: `200`
- Range: 100 to 1000
- Description: Size of candidate list during index construction. Higher = better graph quality

Effects:

```
┌─────────┬──────────────────────────────────────────┐
│ Value   │ Effect                                   │
├─────────┼──────────────────────────────────────────┤
│ 100     │ Fast build, lower quality graph          │
│ 200     │ Good balance (default)                   │
│ 400-500 │ Better quality, 2-3x slower build        │
│ 800+    │ Marginal gains, very slow build          │
└─────────┴──────────────────────────────────────────┘
```

**efSearch (Search-Time Candidate List Size)**

- Type: `int`
- Default: `200`
- Range: k to 1000 (must be >= k)
- Description: Size of candidate list during search. Can be adjusted dynamically.

Effects:

```
┌─────────┬──────────────────────────────────────────┐
│ Value   │ Effect                                   │
├─────────┼──────────────────────────────────────────┤
│ 50      │ Very fast, ~85% recall                   │
│ 100     │ Fast, ~92% recall                        │
│ 200     │ Balanced, ~96% recall                    │
│ 400     │ Slower, ~98% recall                      │
│ 800     │ Much slower, ~99% recall                 │
└─────────┴──────────────────────────────────────────┘
```

Example:

```go
// Create HNSW with high quality settings
index, _ := comet.NewHNSWIndex(
    384,
    comet.Cosine,
    32,    // More connections = better recall
    400,   // Higher construction quality
    200,   // Search quality (can adjust later)
)

// Dynamically adjust search quality
index.SetEfSearch(400)  // Trade speed for recall
```

#### IVF Parameters

**nClusters (Number of Clusters)**

- Type: `int`
- Default: sqrt(n) where n = dataset size
- Range: 16 to n/100
- Description: Number of k-means clusters (Voronoi cells) to partition the space

```
┌─────────────┬────────────┬─────────────────────────┐
│ Dataset Size│ nClusters  │ Typical Range           │
├─────────────┼────────────┼─────────────────────────┤
│ 10K         │ 100        │ 50-200                  │
│ 100K        │ 316        │ 200-500                 │
│ 1M          │ 1000       │ 500-2000                │
│ 10M         │ 3162       │ 2000-5000               │
└─────────────┴────────────┴─────────────────────────┘
```

**nProbes (Search-Time Clusters to Probe)**

- Type: `int`
- Default: `1`
- Range: 1 to nClusters
- Description: Number of nearest clusters to search during query

```
┌─────────┬──────────────────────────────────────────┐
│ nProbes │ Effect                                   │
├─────────┼──────────────────────────────────────────┤
│ 1       │ Fastest, ~60-70% recall                  │
│ 8       │ Good balance, ~85% recall                │
│ 16      │ Better recall, ~92% recall               │
│ 32      │ High recall, ~96% recall                 │
│ 64      │ Very high recall, slower                 │
└─────────┴──────────────────────────────────────────┘
```

Example:

```go
// Create IVF index
index, _ := comet.NewIVFIndex(384, comet.Cosine, 256)

// Train with representative sample
trainData := sampleVectors(10000)  // 10K samples for training
index.Train(trainData)

// Search with multiple probes
results, _ := index.NewSearch().
    WithQuery(query).
    WithK(10).
    WithNProbes(16).  // Search 16 nearest clusters
    Execute()
```

### Advanced Configuration

#### Fusion Configuration

```go
// Weighted Sum Fusion (manual weights)
config := &comet.FusionConfig{
    VectorWeight: 0.7,  // 70% weight to semantic similarity
    TextWeight:   0.3,  // 30% weight to keyword relevance
}
fusion, _ := comet.NewFusion(comet.WeightedSumFusion, config)

hybridSearch := hybrid.NewSearch().
    WithVector(queryVec).
    WithText("machine learning").
    WithFusion(fusion).
    Execute()

// Reciprocal Rank Fusion (rank-based, no weights needed)
hybridSearch := hybrid.NewSearch().
    WithVector(queryVec).
    WithText("machine learning").
    WithFusionKind(comet.ReciprocalRankFusion).
    Execute()
```

#### Distance Metrics

```go
// Euclidean (L2): Use when magnitude matters
euclideanIdx, _ := comet.NewFlatIndex(384, comet.Euclidean)

// L2 Squared: Faster than Euclidean (no sqrt), preserves ranking
l2sqIdx, _ := comet.NewFlatIndex(384, comet.L2Squared)

// Cosine: Use for normalized vectors (text embeddings, etc.)
cosineIdx, _ := comet.NewFlatIndex(384, comet.Cosine)
```

## API Details

### FlatIndex

**Constructor:**

```go
func NewFlatIndex(dim int, distanceKind DistanceKind) (*FlatIndex, error)
```

**Parameters:**

| Parameter      | Type           | Required | Description                                            |
| -------------- | -------------- | -------- | ------------------------------------------------------ |
| `dim`          | `int`          | Yes      | Vector dimension (must be > 0)                         |
| `distanceKind` | `DistanceKind` | Yes      | Distance metric: `Euclidean`, `L2Squared`, or `Cosine` |

**Returns:**

- `*FlatIndex`: Initialized flat index
- `error`: Error if parameters are invalid

### HNSWIndex

**Constructor:**

```go
func NewHNSWIndex(dim int, distanceKind DistanceKind, m, efConstruction, efSearch int) (*HNSWIndex, error)
```

**Parameters:**

| Parameter        | Type           | Required | Default          | Description                                                           |
| ---------------- | -------------- | -------- | ---------------- | --------------------------------------------------------------------- |
| `dim`            | `int`          | Yes      | -                | Vector dimension (must be > 0)                                        |
| `distanceKind`   | `DistanceKind` | Yes      | -                | Distance metric: `Euclidean`, `L2Squared`, or `Cosine`                |
| `m`              | `int`          | No       | 16               | Max connections per node (higher = better accuracy, more memory)      |
| `efConstruction` | `int`          | No       | 200              | Build-time search depth (higher = better graph quality, slower build) |
| `efSearch`       | `int`          | No       | `efConstruction` | Query-time search depth (higher = better accuracy, slower search)     |

**Returns:**

- `*HNSWIndex`: Initialized HNSW index
- `error`: Error if parameters are invalid

**Parameter Guidelines:**

```
┌──────────────┬─────┬────────────────┬──────────┬─────────────┐
│ Use Case     │  M  │ efConstruction │ efSearch │ Description │
├──────────────┼─────┼────────────────┼──────────┼─────────────┤
│ Fast         │  8  │      100       │    50    │ Speed first │
│ Balanced     │ 16  │      200       │   100    │ Default     │
│ High Recall  │ 32  │      400       │   200    │ Accuracy    │
│ Memory Eff.  │  4  │       50       │    25    │ Low memory  │
└──────────────┴─────┴────────────────┴──────────┴─────────────┘
```

### IVFIndex

**Constructor:**

```go
func NewIVFIndex(dim int, nlist int, distanceKind DistanceKind) (*IVFIndex, error)
```

**Parameters:**

| Parameter      | Type           | Required | Description                                            |
| -------------- | -------------- | -------- | ------------------------------------------------------ |
| `dim`          | `int`          | Yes      | Vector dimension (must be > 0)                         |
| `nlist`        | `int`          | Yes      | Number of clusters/partitions (must be > 0)            |
| `distanceKind` | `DistanceKind` | Yes      | Distance metric: `Euclidean`, `L2Squared`, or `Cosine` |

**Returns:**

- `*IVFIndex`: Initialized IVF index
- `error`: Error if parameters are invalid

**Parameter Guidelines:**

```
nlist Selection:
├─ Small dataset (10K-100K):    nlist = sqrt(n) = 100-300
├─ Medium dataset (100K-1M):    nlist = sqrt(n) = 300-1000
├─ Large dataset (1M-10M):      nlist = sqrt(n) = 1000-3000
└─ Very large (10M+):           nlist = sqrt(n) = 3000-10000

Rule of thumb: nlist ≈ sqrt(number_of_vectors)
```

**Search Parameters:**

```go
// nProbe: number of clusters to search (1 to nlist)
results, _ := index.NewSearch().
    WithQuery(queryVec).
    WithK(10).
    WithNProbe(8).  // Search top 8 nearest clusters
    Execute()

Speed vs Accuracy:
├─ nProbe = 1:     Fastest, lowest recall
├─ nProbe = 8:     Balanced (typical)
├─ nProbe = nlist: Exhaustive (same as flat)
```

### PQIndex

**Constructor:**

```go
func NewPQIndex(dim int, distanceKind DistanceKind, M int, Nbits int) (*PQIndex, error)
```

**Parameters:**

| Parameter      | Type           | Required | Constraint   | Description                                            |
| -------------- | -------------- | -------- | ------------ | ------------------------------------------------------ |
| `dim`          | `int`          | Yes      | > 0          | Vector dimension                                       |
| `distanceKind` | `DistanceKind` | Yes      | -            | Distance metric: `Euclidean`, `L2Squared`, or `Cosine` |
| `M`            | `int`          | Yes      | dim % M == 0 | Number of subspaces (dim must be divisible by M)       |
| `Nbits`        | `int`          | Yes      | 1-16         | Bits per subspace (typical: 8)                         |

**Returns:**

- `*PQIndex`: Initialized PQ index
- `error`: Error if parameters are invalid or constraints violated

**Parameter Guidelines:**

```
M (Number of Subspaces):
├─ M = 8:    192x compression (typical, good balance)
├─ M = 16:    96x compression (better accuracy)
├─ M = 32:    48x compression (highest accuracy)
└─ Constraint: dim must be divisible by M

Nbits (Codebook size = 2^Nbits):
├─ Nbits = 4:   16 centroids per subspace (very fast)
├─ Nbits = 8:  256 centroids per subspace (typical)
├─ Nbits = 12: 4096 centroids (high accuracy)
└─ Constraint: 1 ≤ Nbits ≤ 16

Common Configurations:
┌──────┬───────┬───────────────┬─────────────────────┐
│  M   │ Nbits │ Compression   │ Use Case            │
├──────┼───────┼───────────────┼─────────────────────┤
│   8  │   8   │ 192x (1 byte) │ Maximum compression │
│  16  │   8   │  96x (2 byte) │ Balanced            │
│  32  │   8   │  48x (4 byte) │ Better accuracy     │
│   8  │  12   │ 128x (1.5 B)  │ Higher quality      │
└──────┴───────┴───────────────┴─────────────────────┘
```

### IVFPQIndex

**Constructor:**

```go
func NewIVFPQIndex(dim int, distanceKind DistanceKind, nlist int, m int, nbits int) (*IVFPQIndex, error)
```

**Parameters:**

| Parameter      | Type           | Required | Constraint   | Description                                            |
| -------------- | -------------- | -------- | ------------ | ------------------------------------------------------ |
| `dim`          | `int`          | Yes      | > 0          | Vector dimension                                       |
| `distanceKind` | `DistanceKind` | Yes      | -            | Distance metric: `Euclidean`, `L2Squared`, or `Cosine` |
| `nlist`        | `int`          | Yes      | > 0          | Number of IVF clusters                                 |
| `m`            | `int`          | Yes      | dim % m == 0 | Number of PQ subspaces                                 |
| `nbits`        | `int`          | Yes      | 1-16         | Bits per PQ subspace                                   |

**Returns:**

- `*IVFPQIndex`: Initialized IVFPQ index
- `error`: Error if parameters are invalid

**Parameter Guidelines:**

```
Combined IVF + PQ Configuration:

IVF Parameters:
├─ nlist ≈ sqrt(n) for number of vectors
└─ See IVFIndex guidelines above

PQ Parameters:
├─ m: Typically 8, 16, or 32
└─ nbits: Typically 8

Common Configurations for 100M vectors (384-dim):
┌────────┬─────┬────────┬──────────┬─────────────────┐
│ nlist  │  m  │ nbits  │ Memory   │ Use Case        │
├────────┼─────┼────────┼──────────┼─────────────────┤
│  4096  │  8  │   8    │  ~800 MB │ Extreme speed   │
│  8192  │  8  │   8    │  ~900 MB │ Balanced        │
│ 16384  │ 16  │   8    │ ~1.6 GB  │ Better accuracy │
│  8192  │  8  │  12    │ ~1.2 GB  │ High quality    │
└────────┴─────┴────────┴──────────┴─────────────────┘

Memory Savings Example (100M vectors, 384-dim):
├─ Original float32:  100M × 384 × 4 = 146 GB
├─ IVF only:          Still ~146 GB (no compression)
├─ PQ only:           100M × 8 × 1 = 760 MB (faster train)
└─ IVFPQ (m=8):       100M × 8 × 1 + centroids ≈ 800 MB (best of both!)
```

**Search Parameters:**

```go
results, _ := index.NewSearch().
    WithQuery(queryVec).
    WithK(10).
    WithNProbe(8).       // IVF: clusters to search
    WithNRefine(100).    // Optional: refine top-100 with original vectors
    Execute()
```

### BM25SearchIndex

**Constructor:**

```go
func NewBM25SearchIndex() *BM25SearchIndex
```

**Parameters:** None (uses default BM25 parameters: k1=1.5, b=0.75)

**Returns:**

- `*BM25SearchIndex`: Initialized BM25 full-text search index

**BM25 Parameters:**

- `k1 = 1.5`: Term frequency saturation (typical range: 1.2-2.0)
- `b = 0.75`: Document length normalization (typical range: 0.5-0.9)

### RoaringMetadataIndex

**Constructor:**

```go
func NewRoaringMetadataIndex() *RoaringMetadataIndex
```

**Parameters:** None

**Returns:**

- `*RoaringMetadataIndex`: Initialized metadata filtering index using Roaring Bitmaps

### HybridSearchIndex

**Constructor:**

```go
func NewHybridSearchIndex(
    vectorIndex VectorIndex,
    textIndex TextIndex,
    metadataIndex MetadataIndex,
) HybridSearchIndex
```

**Parameters:**

| Parameter       | Type            | Required | Description                                   |
| --------------- | --------------- | -------- | --------------------------------------------- |
| `vectorIndex`   | `VectorIndex`   | Yes      | Any vector index (Flat, HNSW, IVF, PQ, IVFPQ) |
| `textIndex`     | `TextIndex`     | Yes      | BM25 text search index                        |
| `metadataIndex` | `MetadataIndex` | Yes      | Roaring metadata filter index                 |

**Returns:**

- `HybridSearchIndex`: Initialized hybrid search combining all three modalities

## Search APIs

### Vector Search (VectorSearch Interface)

**Creating a Search:**

```go
search := index.NewSearch()  // Available on all VectorIndex implementations
```

**Methods:**

| Method                 | Parameters             | Description                                                                               |
| ---------------------- | ---------------------- | ----------------------------------------------------------------------------------------- |
| `WithQuery`            | `queries ...[]float32` | Set query vector(s) for similarity search                                                 |
| `WithNodes`            | `nodes ...uint32`      | Find vectors similar to indexed nodes by ID                                               |
| `WithK`                | `k int`                | Number of results to return (default: 10)                                                 |
| `WithDocumentIDs`      | `ids ...uint32`        | Pre-filter: only search within these document IDs                                         |
| `WithScoreAggregation` | `agg ScoreAggregation` | How to combine multi-query results: `SumAggregation`, `MaxAggregation`, `MeanAggregation` |
| `WithThreshold`        | `threshold float32`    | Only return results with distance ≤ threshold                                             |
| `WithAutocut`          | `enabled bool`         | Automatically determine optimal cutoff point                                              |
| `Execute`              | -                      | Run the search, returns `[]VectorResult, error`                                           |

**HNSW-Specific Methods:**

| Method         | Parameters | Description                              |
| -------------- | ---------- | ---------------------------------------- |
| `WithEfSearch` | `ef int`   | Override default efSearch for this query |

**IVF-Specific Methods:**

| Method       | Parameters   | Description                               |
| ------------ | ------------ | ----------------------------------------- |
| `WithNProbe` | `nprobe int` | Number of clusters to search (1 to nlist) |

**IVFPQ-Specific Methods:**

| Method        | Parameters    | Description                                |
| ------------- | ------------- | ------------------------------------------ |
| `WithNProbe`  | `nprobe int`  | Number of clusters to search               |
| `WithNRefine` | `nrefine int` | Refine top-N results with original vectors |

**Examples:**

```go
// Basic single-query search
results, err := index.NewSearch().
    WithQuery(queryVector).
    WithK(10).
    Execute()

// Multi-query with aggregation
results, _ := index.NewSearch().
    WithQuery(query1, query2, query3).
    WithK(20).
    WithScoreAggregation(comet.MeanAggregation).
    Execute()

// Node-based search (find similar to existing vectors)
results, _ := index.NewSearch().
    WithNodes(1, 5, 10).  // IDs of indexed vectors
    WithK(10).
    Execute()

// Pre-filtered search
eligibleIDs := []uint32{100, 200, 300, 400, 500}
results, _ := index.NewSearch().
    WithQuery(queryVector).
    WithDocumentIDs(eligibleIDs...).
    WithK(5).
    Execute()

// Distance threshold filtering
results, _ := index.NewSearch().
    WithQuery(queryVector).
    WithK(100).
    WithThreshold(0.5).  // Only distances ≤ 0.5
    Execute()

// Autocut (automatic result truncation)
results, _ := index.NewSearch().
    WithQuery(queryVector).
    WithK(100).
    WithAutocut(true).  // Returns fewer if quality drops
    Execute()

// HNSW with custom efSearch
hnswIndex, _ := comet.NewHNSWIndex(384, comet.Cosine, 16, 200, 100)
results, _ := hnswIndex.NewSearch().
    WithQuery(queryVector).
    WithK(10).
    WithEfSearch(200).  // Higher accuracy for this query
    Execute()

// IVF with nProbe
ivfIndex, _ := comet.NewIVFIndex(384, 1000, comet.Cosine)
results, _ := ivfIndex.NewSearch().
    WithQuery(queryVector).
    WithK(10).
    WithNProbe(16).  // Search 16 nearest clusters
    Execute()

// IVFPQ with refinement
ivfpqIndex, _ := comet.NewIVFPQIndex(384, comet.Cosine, 8192, 8, 8)
results, _ := ivfpqIndex.NewSearch().
    WithQuery(queryVector).
    WithK(10).
    WithNProbe(32).
    WithNRefine(100).  // Refine top-100 with original vectors
    Execute()
```

**Result Format:**

```go
type VectorResult struct {
    Node  VectorNode  // The matched vector node
    Score float32     // Distance score (lower = more similar)
}

// Access results
for _, result := range results {
    id := result.GetId()
    score := result.GetScore()
    vector := result.Node.Vector()
    fmt.Printf("ID: %d, Distance: %.4f\n", id, score)
}
```

**Score Aggregation Strategies:**

```go
// When using multiple queries, results are aggregated:

comet.SumAggregation   // Sum of all distances (penalizes far results)
comet.MaxAggregation   // Maximum distance (pessimistic)
comet.MeanAggregation  // Average distance (balanced, recommended)
```

### Text Search (TextSearch Interface)

**Creating a Search:**

```go
search := textIndex.NewSearch()  // BM25SearchIndex
```

**Methods:**

| Method            | Parameters      | Description                                       |
| ----------------- | --------------- | ------------------------------------------------- |
| `WithQuery`       | `query string`  | Text query for keyword search                     |
| `WithK`           | `k int`         | Number of results to return (default: 10)         |
| `WithDocumentIDs` | `ids ...uint32` | Pre-filter: only search within these document IDs |
| `WithAutocut`     | `enabled bool`  | Automatically determine optimal cutoff point      |
| `Execute`         | -               | Run the search, returns `[]TextResult, error`     |

**Examples:**

```go
// Basic text search
results, err := textIndex.NewSearch().
    WithQuery("machine learning algorithms").
    WithK(10).
    Execute()

// Pre-filtered text search
eligibleIDs := []uint32{1, 5, 10, 15, 20}
results, _ := textIndex.NewSearch().
    WithQuery("neural networks").
    WithDocumentIDs(eligibleIDs...).
    WithK(5).
    Execute()

// With autocut
results, _ := textIndex.NewSearch().
    WithQuery("deep learning").
    WithK(50).
    WithAutocut(true).  // Returns fewer if relevance drops
    Execute()
```

**Result Format:**

```go
type TextResult struct {
    Node  TextNode  // The matched text node
    Score float32   // BM25 relevance score (higher = more relevant)
}

// Access results
for _, result := range results {
    id := result.GetId()
    score := result.GetScore()
    text := result.Node.Text()
    fmt.Printf("ID: %d, BM25: %.4f, Text: %s\n", id, score, text)
}
```

**BM25 Scoring:**

```
BM25 score components:
├─ IDF: Term rarity (rare terms score higher)
├─ TF:  Term frequency (with saturation via k1)
└─ DL:  Document length normalization (via b)

Higher score = more relevant
Typical range: 0-10+ (no upper bound)
```

### Metadata Search (MetadataSearch Interface)

**Creating a Search:**

```go
search := metadataIndex.NewSearch()  // RoaringMetadataIndex
```

**Methods:**

| Method        | Parameters          | Description                                       |
| ------------- | ------------------- | ------------------------------------------------- |
| `WithFilters` | `filters ...Filter` | Metadata filter conditions (AND logic)            |
| `Execute`     | -                   | Run the search, returns `[]MetadataResult, error` |

**Filter Functions:**

| Function  | Parameters                           | Description                          |
| --------- | ------------------------------------ | ------------------------------------ |
| `Eq`      | `field string, value interface{}`    | Equality: field == value             |
| `Lt`      | `field string, value interface{}`    | Less than: field < value             |
| `Lte`     | `field string, value interface{}`    | Less than or equal: field ≤ value    |
| `Gt`      | `field string, value interface{}`    | Greater than: field > value          |
| `Gte`     | `field string, value interface{}`    | Greater than or equal: field ≥ value |
| `Between` | `field string, min, max interface{}` | Range: min ≤ field ≤ max             |

**Examples:**

```go
// Single filter
results, err := metadataIndex.NewSearch().
    WithFilters(comet.Eq("category", "electronics")).
    Execute()

// Multiple filters (AND logic)
results, _ := metadataIndex.NewSearch().
    WithFilters(
        comet.Eq("category", "books"),
        comet.Gte("rating", 4.0),
        comet.Lte("price", 50.0),
        comet.Eq("in_stock", true),
    ).
    Execute()

// Range filter
results, _ := metadataIndex.NewSearch().
    WithFilters(
        comet.Between("year", 2020, 2024),
        comet.Eq("status", "published"),
    ).
    Execute()

// Numeric comparisons
results, _ := metadataIndex.NewSearch().
    WithFilters(
        comet.Gt("views", 1000),
        comet.Lt("price", 100),
    ).
    Execute()

// String equality
results, _ := metadataIndex.NewSearch().
    WithFilters(
        comet.Eq("author", "John Doe"),
        comet.Eq("language", "en"),
    ).
    Execute()
```

**Result Format:**

```go
type MetadataResult struct {
    Node MetadataNode  // The matched metadata node
}

// Access results
for _, result := range results {
    id := result.GetId()
    score := result.GetScore()  // Always 0 (binary match)
    metadata := result.Node.Metadata()

fmt.Printf("ID: %d\n", id)
    fmt.Printf("Category: %v\n", metadata["category"])
    fmt.Printf("Price: %v\n", metadata["price"])
}
```

**Supported Data Types:**

```
Supported field types:
├─ string:   Equality only (Eq)
├─ int/int64: All comparisons (Eq, Lt, Lte, Gt, Gte, Between)
├─ float32/float64: All comparisons
├─ bool:     Equality only (Eq)
└─ nil:      Equality only (Eq)
```

### Hybrid Search (HybridSearch Interface)

**Creating a Search:**

```go
search := hybridIndex.NewSearch()  // HybridSearchIndex
```

**Methods:**

| Method            | Parameters             | Description                                                          |
| ----------------- | ---------------------- | -------------------------------------------------------------------- |
| `WithVectorQuery` | `queries ...[]float32` | Semantic search queries (vector embeddings)                          |
| `WithTextQuery`   | `query string`         | Keyword search query (BM25)                                          |
| `WithFilters`     | `filters ...Filter`    | Metadata filters (pre-filtering before search)                       |
| `WithK`           | `k int`                | Number of results to return per modality before fusion               |
| `WithFusion`      | `fusion FusionKind`    | Score fusion strategy: `ReciprocalRankFusion` or `WeightedSumFusion` |
| `WithDocumentIDs` | `ids ...uint32`        | Pre-filter: only search within these document IDs                    |
| `WithAutocut`     | `enabled bool`         | Automatically determine optimal cutoff point                         |
| `Execute`         | -                      | Run hybrid search, returns `[]HybridResult, error`                   |

**Fusion Strategies:**

| Strategy               | Description                                | When to Use                                                   |
| ---------------------- | ------------------------------------------ | ------------------------------------------------------------- |
| `ReciprocalRankFusion` | Rank-based fusion: `score = Σ(1/(k+rank))` | Default, works without tuning, handles different score scales |
| `WeightedSumFusion`    | Linear combination of normalized scores    | When you want to weight modalities differently                |

**Examples:**

```go
// All three modalities
results, err := hybridIndex.NewSearch().
    WithVectorQuery(queryEmbedding).
    WithTextQuery("machine learning").
    WithFilters(
        comet.Eq("category", "ai"),
        comet.Gte("year", 2020),
    ).
    WithK(20).
    WithFusion(comet.ReciprocalRankFusion).
    Execute()

// Vector + Text only (no metadata filters)
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(queryEmbedding).
    WithTextQuery("neural networks").
    WithK(10).
    Execute()

// Vector + Metadata only (no text)
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(queryEmbedding).
    WithFilters(
        comet.Eq("category", "research"),
        comet.Lte("price", 0),  // Free papers
    ).
    WithK(15).
    Execute()

// Multi-query vector search with text
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(embedding1, embedding2, embedding3).
    WithTextQuery("deep learning transformers").
    WithK(20).
    WithFusion(comet.ReciprocalRankFusion).
    Execute()

// Pre-filtered hybrid search
eligibleIDs := []uint32{1, 5, 10, 15, 20}
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(queryEmbedding).
    WithTextQuery("optimization").
    WithDocumentIDs(eligibleIDs...).
    WithK(5).
    Execute()

// With autocut
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(queryEmbedding).
    WithTextQuery("information retrieval").
    WithK(50).
    WithAutocut(true).
    Execute()
```

**Result Format:**

```go
type HybridResult struct {
    ID          uint32   // Document ID
    FusedScore  float32  // Combined score from all modalities
    VectorScore float32  // Individual vector similarity score
    TextScore   float32  // Individual BM25 score
}

// Access results
for _, result := range results {
    fmt.Printf("ID: %d\n", result.ID)
    fmt.Printf("Fused Score: %.4f\n", result.FusedScore)
    fmt.Printf("Vector: %.4f, Text: %.4f\n",
        result.VectorScore, result.TextScore)
}
```

**How Fusion Works:**

```
Reciprocal Rank Fusion (RRF):
┌──────────────────────────────────────┐
│ Step 1: Get results from each modality
│   Vector: [id=1, id=5, id=7, ...]
│   Text:   [id=7, id=1, id=12, ...]
│
│ Step 2: Compute RRF score per document
│   RRF(doc) = Σ 1/(k + rank_i)
│   where k=60 (default), rank_i is rank in modality i
│
│ Example for doc_id=1:
│   Vector rank: 1 → 1/(60+1) = 0.0164
│   Text rank:   2 → 1/(60+2) = 0.0161
│   RRF score:       0.0164 + 0.0161 = 0.0325
│
│ Step 3: Sort by RRF score (higher = better)
└──────────────────────────────────────┘

Benefits:
├─ No score normalization needed
├─ Robust to different score scales
├─ Emphasizes top-ranked results
└─ Works out-of-the-box (no tuning)
```

**Search Flow:**

```
Hybrid Search Execution:
┌───────────────────────────────────────────┐
│ 1. Metadata Filtering (if filters present)│
│    → Get eligible document IDs            │
└────────────┬──────────────────────────────┘
             │
      ┌──────┴──────┐
      │             │
┌─────▼─────┐ ┌─────▼─────┐
│  Vector   │ │   Text    │
│  Search   │ │  Search   │
│ (top-K)   │ │ (top-K)   │
└─────┬─────┘ └─────┬─────┘
      │             │
      └──────┬──────┘
             │
       ┌─────▼─────┐
       │   Fusion  │
       │ (RRF/WS)  │
       └─────┬─────┘
             │
       ┌─────▼─────┐
       │  Results  │
       │ (sorted)  │
       └───────────┘
```

**Use Case Examples:**

```go
// E-commerce: "Show me red dresses under $100 similar to this image"
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(imageEmbedding).
    WithTextQuery("red dress").
    WithFilters(
        comet.Eq("category", "dresses"),
        comet.Lte("price", 100),
        comet.Eq("in_stock", true),
    ).
    WithK(20).
    Execute()

// Academic search: "Papers about 'attention mechanisms' similar to this abstract, published after 2020"
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(abstractEmbedding).
    WithTextQuery("attention mechanisms transformers").
    WithFilters(
        comet.Gte("year", 2020),
        comet.Eq("peer_reviewed", true),
    ).
    WithK(50).
    Execute()

// Job search: "Backend engineer roles in San Francisco paying over $150k"
results, _ := hybridIndex.NewSearch().
    WithVectorQuery(resumeEmbedding).
    WithTextQuery("backend engineer golang kubernetes").
    WithFilters(
        comet.Eq("location", "San Francisco"),
        comet.Gte("salary", 150000),
        comet.Eq("remote", false),
    ).
    WithK(30).
    Execute()
```

## Persistent Storage

Comet provides a durable, scalable storage layer that persists your hybrid search index to disk using an LSM-tree inspired architecture. This enables datasets larger than RAM while maintaining fast in-memory writes.

### Architecture Overview

```
┌─────────────────────────────────────────────────────────────────┐
│                        STORAGE LAYERS                            │
└─────────────────────────────────────────────────────────────────┘

MEMORY (Fast, Volatile)
    ┌──────────────────────────────────────────────────┐
    │  Active Memtable (Mutable)                       │
    │  • Size: 0-100MB                                 │
    │  • Accepts all writes                            │
    │  • Always searched first                         │
    └──────────────────┬───────────────────────────────┘
                       │ (fills up)
    ┌──────────────────▼───────────────────────────────┐
    │  Frozen Memtables (Immutable Queue)              │
    │  • Size: 0-200MB total                           │
    │  • Waiting to be flushed                         │
    └──────────────────┬───────────────────────────────┘
                       │ (background flush)
                       ▼
                    DISK (Durable, Larger)
    ┌──────────────────────────────────────────────────┐
    │  Segments (Compressed, Immutable)                │
    │  • 20-40MB each (gzip compressed)                │
    │  • Lazy-loaded and cached                        │
    │  • Searched in parallel                          │
    └──────────────────┬───────────────────────────────┘
                       │ (background compaction)
                       ▼
    ┌──────────────────────────────────────────────────┐
    │  Compacted Segments (Larger, fewer files)        │
    │  • 100-500MB each                                │
    │  • Merged from multiple segments                 │
    │  • Deleted docs removed                          │
    └──────────────────────────────────────────────────┘
```

### What Are Segments?

**Segments** are immutable, compressed snapshots of your data on disk. Each segment contains:

```
Segment #000001
├── hybrid_000001.bin.gz    → Document IDs and metadata
├── vector_000001.bin.gz    → Vector index (HNSW/IVF/etc.)
├── text_000001.bin.gz      → BM25 inverted index
└── metadata_000001.bin.gz  → Roaring bitmap index
```

**Key Properties:**

- **Immutable**: Once written, never modified
- **Compressed**: gzip level 9 (~75% reduction)
- **Lazy-loaded**: Only loaded from disk when needed
- **Cached**: Stays in memory after first access

### How Searches Work

Searches scan all data sources from newest to oldest, then merge results:

```
┌─────────────────────────────────────────────────────────────┐
│                      SEARCH FLOW                             │
└─────────────────────────────────────────────────────────────┘

Query: WithVector(v).WithText("query").WithK(10)
  │
  ├─→ 1. Search Active Memtable (in-memory, newest)
  │   └─→ Results: [doc_100: 0.95, doc_99: 0.89]
  │
  ├─→ 2. Search Frozen Memtables (in-memory, pending flush)
  │   └─→ Results: [doc_95: 0.92, doc_90: 0.88]
  │
  ├─→ 3. Search Segments (on disk, parallel)
  │   ┌──────────┐  ┌──────────┐  ┌──────────┐
  │   │Segment 1 │  │Segment 2 │  │Segment 3 │
  │   └────┬─────┘  └────┬─────┘  └────┬─────┘
  │        └─────────────┴─────────────┘
  │        └─→ Results: [doc_80: 0.91, doc_50: 0.86]
  │
  ├─→ 4. Merge & Deduplicate (keep highest score per ID)
  │   └─→ Combined: [100, 95, 80, 99, 90, ...]
  │
  └─→ 5. Sort & Limit
      └─→ Top-10: [100: 0.95, 95: 0.92, 80: 0.91, ...]
```

**Performance Characteristics:**

| Component       | Speed     | Data Freshness     |
| --------------- | --------- | ------------------ |
| Active Memtable | Very Fast | Real-time (newest) |
| Frozen Memtable | Very Fast | Recent (pending)   |
| Segments (few)  | Fast      | Historical         |
| Segments (many) | Slower    | Historical         |

_More segments = slower searches. This is why compaction is important!_

### How Writes Work

Writes always go to the active memtable for fast performance:

```
┌─────────────────────────────────────────────────────────────┐
│                      WRITE FLOW                              │
└─────────────────────────────────────────────────────────────┘

Add(vector, text, metadata)
  │
  ├─→ 1. Add to Active Memtable
  │      • Check space available
  │      • If full → rotate to new memtable
  │      • Add document
  │      • Return immediately ✓
  │
  ├─→ 2. Check Flush Threshold
  │      Total memtable size ≥ 200MB?
  │      • Yes → Schedule background flush
  │      • No  → Continue
  │
  └─→ [Write complete - returned to caller]

Meanwhile, in background:
  │
  └─→ Background Flush Worker
      • Freeze memtables
      • Serialize to bytes
      • Compress with gzip
      • Write to disk as segment
```

**Memtable Rotation:**

```
BEFORE Rotation:
┌──────────────────────────────────────────┐
│  Active Memtable (100MB / 100MB) FULL!  │
└──────────────────────────────────────────┘

AFTER Rotation:
┌──────────────────────────────────────────┐
│  Frozen Memtable (100MB) ← Queued flush  │
├──────────────────────────────────────────┤
│  Active Memtable (0MB)   ← Ready writes  │
└──────────────────────────────────────────┘
```

### How Compaction Works

Compaction merges multiple small segments into fewer larger ones:

```
┌─────────────────────────────────────────────────────────────┐
│                   COMPACTION FLOW                            │
└─────────────────────────────────────────────────────────────┘

BEFORE Compaction:
┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐
│Segment 1 │  │Segment 2 │  │Segment 3 │  │Segment 4 │  │Segment 5 │
│ 1K docs  │  │ 1K docs  │  │ 1K docs  │  │ 1K docs  │  │ 1K docs  │
│  25MB    │  │  25MB    │  │  25MB    │  │  25MB    │  │  25MB    │
└──────────┘  └──────────┘  └──────────┘  └──────────┘  └──────────┘

Total: 5 segments, 5,000 docs, 125MB
Search: 5 parallel searches + merge (slower)

↓ Compaction

AFTER Compaction:
┌───────────────────────────┐
│    Merged Segment #006    │
│       4,500 docs          │
│         95MB              │
│  (500 deleted docs gone)  │
└───────────────────────────┘

Total: 1 segment, 4,500 docs, 95MB
Search: 1 search (faster!)
Space saved: 30MB reclaimed
```

**Benefits:**

- ✓ Fewer segments → faster searches
- ✓ Deleted documents removed
- ✓ Disk space reclaimed
- ✓ Better I/O patterns

### Basic Usage

```go
import "github.com/wizenheimer/comet"

// Configure storage
config := comet.DefaultStorageConfig("./data")
config.VectorIndexTemplate, _ = comet.NewFlatIndex(384, comet.Cosine)
config.TextIndexTemplate = comet.NewBM25SearchIndex()
config.MetadataIndexTemplate = comet.NewRoaringMetadataIndex()

// Open persistent storage
store, err := comet.OpenPersistentHybridIndex(config)
if err != nil {
    log.Fatal(err)
}
defer store.Close()

// Add documents (same API as in-memory)
id, _ := store.Add(vector, "document text", metadata)

// Search (same API as in-memory)
results, _ := store.NewSearch().
    WithVector(queryVector).
    WithText("search terms").
    WithK(10).
    Execute()

// Force flush to disk
store.Flush()

// Trigger compaction manually
store.TriggerCompaction()
```

### Configuration Options

```go
config := &comet.StorageConfig{
    BaseDir:             "./data",
    MemtableSizeLimit:   100 * 1024 * 1024,  // 100MB per memtable
    FlushThreshold:      200 * 1024 * 1024,  // Flush at 200MB total
    CompactionInterval:  5 * time.Minute,    // Check every 5 min
    CompactionThreshold: 5,                  // Compact when ≥5 segments
}
```

### When to Use Persistent Storage

**Use persistent storage when:**

- ✓ Your index needs to survive restarts
- ✓ Dataset size exceeds available RAM
- ✓ You need write durability
- ✓ You want automatic compaction

**Use in-memory when:**

- ✓ Dataset fits comfortably in RAM
- ✓ Maximum search speed is critical
- ✓ Data is ephemeral or frequently rebuilt
- ✓ Simplicity over durability

### Important Notes

**Eventually Consistent Deletes:**

```
Remove(docID)
  ├─→ Removed from active memtable: ✓ Immediate
  ├─→ Still in frozen memtables:    ✗ Until flushed
  └─→ Still in segments:            ✗ Until compacted

Timeline:
  T0: Delete called
  T1: Removed from active ✓
  T2: Still found in old data ✗
  T3: Compaction runs
  T4: Completely removed ✓
```

**Crash Recovery:**

- Segments on disk survive crashes ✓
- Active/frozen memtables lost (no WAL yet) ✗
- Always call `Close()` for graceful shutdown

**Monitoring:**

```go
// Check segment count
segmentCount := store.segmentManager.Count()

// Check disk usage
diskUsage := store.segmentManager.TotalSize()

// Check memtable queue depth
queueDepth := store.memtableQueue.Count()

// Evict segment caches (memory pressure)
store.segmentManager.EvictAllCaches()
```

### File Structure

```
data/
├── LOCK                      # Process lock file
├── hybrid_000001.bin.gz      # Segment 1 files
├── vector_000001.bin.gz
├── text_000001.bin.gz
├── metadata_000001.bin.gz
├── hybrid_000002.bin.gz      # Segment 2 files
├── vector_000002.bin.gz
├── text_000002.bin.gz
└── metadata_000002.bin.gz
```

For complete documentation, see [docs/PERSISTENCE.md](docs/PERSISTENCE.md).

## Use Cases

### Use Case 1: Semantic Document Search

**Problem:** A documentation platform needs to find relevant documents based on user queries, going beyond simple keyword matching to understand intent.

**Solution:** Use Comet's vector search with text embeddings from a sentence transformer model.

**Implementation:**

```go
package main

import (
    "github.com/wizenheimer/comet"
    "log"
)

type Document struct {
    ID       uint32
    Title    string
    Content  string
    Embedding []float32  // From sentence-transformers
}

func main() {
    // Create HNSW vector store for 384-dim embeddings
    m, efC, efS := comet.DefaultHNSWConfig()
    index, _ := comet.NewHNSWIndex(384, comet.Cosine, m, efC, efS)

// Add documents (embeddings generated by your ML model)
    docs := []Document{
        {Title: "Getting Started", Embedding: getEmbedding("getting started guide")},
        {Title: "API Reference", Embedding: getEmbedding("api documentation")},
        {Title: "Troubleshooting", Embedding: getEmbedding("common problems and solutions")},
    }

for _, doc := range docs {
        node := comet.NewVectorNode(doc.Embedding)
        index.Add(*node)
    }

// Search with user query
    queryEmbedding := getEmbedding("how do I start using this?")
    results, _ := index.NewSearch().
        WithQuery(queryEmbedding).
        WithK(5).
        Execute()

// Return relevant documents
    for _, result := range results {
        log.Printf("Found: %s (similarity: %.4f)",
            docs[result.GetId()].Title, 1-result.GetScore())
    }
}

func getEmbedding(text string) []float32 {
    // Call your embedding model API (OpenAI, Cohere, local model, etc.)
    return nil  // Placeholder
}
```

### Use Case 2: E-commerce Product Recommendations

**Problem:** Recommend similar products based on browsing history, with filtering by price, category, and availability.

**Solution:** Hybrid search combining product embeddings with metadata filters.

**Implementation:**

```go
type Product struct {
    ID          uint32
    Name        string
    ImageVector []float32  // From image embedding model
    Price       float64
    Category    string
    InStock     bool
}

func RecommendSimilarProducts(
    productID uint32,
    maxPrice float64,
    category string,
) ([]Product, error) {
    // Setup hybrid store
    vecIdx, _ := comet.NewHNSWIndex(512, comet.Cosine, 16, 200, 200)
    metaIdx := comet.NewRoaringMetadataIndex()
    hybrid := comet.NewHybridSearchIndex(vecIdx, nil, metaIdx)

// Get the product's embedding
    product := getProduct(productID)

// Search with filters
    results, err := hybrid.NewSearch().
        WithVector(product.ImageVector).
        WithMetadata(
            comet.Eq("category", category),
            comet.Lte("price", maxPrice),
            comet.Eq("in_stock", true),
        ).
        WithK(10).
        Execute()

if err != nil {
        return nil, err
    }

// Convert to Product structs
    products := make([]Product, len(results))
    for i, result := range results {
        products[i] = getProduct(result.ID)
    }

return products, nil
}
```

### Use Case 3: Question-Answering System with Hybrid Retrieval

**Problem:** Build a QA system that combines semantic understanding (vector search) with keyword precision (BM25) for better answer retrieval.

**Solution:** Use RRF fusion to combine both modalities.

**Implementation:**

```go
func AnswerQuestion(question string) ([]string, error) {
    // Create hybrid store
    vecIdx, _ := comet.NewFlatIndex(768, comet.Cosine)  // BERT embeddings
    txtIdx := comet.NewBM25SearchIndex()
    hybrid := comet.NewHybridSearchIndex(vecIdx, txtIdx, nil)

// Index knowledge base
    for _, doc := range knowledgeBase {
        embedding := getBERTEmbedding(doc.Text)
        hybrid.Add(embedding, doc.Text, nil)
    }

// Search with both modalities
    questionEmbedding := getBERTEmbedding(question)
    results, err := hybrid.NewSearch().
        WithVector(questionEmbedding).        // Semantic similarity
        WithText(question).                    // Keyword matching
        WithFusionKind(comet.ReciprocalRankFusion).  // Combine rankings
        WithK(5).
        Execute()

if err != nil {
        return nil, err
    }

// Extract answer passages
    answers := make([]string, len(results))
    for i, result := range results {
        answers[i] = knowledgeBase[result.ID].Text
    }

return answers, nil
}
```

## Contributing

Contributions are welcome! Please follow these guidelines:

### Development Setup

```bash
# Clone repository
git clone https://github.com/wizenheimer/comet.git
cd comet

# Install dependencies
make deps

# Run tests
make test

# Run linter
make lint

# Check everything
make check
```

### Code Style

- Follow standard Go conventions (`gofmt`, `go vet`)
- Write descriptive comments for exported functions
- Include examples in documentation comments
- Add tests for new features (maintain >95% coverage)
- Keep functions focused and composable
- Use meaningful variable names

### Commit Messages

Follow conventional commits format:

**Good commit messages:**

- `feat: Add IVF index with k-means clustering`
- `fix: Handle zero vectors in cosine distance`
- `perf: Optimize HNSW search with heap pooling`
- `docs: Update API reference for hybrid search`
- `test: Add benchmarks for BM25 search`

**Bad commit messages:**

- `Update code`
- `Fix bug`
- `WIP`
- `asdf`

### Pull Request Process

1. **Fork the repository** and create a feature branch
2. **Write your code** following the style guidelines
3. **Add tests** for all new functionality
4. **Run the full test suite** and ensure all tests pass
5. **Update documentation** (README, godoc comments)
6. **Commit with descriptive messages** using conventional commits
7. **Push to your fork** and open a Pull Request
8. **Respond to review feedback** promptly

### Code Review Checklist

Before submitting a PR, ensure:

- [ ] All tests pass (`make test`)
- [ ] Linter shows no issues (`make lint`)
- [ ] Coverage remains >95% (`make test-coverage`)
- [ ] Documentation is updated
- [ ] Benchmarks show no regression (if applicable)
- [ ] No breaking changes (unless discussed)

## License

MIT License - see LICENSE file for details

## References

- **HNSW Algorithm**: [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://arxiv.org/abs/1603.09320)
- **Product Quantization**: [Product quantization for nearest neighbor search](https://ieeexplore.ieee.org/document/5432202)
- **BM25 Ranking**: [The Probabilistic Relevance Framework: BM25 and Beyond](https://www.staff.city.ac.uk/~sbrp622/papers/foundations_bm25_review.pdf)
- **Roaring Bitmaps**: [Better bitmap performance with Roaring bitmaps](https://arxiv.org/abs/1603.06549)
- **Reciprocal Rank Fusion**: [Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods](https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf)

comet

File Explorer

Today's picks

Was this content helpful?

Recent Feedback

comet

File Explorer

Today's picks

Was this content helpful?

Recent Feedback

Download README