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.
Note (2026-11-08): the abstract (Wu et al.) reports, from experiments on six real-world datasets, up to 3.5 times speedup over HNSW's incremental construction and an average 7.9 times speedup for methods without incremental support, with search performance comparable or superior; the essay drops 'up to' for the first figure and says the merged graph has the same quality as one built all at once, which the abstract does not claim.
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.