US 12,613,848 B2Granted

Parallel construction algorithm for in-memory hierarchical navigable small world vector index in a relational database management system

AssigneeOracle International Corporation

InventorsMarco Arnaboldi, Ioannis Alagiannis, Martin Brugnara, Laurent Phillipe Daynes, Damien Hilloulin, Vlad Ioan Haprian

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

The present disclosure relates to efficiently constructing in-memory HNSW vector indexes in a database management system (DBMS). A DBMS may store in memory a segmented array, wherein the segmented array may store representations of a plurality of vectors from a database. A hierarchical navigable small world (HNSW) vector index may be constructed in the memory, wherein the HNSW vector index may index the plurality of vectors. A similarity search may be performed using the HNSW vector index.

Claims20

Dependent claims

A method comprising:

a database management system (DBMS) storing in memory a segmented array in vector storage, wherein:
the segmented array stores representations of a plurality of vectors from a database,
each segment of the segmented array comprises a plurality of elements corresponding to respective vectors of the plurality of vectors,
each element of the plurality of elements comprises a representation of a respective vector of the plurality of vectors and metadata associated with the respective vector and is indexed by a vector identifier for the respective vector, and
the vector identifier indicates a position of the vector in the vector storage;
constructing, in the memory, a hierarchical navigable small world (HNSW) vector index, wherein the HNSW vector index indexes the plurality of vectors;
and
performing a similarity search using the HNSW vector index,
wherein the method is performed by one or more computing devices.

6 more elements

One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause the one or more computing devices to at least:

store in memory a segmented array in vector storage, wherein;
the segmented array stores representations of a plurality of vectors from a database,
each segment of the segmented array comprises a plurality of elements corresponding to respective vectors of the plurality of vectors,
each element of the plurality of elements comprises a representation of a respective vector of the plurality of vectors and metadata associated with the respective vector and is indexed by a vector identifier for the respective vector;
and
the vector identifier indicates a position of the vector in the vector storage;
construct, in the memory, a hierarchical navigable small world (HNSW) vector index, wherein the HNSW vector index indexes the plurality of vectors;
and
performing a similarity search using the HNSW vector index.

6 more elements

Dependencies are inferred from the claim text.