iqdb-flat 1.0.0

Brute-force exact nearest-neighbor search and recall ground truth - part of the iQDB family.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

<h1 align="center">
    <img width="99" alt="Rust logo" src="https://raw.githubusercontent.com/jamesgober/rust-collection/72baabd71f00e14aa9184efcb16fa3deddda3a0a/assets/rust-logo.svg">
    <br>
    <b>iqdb-flat</b>
    <br>
    <sub><sup>iQDB FLAT (EXACT) INDEX</sup></sub>
</h1>

<div align="center">
    <a href="https://crates.io/crates/iqdb-flat"><img alt="Crates.io" src="https://img.shields.io/crates/v/iqdb-flat"></a>
    <a href="https://crates.io/crates/iqdb-flat"><img alt="Downloads" src="https://img.shields.io/crates/d/iqdb-flat?color=%230099ff"></a>
    <a href="https://docs.rs/iqdb-flat"><img alt="docs.rs" src="https://img.shields.io/docsrs/iqdb-flat"></a>
    <a href="https://github.com/jamesgober/iqdb-flat/actions"><img alt="CI" src="https://github.com/jamesgober/iqdb-flat/actions/workflows/ci.yml/badge.svg"></a>
    <a href="https://github.com/rust-lang/rfcs/blob/master/text/2495-min-rust-version.md"><img alt="MSRV" src="https://img.shields.io/badge/MSRV-1.87%2B-blue"></a>
</div>

<br>

<div align="left">
    <p>
        <strong>iqdb-flat</strong> is brute-force exact nearest-neighbor search: the simplest possible index and the ground truth for every recall benchmark. It is built to be fast enough to be a real choice for small datasets, not just a reference.
    </p>
    <p>
        It is the first and simplest consumer of the `Index` trait, so it doubles as the trait's design validation.
    </p>
    <br>
    <hr>
    <p>
        <strong>MSRV is 1.87+</strong> (Rust 2024 edition). Exact, correct, and the recall ground truth. Fast for small data.
    </p>
    <blockquote>
        <strong>Status: stable (1.0).</strong> The full index — exact search, top-<code>k</code>, the <code>Index</code> trait, optional parallel scans, and metadata pre-filtering — is committed under the SemVer 1.x guarantee: no breaking changes until 2.0. See <a href="./CHANGELOG.md"><code>CHANGELOG.md</code></a>.
    </blockquote>
</div>

<hr>
<br>

<h2>What it does</h2>

- **Exact search** &mdash; scans every vector, computes the true distance, returns the top-`k`; always correct, never approximate
- **Ground truth** &mdash; the reference every approximate index (HNSW, IVF) is measured against via recall@k
- **Deterministic** &mdash; one *smaller-is-nearer* ordering across all five metrics, with a stable insertion-order tiebreaker and NaN-safe selection
- **Fast where it counts** &mdash; SIMD distance via `iqdb-distance`, a bounded-heap `O(n log k)` top-`k`, amortized `O(1)` insert/delete, and an optional rayon parallel scan
- **Right for small data** &mdash; the obvious choice under ~10k vectors, where graph or partition overhead is not justified

<br>

## Installation

```toml
[dependencies]
iqdb-flat = "1.0"

# Optional rayon-backed parallel scan for large in-memory corpora:
# iqdb-flat = { version = "1.0", features = ["parallel"] }
```

<br>

## Quick Start

```rust
use std::sync::Arc;

use iqdb_flat::{FlatConfig, FlatIndex};
use iqdb_index::{Index, IndexCore};
use iqdb_types::{DistanceMetric, SearchParams, VectorId};

fn main() -> iqdb_types::Result<()> {
    // A 2-D Euclidean index. `FlatConfig` is a unit struct — nothing to tune.
    let mut idx = FlatIndex::new(2, DistanceMetric::Euclidean, FlatConfig)?;

    idx.insert(VectorId::from(1u64), Arc::<[f32]>::from(&[0.0, 0.0][..]), None)?;
    idx.insert(VectorId::from(2u64), Arc::<[f32]>::from(&[3.0, 4.0][..]), None)?;
    idx.insert(VectorId::from(3u64), Arc::<[f32]>::from(&[1.0, 0.0][..]), None)?;

    let hits = idx.search(&[0.0, 0.0], &SearchParams::new(2, DistanceMetric::Euclidean))?;

    assert_eq!(hits.len(), 2);
    assert_eq!(hits[0].id, VectorId::U64(1)); // distance 0.0
    assert_eq!(hits[1].id, VectorId::U64(3)); // distance 1.0
    Ok(())
}
```

Filtered search restricts the scan to rows whose metadata matches, evaluated
before distance work so a selective filter skips proportionally:

```rust
# use iqdb_flat::{FlatConfig, FlatIndex};
# use iqdb_index::{Index, IndexCore};
use iqdb_types::{DistanceMetric, Filter, SearchParams, Value};

# fn demo(idx: &FlatIndex) -> iqdb_types::Result<()> {
let params = SearchParams {
    filter: Some(Filter::eq("lang", Value::String("rust".into()))),
    ..SearchParams::new(10, DistanceMetric::Euclidean)
};
let hits = idx.search(&[0.0, 0.0], &params)?;
# Ok(())
# }
```

The complete surface — every method, parameter, error, and more examples — is in
[`docs/API.md`](./docs/API.md).

<br>

## Performance

- **Distance** is delegated to [`iqdb-distance`](https://crates.io/crates/iqdb-distance), which dispatches to SIMD kernels (AVX2/NEON) where the target allows; flat never reimplements a metric.
- **Top-`k`** uses a bounded max-heap of size `k` keyed by `(distance, sequence)` — `O(n log k)`, NaN-safe via `f32::total_cmp`.
- **Insert / delete** are amortized `O(1)`: a `HashMap` id→position map for duplicate checks, `swap_remove` for deletion, and a monotonic sequence stamp so reordering never disturbs the tiebreaker.
- **No-filter search** allocates a fixed number of buffers independent of corpus size (locked in by `tests/no_alloc.rs`).
- **`parallel` feature** adds a rayon chunked scan that is **byte-identical** to the sequential baseline (`tests/parallel_equivalence.rs`); small corpora short-circuit to sequential.

<br>

## Status

`v1.0.0` is **stable**: exact search, top-`k`, the full `Index` / `IndexCore`
trait implementation, the optional `parallel` scan, and metadata pre-filtering
are all committed under the SemVer 1.x guarantee — no breaking changes until 2.0.
The surface is covered by unit, property, differential, and scale tests —
including a bit-for-bit large-scan oracle check at N = 20,000 — plus a runnable
<a href="./examples"><code>examples/</code></a> suite, and is recorded in the
<a href="./dev/ROADMAP.md"><code>ROADMAP</code></a>. Only additive, non-breaking
changes are made within 1.x.

<hr>
<br>

## Where It Fits

`iqdb-flat` is a Phase-3 index. It builds on:

- `iqdb-types` &mdash; vectors, ids, metadata
- `iqdb-distance` &mdash; the distance kernels
- `iqdb-index` &mdash; implements the `Index` trait
- `iqdb-eval` &mdash; uses it to generate ground truth

It is unblocked once `iqdb-index` exists; no external dependency.

<br>

## Standards

Built to the iQDB Rust standard. See <a href="./REPS.md"><code>REPS.md</code></a> (Rust Efficiency &amp; Performance Standards) and <a href="./dev/DIRECTIVES.md"><code>dev/DIRECTIVES.md</code></a> for the engineering law and the definition of done. Before a PR: `cargo fmt --all`, `cargo clippy --all-targets --all-features -- -D warnings`, and `cargo test --all-features` must be clean.

<br>

<div id="license">
    <h2>License</h2>
    <p>Licensed under either of</p>
    <ul>
        <li><b>Apache License, Version 2.0</b> &mdash; <a href="./LICENSE-APACHE">LICENSE-APACHE</a></li>
        <li><b>MIT License</b> &mdash; <a href="./LICENSE-MIT">LICENSE-MIT</a></li>
    </ul>
    <p>at your option.</p>
</div>

<div align="center">
  <h2></h2>
  <sup>COPYRIGHT <small>&copy;</small> 2026 <strong>JAMES GOBER.</strong></sup>
</div>