Vector Internals (Deep) — Intensive

The book already taught you what approximate nearest-neighbour (ANN) search is and how to use it: HNSW in Lucene (the layers, the M/efConstruction/efSearch knobs, the .vec/.vex/.vem files), k-NN algorithms (HNSW vs IVF vs PQ at the mapping level), native integration and memory (the JNI boundary, native memory, the circuit breaker), and quantization and disk-ANN (byte/FP16/PQ/BQ, on_disk, compression_level). This masterclass goes one layer deeper than all of them. It is about the algorithms themselves — the exact line-level construction procedure of an HNSW graph, the faiss index-type taxonomy and what train() actually computes, and the arithmetic of scalar, product, and binary quantization — at the depth where you can fix a recall regression, explain why a diversity heuristic beats nearest-M, or read HnswGraphBuilder and faiss::IndexIVFPQ without hand-waving.

We do not re-derive the basics. If you have not read the four chapters above, stop and read them; this chapter assumes every one of them and picks up where they stop being specific. Where they say "the graph is built incrementally," this chapter shows you the random-level draw, the per-layer beam, and the neighbour-pruning loop. Where they say "PQ uses precomputed lookup tables," this chapter writes out the asymmetric distance computation. Where they say "training builds the codebooks," this chapter says exactly which k-means runs over which sample.

After this chapter you can:

• Reproduce the HNSW insertion algorithm from memory: random level assignment, greedy descent from the entry point, the per-layer efConstruction beam, the diversity neighbour-selection heuristic, and the entry-point update — and name the Lucene classes (HnswGraphBuilder, OnHeapHnswGraph, HnswGraphSearcher, IncrementalHnswGraphMerger) that implement each step.
• Place faiss's index types (IndexFlat, IndexHNSWFlat, IndexIVFFlat, IndexIVFPQ) on a precision/memory/speed map and say what train() builds for each.
• Write the SQ / PQ / BQ encode-and-distance math, compute the compression ratio, and explain why each needs (or does not need) a full-precision rescore.
• Read the GPU / remote-build RFCs and say what they change about who pays the graph-build cost.

Note on terminology: the cluster manager (formerly master) coordinates the k-NN model system index (.opensearch-knn-models) for trained IVF/PQ indices and, in the remote-build RFCs, the remote-build component. Graph construction itself is a per-segment, per-shard, single-threaded-per-graph affair; the cluster manager is off-stage for the algorithms below until training and remote build re-introduce it.

Part 1 — HNSW construction, line by line

The Lucene HNSW chapter drew the layered graph and described greedy search. It described construction in one sentence: "find the node's nearest neighbours at each layer, connect to up to M of them, prune back to M." That sentence hides four distinct mechanisms, and every one of them is a place where a real recall or build-time bug can live. We take them in order.

1.1 Random level assignment — the geometric draw

Each inserted node is given a maximum level l once, at insertion, and never changes. The level is drawn from a geometric distribution so that the number of nodes at level l falls off exponentially: roughly N · p^l nodes reach level l, where p = 1/e^{1/mL} and mL = 1/ln(M) is the level-generation normalization constant from the original Malkov–Yashunin paper. Concretely Lucene draws a uniform r ∈ (0,1] and computes:

level = floor( -ln(r) * mL )            where mL = 1 / ln(M)

-ln(r) is an exponential random variable; scaling by mL and flooring yields the geometric level. With M = 16, mL = 1/ln(16) ≈ 0.36, so the probability a node lands above layer 0 is about 1 - e^{-1/mL} = 1 - e^{-ln(16)} = 1 - 1/16 = 0.9375 chance of being only on layer 0 — i.e. ~1 in 16 nodes reach layer 1, ~1 in 256 reach layer 2, and so on. That 1/M thinning per layer is exactly the skip-list-for-geometry property: the top layers are sparse express lanes.

# In an apache/lucene checkout — find the level draw and the normalization constant.
grep -rn "ml\b\|getRandomGraphLevel\|Math.log\|levelOfFirstNode\|randomLevel\|-Math.log" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java

Note: The level is drawn from a deterministic PRNG seeded per builder, so the same vectors in the same order with the same seed produce the same graph. That is what makes Lab VI1's recall numbers reproducible and why a flaky graph test usually means a seed leaked or the insert order changed.

1.2 Insertion = greedy descent + per-layer beam

To insert node q with drawn level l:

1. If q is the first node, it becomes the graph's single entry point at its level; done.
2. Greedy descent (layers above l). Start at the current entry point on the top layer. On each layer above l, run a greedy search (beam width 1): repeatedly move to the neighbour closest to q, until no neighbour improves — a local minimum. Carry that local minimum down as the entry point for the next layer. No edges are added on these layers; they only position the search.
3. Beam search + linking (layers l down to 0). On each layer from min(l, topLevel) down to 0, run a wide search with beam width efConstruction: maintain a candidate priority queue, expand the closest unexpanded candidate, and keep the best-so-far set. The result is up to efConstruction near neighbours of q on that layer. From those, select ≤ M neighbours via the diversity heuristic (§1.3), add bidirectional edges q ↔ neighbour, and for each neighbour whose edge list now exceeds its cap, prune it back with the same heuristic.
4. Entry-point update. If l is greater than the current top level of the graph, q becomes the new entry point.

The beam in step 3 is identical machinery to query-time search — that is the elegant part of HNSW: insertion is a search that also writes edges. Lucene shares the code in HnswGraphSearcher; the builder calls it with efConstruction as the beam width.

flowchart TD
    Start["insert q, drawn level l"] --> First{"first node?"}
    First -->|yes| EP0["q = entry point; done"]
    First -->|no| Desc["greedy descent from entry point<br/>on layers above l (beam=1)"]
    Desc --> Beam["for layer = min(l,top) .. 0:<br/>beam search width=efConstruction"]
    Beam --> Sel["diversity heuristic: pick <= M neighbours"]
    Sel --> Link["add bidirectional edges q <-> n"]
    Link --> Prune["each n over its cap?<br/>re-run heuristic, prune to M"]
    Prune --> Up{"l > current top level?"}
    Up -->|yes| EPnew["q becomes new entry point"]
    Up -->|no| Done["done"]
    EPnew --> Done

# The insertion method and the per-layer search inside the builder:
grep -rn "addGraphNode\|searchLevel\|beamWidth\|graphSearcher\|entryNode\|class HnswGraphBuilder" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java | head -25

1.3 The diversity heuristic — why "nearest-M" is wrong

The single most important detail of HNSW construction is which M of the efConstruction candidates you keep. The naive answer — "the M nearest" — produces a graph that is locally dense but globally poorly connected: all M edges point into the same tight cluster, and the greedy walk gets stuck in local minima because there are no long-range escape edges. Recall collapses on hard queries.

The diversity heuristic (Malkov–Yashunin's SELECT-NEIGHBORS-HEURISTIC) fixes this. Process candidates nearest-first; accept a candidate c only if it is closer to q than it is to any already-accepted neighbour. Formally, accept c iff:

dist(q, c) < dist(c, a)   for every already-accepted neighbour a

The intuition: if some already-chosen a is closer to c than q is, then a already "covers" the direction of c — adding c is redundant, and you would rather spend the edge on a candidate that opens a new direction. The result is a set of M neighbours that are near q and spread around it, giving the greedy walk diverse escape routes.

candidates near q, sorted:  c1 c2 c3 c4 c5 ...
accept c1 (always: first).
c2: is dist(q,c2) < dist(c2,c1)?  if yes accept, else skip (c1 covers it).
c3: < dist(c3,c1) AND < dist(c3,c2)?  accept iff closer to q than to every accepted.
... stop when M accepted (or candidates exhausted).

flowchart LR
    Q(("q")) --- A(("a*"))
    Q --- B(("b*"))
    Q --- C(("c skipped"))
    A -. "a covers c:<br/>dist(c,a) < dist(q,c)" .- C
    classDef kept fill:#d5f5d5,stroke:#2a7
    classDef drop fill:#f5d5d5,stroke:#a22
    class A,B kept
    class C drop

Lucene implements this in the builder's neighbour-selection path. The key predicate is a distance comparison between the candidate and the already-selected neighbours, not just to q:

# The diversity check — the comparison is candidate-vs-selected, not only candidate-vs-q:
grep -rn "diversit\|selectAndLink\|isDiverse\|popToScratch\|NeighborArray\|checkDiverse" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java \
  lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java | head

Warning: A graph built without the diversity heuristic (nearest-M only) can look fine on easy, in-distribution queries and fall off a recall cliff on out-of-distribution or clustered queries. If you ever hand-roll an HNSW builder (as in Lab VI1's stretch goal), the diversity predicate is the line you will get wrong first.

1.4 M, M0, and the per-layer edge caps

The cap on neighbours is M on layers ≥ 1 but M0 = 2·M on layer 0. Layer 0 holds every node and is the layer the final beam search actually traverses, so it gets double the edges for connectivity; the sparse upper layers stay lean. This is why the Lucene chapter's memory estimate uses ~m × 2 ids on layer 0. When you raise the k-NN m parameter you are raising both caps, which is why memory and .vex size grow roughly linearly in m.

1.5 Search recap — descent then the layer-0 beam

Query-time search reuses the same descent + beam, just without writing edges and with efSearch instead of efConstruction (see the Lucene chapter for the picture): greedy descent from the entry point through the sparse layers (beam 1), then a beam of width efSearch on layer 0, returning the best k. The distance-computation count is dominated by the layer-0 beam — ~efSearch · M0 — which is why it is ~O(log N) in N but linear in your efSearch/M choices.

1.6 Merge — the graph is rebuilt, not concatenated

Segments are immutable, so the HNSW graph inside a segment is too. When merges combine segments, node ordinals and edge lists are local to each old segment and cannot be concatenated. Lucene's IncrementalHnswGraphMerger seeds the merged graph from the largest input segment's existing graph (those nodes keep their structure) and re-inserts only the vectors from the smaller segments via the normal HnswGraphBuilder path. This is the dominant cost of a vector merge and the reason force-merging a vector index is expensive — see the Lucene merge section and the storage-engine masterclass for merge mechanics.

grep -rln "IncrementalHnswGraphMerger\|class .*HnswVectorsWriter\|mergeOneField" lucene/core/src/java

1.7 Lucene class map for construction

You build a real graph with these in Lab VI1.

Part 2 — faiss index types

The native-memory chapter showed how the k-NN faiss engine reaches C++ (JNIService → FaissService → index->search(...)). This section is about what C++ object sits behind that opaque long pointer. faiss is a library of index types with a common faiss::Index interface (train, add, search); k-NN selects and configures one from your method mapping. The four that matter for OpenSearch:

2.1 IndexFlat — the exact baseline

IndexFlat stores vectors contiguously and, on search, computes the distance from the query to every vector (SIMD dot-products / L2), keeping the top-k. It is O(N·d) — the brute-force baseline from the Lucene chapter. It needs no training and no graph. You rarely set it as your primary index, but it is everywhere underneath: it is what an exact rescore pass uses, and it is the coarse quantizer inside IVF (the centroid list is itself a tiny IndexFlat you brute-force to find the nearest cells).

2.2 IndexHNSWFlat — HNSW over flat vectors

This is the faiss equivalent of Lucene's HNSW: the same layered graph from Part 1, but built and searched by faiss's C++ (faiss/impl/HNSW.cpp) instead of HnswGraphBuilder. faiss's parameter M is the same M; its efConstruction and efSearch map directly from the k-NN ef_construction / ef_search. The stored vectors are float32 (the "Flat" in the name); swap in a quantizer and you get IndexHNSWSQ / IndexHNSWPQ. It is train-free — like Lucene HNSW, the graph builds incrementally as you add.

# In a k-NN checkout: where the faiss index type/string is assembled from the mapping.
grep -rn "IndexHNSWFlat\|HNSW32\|index_description\|indexDescription\|createIndex\|IDMap" \
  jni/src jni/include 2>/dev/null | head
grep -rn "METHOD_HNSW\|METHOD_IVF\|ENCODER_PQ\|FAISS_NAME\|MethodComponent" \
  src/main/java/org/opensearch/knn/common/KNNConstants.java

2.3 IndexIVFFlat — the inverted file

IVF is covered conceptually in k-NN algorithms § IVF. The faiss object: a coarse quantizer (an IndexFlat of nlist centroids learned by k-means) plus nlist inverted lists (posting lists), one per centroid. train() runs k-means over a sample to learn the centroids; add() assigns each vector to its nearest centroid's list; search() finds the nprobe nearest centroids and scans only those lists. The cell contents in IndexIVFFlat are raw float32.

2.4 IndexIVFPQ — IVF with product-quantized cells

IndexIVFPQ is the classic billion-scale faiss recipe: IVF for partitioning + PQ for compression of the cell contents. train() does two things: k-means for the IVF centroids, and per-subspace k-means for the PQ codebooks (§3.2). add() assigns to a cell and stores the PQ code (not the float32 vector). search() finds nprobe cells and computes asymmetric distances against the PQ codes using precomputed tables. This is the most memory-efficient faiss index and the one that demands rescoring most.

flowchart TD
    subgraph Flat["IndexFlat"]
      F["raw float32, brute-force O(N*d)"]
    end
    subgraph HNSW["IndexHNSWFlat"]
      H["float32 + HNSW graph, ~O(log N), train-free"]
    end
    subgraph IVF["IndexIVFFlat"]
      I["centroids (k-means) + float32 posting lists, nprobe cells"]
    end
    subgraph IVFPQ["IndexIVFPQ"]
      P["centroids + PQ codes + codebooks, ADC distance"]
    end
    Flat -->|add a graph| HNSW
    Flat -->|partition into cells| IVF
    IVF -->|compress cell contents| IVFPQ

2.5 What train() builds — the summary

This is exactly why k-NN's _train API and the .opensearch-knn-models system index exist for IVF/PQ and not for HNSW — see k-NN algorithms § Training. You exercise all four index types through OpenSearch, including the _train flow and the JNI boundary, in Lab VI2.

Part 3 — The quantization math

The quantization chapter gave you the menu (byte/FP16/PQ/BQ/on_disk) and the compression table. This section is the arithmetic — enough that you could implement each quantizer, which is exactly what Lab VI3 makes you do. All three share one shape: encode: vector → compact code, decode: code → approximate vector, and a distance that either reconstructs or works directly on the code. All three are lossy, and all three recover recall by rescoring the shortlist against full precision.

3.1 Scalar quantization (SQ) — per-dimension min/max → int

SQ maps each float component to a small integer by linear rescaling. With per-dimension bounds [min_j, max_j] learned from the data (or global bounds), int8 quantization is:

encode:   q_j   = round( (x_j - min_j) / (max_j - min_j) * (2^bits - 1) )
decode:   x'_j  = min_j + q_j / (2^bits - 1) * (max_j - min_j)
error:    e_j   = |x_j - x'_j|   <=  (max_j - min_j) / (2 * (2^bits - 1))    (half a step)

• int8 (bits = 8, 256 levels): 4× smaller than float32, step size (max-min)/255, error ≤ half a step. Recall loss is typically small for normalized embeddings.
• int4 (bits = 4, 16 levels): 8× smaller, step (max-min)/15 — 16× coarser than int8, recall loss noticeably larger. Always rescore.
• fp16: not min/max SQ but IEEE-754 half — 2×, near-zero loss; the gentlest step (see quantization chapter § FP16).

Per-dimension bounds beat global bounds when dimensions have different scales (common in raw, un-normalized embeddings): a single global [min,max] wastes resolution on narrow-range dimensions. This is the SQ that Lucene's Lucene99ScalarQuantizedVectorsFormat / Lucene104ScalarQuantizedVectorsFormat implement (int7/int8, and configurable 1/2/4/7/8-bit in Lucene104*) and that faiss exposes as the sq encoder. The production pattern: search the int8/int4 graph for a shortlist, then rescore against float32.

3.2 Product quantization (PQ) — codebooks + asymmetric distance

PQ (mechanics in k-NN algorithms § PQ) splits a d-dim vector into m contiguous subvectors of length d/m, and learns a separate codebook of k = 2^nbits centroids (typically nbits = 8 → k = 256) per subspace by running k-means within that subspace over the training sample. Encoding replaces each subvector with the id of its nearest centroid:

split:   x = [ x^(1) | x^(2) | ... | x^(m) ]          each x^(i) has d/m dims
codebook C^(i) = { c^(i)_0 ... c^(i)_{k-1} }          k=256 centroids per subspace, learned by k-means
encode:  code_i = argmin_j  || x^(i) - c^(i)_j ||      one byte per subvector when k=256
store:   m bytes total   (vs d*4 bytes float32)

The clever part is the distance. Asymmetric Distance Computation (ADC) keeps the query in full precision and only the database vectors quantized. For a query y, precompute, once per query, a lookup table per subspace:

LUT_i[j] = || y^(i) - c^(i)_j ||^2          for all j in 0..k-1, for each subspace i

Then the (squared L2) distance from y to any encoded database vector with code (code_1 ... code_m) is a sum of m table lookups — no per-dimension arithmetic, no reconstruction:

dist(y, x_encoded)^2  ≈  sum over i of  LUT_i[ code_i ]

So after an m·k table build per query (e.g. 96 · 256 for m=96, nbits=8), each candidate distance is just m = 96 byte-indexed table reads and an add — extremely cache-friendly and SIMD-able. "Asymmetric" because the query is not quantized; the symmetric variant (SDC) quantizes the query too and is slightly faster to set up but less accurate. faiss and OpenSearch use ADC.

flowchart LR
    subgraph encode["encode (index time)"]
      X["x (d dims)"] --> SP["split into m subvectors"]
      SP --> NN["argmin over 256 centroids per subspace"]
      NN --> CODE["m-byte code"]
    end
    subgraph query["search (per query)"]
      Y["query y"] --> LUT["build LUT_i[j] = ||y^(i) - c^(i)_j||^2"]
      CODE --> SUM["dist^2 = sum_i LUT_i[code_i]"]
      LUT --> SUM
      SUM --> SHORT["shortlist -> float32 rescore"]
    end

PQ at d=768, m=96, nbits=8: 96 bytes vs 3072 → 32×. The recall cost is real (you compare reconstructions), so PQ demands rescoring; it is the most aggressive float-based compression and the only one needing trained codebooks. You implement a tiny PQ — split, k-means codebooks, ADC — in Lab VI3.

3.3 Binary quantization (BQ) — sign bit + Hamming

BQ reduces each component to one bit (commonly the sign, or above/below a per-dimension threshold) and compares vectors with Hamming distance — the popcount of the XOR — which modern CPUs do over 64 bits in one instruction:

encode:  b_j = 1 if x_j > threshold_j else 0          (sign: threshold_j = 0)
store:   d bits = d/8 bytes   (d=768 -> 96 bytes, 32x)
distance: hamming(a, b) = popcount(a XOR b)            number of differing bits

At 1 bit/dim, d=768 → 96 bytes (32×, same footprint as PQ-96×8 but train-free and far cheaper to compare). BQ throws away almost all magnitude information, so its recall loss is the steepest on the menu — it always pairs with rescoring, usually with a larger oversample factor than PQ. Its niche: the cheapest possible first stage of a funnel — Hamming-shortlist a large candidate set, then full-precision rescore. The RaBitQ family improves BQ's accuracy with a randomized rotation before binarizing; the k-NN space_type for binary vectors is hamming.

3.4 The compression-vs-recall-vs-latency table (with the math)

The two big levers are orthogonal: SQ/PQ/BQ is "how small per vector," and the HNSW/IVF structure is "which vectors you compare." They compose — HNSW+SQ, IVF+PQ, HNSW over BQ — and on_disk mode (see disk-ANN) productizes "compressed graph in RAM + float32 on disk + automatic rescore" behind a single compression_level knob.

GPU and remote index build

Quantization shrinks the stored index but not the build cost — constructing an HNSW graph (even over compressed vectors) is CPU-heavy and recurs on every merge. Two active RFCs attack this and are worth reading before touching index-build code:

• GPU-accelerated build — k-NN #2293, [RFC] Boosting OpenSearch Vector Engine Performance using GPUs. NVIDIA cuVS + the CAGRA GPU-native graph-build algorithm construct the index on the GPU in FP32, then serve it on CPU. Graph build is embarrassingly parallel, so a GPU cuts wall-clock build time dramatically.
• Remote vector index build — k-NN #2294, [RFC] Remote Vector Index Build. Offload per-segment graph construction from the data node to a remote GPU/CPU fleet: the data node ships the segment's vectors out, a remote builder constructs the graph, and the result is pulled back and written into the segment.

Neither changes the query path — a remotely- or GPU-built graph queries identically to a locally-built one. They change who pays the build cost and on what hardware. For current status, search rather than assume:

repo:opensearch-project/k-NN is:issue GPU cuVS CAGRA remote build
repo:opensearch-project/k-NN is:issue label:"Roadmap" remote index build

Real grep targets

# --- HNSW construction (apache/lucene checkout) ---
# Level draw + normalization constant (mL = 1/ln(M)):
grep -rn "Math.log\|getRandomGraphLevel\|randomLevel\|ml\b\|levelOfFirstNode" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
# Insertion, descent, beam, linking, pruning:
grep -rn "addGraphNode\|searchLevel\|beamWidth\|entryNode\|popToScratch" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
# The diversity heuristic (candidate-vs-selected comparison):
grep -rn "diversit\|isDiverse\|selectAndLink\|checkDiverse" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/*.java
# Layer-0 cap M0 = 2*M:
grep -rn "M0\|maxConn0\|nodeVersions\|2 \* M\|maxConn" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/*.java
# Merge:
grep -rln "IncrementalHnswGraphMerger" lucene/core/src/java

# --- faiss index types (k-NN checkout) ---
grep -rn "IndexHNSWFlat\|IndexIVFFlat\|IndexIVFPQ\|IndexFlat\|index_description\|createIndex" \
  jni/src jni/include 2>/dev/null
grep -rn "METHOD_HNSW\|METHOD_IVF\|ENCODER_PQ\|ENCODER_SQ\|ENCODER_FLAT\|NLIST\|NPROBE" \
  src/main/java/org/opensearch/knn/common/KNNConstants.java
grep -rln "TrainingJob\|ModelDao\|MODEL_INDEX_NAME\|FaissService\|JNIService" \
  src/main/java/org/opensearch/knn

# --- quantization (k-NN + lucene) ---
grep -rn "fp16\|ENCODER_SQ\|ScalarQuantiz\|code_size\|nbits\|pq\b\|hamming\|popcount" \
  src/main/java/org/opensearch/knn/common/KNNConstants.java
grep -rln "Lucene9.*ScalarQuantizedVectorsFormat\|Lucene10.*ScalarQuantizedVectorsFormat" \
  lucene/core/src/java

Common bugs and symptoms

Validation: prove you understand this

1. Write the geometric level-assignment formula and compute, for M=16, the expected fraction of nodes that reach layer 1 and layer 2. Explain why M0 = 2·M on layer 0.
2. Reproduce the HNSW insertion algorithm end to end for a node with drawn level l=1 in a graph whose top level is 2: name what happens on layers 2, 1, and 0, where efConstruction enters, and when the entry point is updated.
3. State the diversity acceptance predicate exactly, and explain with a 3-candidate example why it produces better recall than keeping the M nearest candidates.
4. For each of IndexFlat, IndexHNSWFlat, IndexIVFFlat, IndexIVFPQ: say what it stores, what train() computes (if anything), and which k-NN mapping builds it.
5. Write the int8 SQ encode/decode and the worst-case per-dimension error. Compute the compression ratio for int4 and explain why it needs rescoring but FP16 usually does not.
6. Write the PQ encode step and the ADC distance with its per-query lookup table. For d=768, m=96, nbits=8, give the code size, the compression ratio, and the per-query table-build and per-candidate distance costs.
7. Explain BQ's encode and distance, why its recall loss is the steepest on the menu, and why it is best used as the first stage of a rescoring funnel.
8. Say what GPU build (#2293) and remote index build (#2294) change about a k-NN deployment — and what they deliberately do not change.

When you can do all eight, build the graph for real in Lab VI1: HNSW Graph Construction, exercise the faiss index types and the JNI boundary in Lab VI2: Faiss Index Types and JNI, and implement the quantizers yourself in Lab VI3: The Quantization Math. For the layers above this one, return to HNSW in Lucene, k-NN algorithms, native integration and memory, and quantization and disk-ANN.