Package com.apple.foundationdb.async.hnsw

Class Insert

java.lang.Object
com.apple.foundationdb.async.hnsw.Insert
@API(EXPERIMENTAL) public class Insert extends Object
An implementation of the insert operations of the Hierarchical Navigable Small World (HNSW) algorithm for efficient approximate nearest neighbor (ANN) search.

HNSW constructs a multi-layer graph, where each layer is a subset of the one below it. The top layers serve as fast entry points to navigate the graph, while the bottom layer contains all the data points. This structure allows for logarithmic-time complexity for search operations, making it suitable for large-scale, high-dimensional datasets.

The entry point for any interactions with the HNSW data structure is implemented in HNSW. Do not instantiate this class directly.

  • Constructor Details

    • Insert

      public Insert(@Nonnull Locator locator)
      This constructor initializes a new insert operations object with the necessary components for storage, execution, configuration, and event handling.
      Parameters:
      locator - the Locator where the graph data is stored, which config to use, which executor to use, etc.

  • Method Details

    • getLocator

      @Nonnull public Locator getLocator()

    • getSubspace

      @Nonnull public Subspace getSubspace()
      Gets the subspace associated with this object.
      Returns:
      the non-null subspace

    • getExecutor

      @Nonnull public Executor getExecutor()
      Get the executor used by this hnsw.
      Returns:
      executor used when running asynchronous tasks

    • getConfig

      @Nonnull public Config getConfig()
      Get the configuration of this hnsw.
      Returns:
      hnsw configuration

    • getOnWriteListener

      @Nonnull public OnWriteListener getOnWriteListener()
      Get the on-write listener.
      Returns:
      the on-write listener

    • getOnReadListener

      @Nonnull public OnReadListener getOnReadListener()
      Get the on-read listener.
      Returns:
      the on-read listener

    • insert

      @Nonnull public CompletableFuture<Void> insert(@Nonnull Transaction transaction, @Nonnull Tuple newPrimaryKey, @Nonnull RealVector newVector)
      Inserts a new vector with its associated primary key into the HNSW graph.

      The method first determines a layer for the new node, called the top layer. It then traverses the graph from the entry point downwards, greedily searching for the nearest neighbors to the newVector at each layer. This search identifies the optimal connection points for the new node.

      Once the nearest neighbors are found, the new node is linked into the graph structure at all layers up to its top layer. Special handling is included for inserting the first-ever node into the graph or when a new node's layer is higher than any existing node, which updates the graph's entry point. All operations are performed asynchronously.

      Parameters:
      transaction - the Transaction context for all database operations
      newPrimaryKey - the unique Tuple primary key for the new node being inserted
      newVector - the RealVector data to be inserted into the graph
      Returns:
      a CompletableFuture that completes when the insertion operation is finished