PiPNN built a billion-vector search index in under 20 minutes

Type a question into a retrieval-based assistant and a relevant document appears almost instantly. The visible search feels effortless. What stays hidden is the expensive preparatory work: millions or billions of embeddings have to be arranged so the system can locate nearby candidates without checking every item. For changing datasets, the cost of constructing and reconstructing that map can be as consequential as the search itself.[2]

Researchers at the University of Maryland and Google Research have developed PiPNN, a graph-construction method for approximate nearest-neighbour indexing. Maryland highlighted the work on 21 October; the paper was first posted in February and revised in July. It reports a billion-item index built in under 20 minutes, with other tested comparisons reaching 11.6 times Vamana’s construction speed and 12.9 times HNSW’s.[1][2]

Why the index takes time to build

Conventional graph-based ANN systems link points likely to be useful neighbours in a high-dimensional embedding space. At search time, these links make it possible to explore a relatively small fraction of the dataset and still recover good matches. But the fastest search structures are often slow to construct because the builder repeatedly searches a partially completed graph and revises connections. Random-access work and intermediate memory become serious bottlenecks at enormous scale.[1]

PiPNN changes the sequence. It partitions the dataset into overlapping neighbourhoods, performs batches of distance comparisons that suit efficient matrix computation, and streams candidate edges into a procedure called HashPrune. That procedure keeps the number of retained edges bounded while discarding redundant links. In effect, the algorithm spends more time performing regular, high-throughput work and less time wandering through an unfinished graph.[1]

The resulting graphs also have to support fast, accurate searches. The paper reports competitive query throughput and recall—the fraction of true nearest neighbours recovered—alongside its build-time improvements. Construction and retrieval are separate measurements; making the graph quickly is useful only if it remains a good search structure.[1]

The update problem

Maryland quotes one of the researchers' practical concern: an index that takes longer to rebuild than the interval between data changes can never faithfully represent the latest data. For ecommerce inventories, document corpora, recommendation systems and financial or scientific repositories, rapid construction may make fresher retrieval feasible. It may also free resources that would otherwise be occupied by ongoing rebuilds.[2]

Faster rebuilding is especially relevant to large batch updates. A service with occasional changes may still prefer incremental maintenance of its existing graph. PiPNN reduces one cost in the retrieval pipeline; embeddings, permissions and document quality continue to determine what information a search can return.

One server, substantial resources

The billion-scale runs used a Google Cloud c4-highmem-288 instance with 288 virtual CPUs and 2.2 terabytes of DRAM. That is substantial hardware, even though it is a single machine. Across the paper’s benchmark comparisons, average construction speedups were about 6.32 times against Vamana and 10.4 times against HNSW, below the headline maxima.[1][2]

The practical test is how quickly a changing collection can become searchable at the required recall. When a rebuild takes longer than the interval between major updates, the index starts behind. Reducing that preparation time can make fresher retrieval possible before a user asks the next question.

Report an error or suggest a correction