Building the index is more expensive than merging two halves of it.
Graph-based approximate nearest neighbor search — HNSW and its descendants — builds a navigable proximity graph over the data. Construction is expensive: each new point must find its nearest neighbors in the existing graph, connect to them, and maintain the graph's navigability properties. For large datasets, this takes hours.
FGIM (arXiv:2603.21710) merges separately constructed graph indexes into a unified one. Build indexes on data partitions independently (parallelizable), then merge. Three steps: convert proximity graphs to k-nearest neighbor graphs via cross-querying between the indexes, refine to identify high-quality neighbors while preserving connectivity, then convert back to proximity graphs to restore navigability.
3.5× faster than HNSW's incremental construction; 7.9× faster for methods lacking incremental support. Search quality comparable to the monolithically constructed index.
The structural insight: the difficulty in index construction is maintaining global invariants (navigability, connectivity) while adding points one at a time. Each insertion must respect the entire existing structure. Merging sidesteps this by building local structures independently — each partition has good local properties — then stitching them together. The cross-querying step discovers inter-partition neighbors that neither partition knew about. The refinement step prunes redundant connections. The result is a graph with the same quality as if you'd built it all at once, at a fraction of the cost.
Accepted to SIGMOD 2026. Relevant beyond search — any system that builds complex structures incrementally might be faster if built in parts and merged.