Struct DiskANNIndex 

pub struct DiskANNIndex<DP: DataProvider> {
    pub config: Config,
    pub data_provider: DP,
    /* private fields */
}

Fields

config: Config

Index config

data_provider: DP

The data provider.

Implementations

impl<DP> DiskANNIndex<DP>

where DP: DataProvider,

pub fn new( config: Config, data_provider: DP, thread_hint: Option<NonZeroUsize>, ) -> Self

pub fn provider(&self) -> &DP

pub fn insert<S, T>( &self, strategy: S, context: &DP::Context, id: &DP::ExternalId, vector: T, ) -> impl SendFuture<ANNResult<()>>

where S: InsertStrategy<DP, T>, DP: SetElement<T>, T: Copy + Send,

Insert a vector into the index with the given id and vector.

pub fn multi_insert<S, B>( self: &Arc<Self>, strategy: S, context: &DP::Context, vectors: Arc<B>, ids: Arc<[DP::ExternalId]>, ) -> impl SendFuture<ANNResult<()>>

where Self: 'static, S: MultiInsertStrategy<DP, B>, B: Batch, DP: for<'a> SetElement<B::Element<'a>>,

Insert a small set of vectors into the index. The call parallelizes the search for each vector as well as the subsequent pruning and edge addition.

Each multi_insert makes at most one update (either set or append) per id to the DataProvider. The algorithm resolves conflicting updates to adjacency lists caused by multiple inserts without involving the provider in the resolution.

This method receives self by Arc to allow cloning for parallel task spawns.

• strategy: The InsertStrategy to use for insert searches and prunes.
• context is the context to pass through to providers.
• vectors the vectors and associated ids to insert.

Configuration

Multi-insert specific configuration includes:

1. [diskann::index::Config::max_minibatch_par()]: Control the maximum number of concurrent task spawns used by the implementation. This puts an upper bound on the extracted parallelism of this function.

2. [diskann::index::Config::intra_batch_candidates()]: Controls the maximum number of candidates from within the batch that are considered as neighbors.

   When the batch size is very high or the inserted data has high self similarity, it is recommended to set this a moderate value such as 32 to ensure edges are formed within a batch. However, setting this too high can slow down ingestion for high batch sizes.

   If this is set to zero, then candidates will not be considered among the batch unless the number of unique back edge sources is fewer than eight times the batch size. This helps with initial graph formation when the index is initially empty. The value “8” is a rough heuristic, chosen to trigger frequently during the initial phases of build but rarely again.

Error Handling

The error handling for this function is currently undergoing a revision. Currently, errors encountered during tasks spawns are suppressed. The revision will inform the caller of failed insertions in a more precise manner.

Dev-Docs on Flow

Multi-Insert works in three phases: (1) Set Elements, (2) Candidate Generation, and (3) graph update.

Set Elements

Vectors taken from external sources need to be inserted into the underlying data provider and an internal ID needs to be generated for these items. This phase parallelizes the insertion and collects the internal IDs for the inserted vectors.

Candidate Generation

This is made up of a graph search followed by a prune on the resulting candidate list. If [diskann::index::Config::intra_batch_candidates()] is non-zero, then candidates from within the batch are added at this step prior to prune.

Bootstrap

If no intra-batch candidates are to be used, the optional bootstrap routine (defined in the above section titled “configuration”) is run after the initial candidate generation.

Graph Update

After all candidates have been retrieved, backedges are aggregated and the graph is updated. First with the generated candidates, and second to commit the backedges, triggering secondary prunes if necessary. This phase is partitioned so each parallel task updates a disjoint set of elements.

pub fn is_any_neighbor_deleted<NA>( &self, context: &DP::Context, accessor: &mut NA, vector_id: DP::InternalId, ) -> impl SendFuture<ANNResult<bool>>

where DP: Delete, NA: AsNeighbor<Id = DP::InternalId>,

pub fn drop_adj_list( &self, accessor: &mut impl AsNeighborMut<Id = DP::InternalId>, vector_id: DP::InternalId, ) -> impl SendFuture<ANNResult<()>>

pub fn get_undeleted_neighbors<NA>( &self, context: &DP::Context, accessor: &mut NA, vector_id: DP::InternalId, ) -> impl SendFuture<ANNResult<PartitionedNeighbors<DP::InternalId>>>

where DP: Delete, NA: AsNeighbor<Id = DP::InternalId>,

pub fn return_refs_to_deleted_vertex<NA>( &self, accessor: &mut NA, vector_id: DP::InternalId, candidate_list: &[DP::InternalId], ) -> impl SendFuture<ANNResult<Vec<DP::InternalId>>>

where DP: Delete, NA: AsNeighbor<Id = DP::InternalId>,

Return the list of ids with refs to a particular (deleted) vertex

pub fn multi_inplace_delete<S>( self: &Arc<Self>, strategy: S, context: &DP::Context, ids: Arc<[DP::ExternalId]>, num_to_replace: usize, inplace_delete_method: InplaceDeleteMethod, ) -> impl SendFuture<ANNResult<()>>

where Self: 'static + Send + Sync, S: InplaceDeleteStrategy<DP> + for<'a> SearchStrategy<DP, S::DeleteElement<'a>> + Send + Sync + Clone, DP: Delete + Send + Sync,

pub fn inplace_delete<S>( &self, strategy: S, context: &DP::Context, id: &DP::ExternalId, num_to_replace: usize, inplace_delete_method: InplaceDeleteMethod, ) -> impl SendFuture<ANNResult<()>>

where S: InplaceDeleteStrategy<DP> + Sync + Clone, DP: Delete,

This method deletes a vertex without needing to loop over the entire graph to find its out-neighbors. It is meant to be called in conjunction with [drop_deleted_neighbors] run occasionally as a background process.

See https://arxiv.org/abs/2502.13826 for full description and experiments

pub fn drop_deleted_neighbors<NA>( &self, context: &DP::Context, accessor: &mut NA, vector_id: DP::InternalId, only_orphans: bool, ) -> impl SendFuture<ANNResult<ConsolidateKind>>

where DP: Delete, NA: AsNeighborMut<Id = DP::InternalId>,

Look for deleted nodes in the neighbors of vector_id, and remove them if found This is used in conjunction with inplace deletes If only_orphans is set to true, we check to make sure a node’s adjacency list is empty before removing a link to it. This is in case drop_deleted_neighbors is called with an inplace delete still pending

pub fn consolidate_vector<S>( &self, strategy: &S, context: &DP::Context, vector_id: DP::InternalId, ) -> impl SendFuture<ANNResult<ConsolidateKind>>

where DP: Delete, S: PruneStrategy<DP>,

Consider the neighbors of vector_id, look for deleted nodes and compute replacements for them.

pub fn search<S, T, O, OB, P>( &self, search_params: P, strategy: &S, context: &DP::Context, query: T, output: &mut OB, ) -> impl SendFuture<ANNResult<P::Output>>

where P: Search<DP, S, T>, S: DefaultPostProcessor<DP, T, O>, O: Send, OB: SearchOutputBuffer<O> + Send + ?Sized,

Execute a search using the unified search interface.

This method provides a single entry point for all search types. The search_params argument implements [search::Search], which defines the complete search behavior including algorithm selection and post-processing.

Supported Search Types

• [search::Knn]: Standard k-NN graph-based search
• [search::MultihopSearch]: Label-filtered search with multi-hop expansion
• [search::Range]: Range-based search within a distance radius
• [search::Diverse]: Diversity-aware search (feature-gated)

Example

use diskann::graph::{search::{Knn, Range}, Search};

// Standard k-NN search
let params = Knn::new(10, 100, None)?;
let stats = index.search(params, &strategy, &context, &query, &mut output).await?;

// Range search (results written to output buffer)
let params = Range::new(100, 0.5)?;
let stats = index.search(params, &strategy, &context, &query, &mut output).await?;

pub fn search_with<S, T, O, OB, P, PP>( &self, search_params: P, strategy: &S, processor: PP, context: &DP::Context, query: T, output: &mut OB, ) -> impl SendFuture<ANNResult<P::Output>>

where P: Search<DP, S, T>, S: SearchStrategy<DP, T>, PP: for<'a> SearchPostProcess<S::SearchAccessor<'a>, T, O> + Send + Sync, O: Send, OB: SearchOutputBuffer<O> + Send + ?Sized,

Execute a search with an explicit post-processor parameter.

pub fn paged_search<'a, S, T>( &'a self, strategy: S, context: &'a DP::Context, query: T, l_value: usize, ) -> impl SendFuture<ANNResult<PagedSearch<'a, DP, S, T>>>

where S: SearchStrategy<DP, T>, T: Copy + Send + 'a,

Begin a paged search over the index.

Returns a PagedSearch handle whose next_page method yields successive pages of nearest-neighbor results.

pub fn paged_search_with_init_ids<'a, S, T>( &'a self, strategy: S, context: &'a DP::Context, query: T, l_value: usize, init_ids: Option<&'a [DP::InternalId]>, ) -> impl SendFuture<ANNResult<PagedSearch<'a, DP, S, T>>>

where S: SearchStrategy<DP, T>, T: Copy + Send + 'a,

Begin a paged search with explicit initial seed IDs.

This is the same as paged_search but allows the caller to provide custom starting points for the graph traversal.

pub fn count_reachable_nodes<NA>( &self, start_points: &[DP::InternalId], accessor: &mut NA, ) -> impl SendFuture<ANNResult<usize>>

where NA: AsNeighbor<Id = DP::InternalId>,

Count the number of nodes in the graph reachable from the given start_points.

This function has a large memory footprint for large graphs and should not be called frequently. This is mainly for analysis and sanity tests.

pub fn get_degree_stats<NA, Itr>( &self, accessor: &mut NA, itr: Itr, ) -> impl SendFuture<ANNResult<DegreeStats>>

where Itr: IntoIterator<Item = DP::InternalId, IntoIter: Send> + Send, NA: AsNeighbor<Id = DP::InternalId>,

impl<DP> DiskANNIndex<DP>

where DP: DataProvider,

pub fn prune_range<S>( &self, strategy: &S, context: &DP::Context, range: Range<DP::InternalId>, ) -> impl SendFuture<ANNResult<()>>

where S: PruneStrategy<DP>,

Prune all nodes in the graph.

This is used as the final step of graph construction.

Trait Implementations

impl<DP: Debug + DataProvider> Debug for DiskANNIndex<DP>

where DP::InternalId: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.