obikmer/UserDocMD/formats/index_layout.md

# Index construction and on-disk layout

## Construction pipeline

Building an index ([`index`](../usage/index_command.md)) proceeds through a fixed sequence of phases, each operating independently per partition (see [Partitioning and indexing architecture](../theory/indexing_architecture.md)):

1. **Scatter.** A single streaming pass over the input. Each sequence fragment is cut at non-ACGT bases, passed through the low-complexity entropy filter (see [Low-complexity kmer filter](../theory/entropy_filter.md)), and any resulting segment shorter than k is dropped. Surviving segments are decomposed into super-kmers, canonicalized, and routed by `hash(minimizer) mod n_partitions` into one file per partition.
2. **Dereplication.** Within each partition, identical super-kmer sequences are merged and their occurrence counts summed. This count is per super-kmer, not per kmer — a kmer's true abundance is the sum of the counts of every super-kmer containing it.
3. **Exact counting.** Every kmer in every dereplicated super-kmer is enumerated and its exact total count computed. A per-genome kmer frequency spectrum is produced at this stage.
4. **Quorum filtering.** Kmers outside the `--min-abundance`/`--max-abundance` range are dropped, and super-kmers are recompacted around the surviving kmer set.
5. **Local assembly.** The surviving kmers of each partition are assembled into unitigs — maximal non-branching runs of a local de Bruijn graph — such that every kmer appears exactly once, at one (unitig, offset) location.
6. **MPHF and evidence construction.** A minimal perfect hash function is built over the canonical kmers of each partition, together with the evidence structure needed to verify that a queried kmer was genuinely indexed (see below). Per-genome counts or presence bits are recorded alongside if requested.

Phases 1–5 are independent per partition and run in parallel; phase 6 finalizes each partition once its kmer set is fixed.

## Minimal perfect hash function (MPHF)

Each partition's surviving kmers are mapped to a dense range of integer slots by a minimal perfect hash function: no collisions, near-optimal space (a few bits per key), O(1) lookup. Because an MPHF maps *any* input to some slot — including kmers that were never indexed — a lookup alone cannot distinguish a genuinely indexed kmer from an arbitrary one; every lookup is followed by an evidence check.

## Evidence: exact vs. approximate

Two verification modes are available, selected at build time (`index --approx`) and convertible afterwards ([`reindex`](../usage/reindex.md)):

- **Exact** (default): the hashed slot stores a pointer back into the partition's unitig data. At query time the kmer is reconstructed from that location and compared directly to the query. Zero false positives, at the cost of one extra random read per lookup.
- **Approximate** (`--approx`): the slot stores a short fingerprint (`--evidence-bits` bits) instead of a pointer; verification is a single fingerprint comparison. This trades a small, bounded false-positive rate ($1/2^b$ per kmer, reduced further to about $1/2^{b \cdot z}$ for a read requiring $z$ consecutive matching kmers via the `-z`/`--findere-z` parameter) for lower memory and disk usage, since no reconstruction index is needed. See [`estimate`](../usage/estimate.md) to explore this trade-off before building.

## On-disk layout

```
<index_root>/
  index.meta                    global configuration (k, minimizer size, partition count,
                                 evidence mode, whether counts are stored) and genome list/metadata
  scatter.done / count.done / index.done      build-progress sentinels
  spectrums/<label>.json        per-genome kmer frequency histogram
  partitions/
    part_00000/ ... part_NNNNN/
      index/
        meta.json                number of layers in this partition
        layer_0/
          unitigs.bin             reconstructible kmer sequence data — always kept
          unitigs.bin.idx         random-access index into unitigs.bin (exact evidence only)
          mphf.bin                 the minimal perfect hash function
          evidence.bin              exact evidence (exact mode only)
          fingerprint.bin           approximate evidence (approximate mode only)
          counts/                   per-genome kmer counts (if counts were requested)
          presence/                 per-genome presence/absence bits
        layer_1/, layer_2/, ...     added by later merges, same internal structure
```

`unitigs.bin` is the only file from which the indexed kmer content can be fully recovered; it is always retained. Every other file (MPHF, evidence, counts) is derived from it.

A **layer** corresponds to one increment of kmer content added to a partition — most commonly, one [`merge`](../usage/merge.md) operation that introduces kmers not already present in the index. Genomes already present in the index simply gain new columns in the existing layers' count/presence data; only genuinely new kmer content is assembled into a new layer. Because of this, merging cost scales with the novel kmer content being added, not with the accumulated size of the index. A query against an index with several layers checks each layer's MPHF in turn.

Sources merged together must share the same kmer size, minimizer size, partition count, and evidence mode (including matching approximate-mode parameters); mismatches are rejected rather than silently reconciled — [`reindex`](../usage/reindex.md) one of the sources first if needed.

`obikmer pack` consolidates a partition's per-column files (counts/presence) into a single file, reducing the number of file opens needed at query time.