JVector: the most advanced embedded vector search engine
JVector is a pure Java embedded vector search engine, used by DataStax Astra DB and (soon) Apache Cassandra.
What is JVector?
JVector vs Lucene searching the Deep100M dataset (about 35GB of vectors and 25GB index):
JVector scales updates linearly to at least 32 threads:
See UPGRADING.md.
Adding to your project. Replace ${latest-version}
with . Example <version>1.0.1</version>
:
<dependency>
<groupId>io.github.jbellis</groupId>
<artifactId>jvector</artifactId>
<!-- Use the latest version from https://central.sonatype.com/artifact/io.github.jbellis/jvector -->
<version>${latest-version}</version>
</dependency>
Building the index:
GraphIndexBuilder
is the entry point for building a graph. You will need to implement
RandomAccessVectorValues
to provide vectors to the builder;
ListRandomAccessVectorValues
is a good starting point.build()
and it will parallelize the build across
all available cores. Otherwise you can call addGraphNode
as you add vectors;
this is non-blocking and can be called concurrently from multiple threads.GraphIndexBuilder.cleanup
when you are done adding vectors. This will
optimize the index and make it ready to write to disk. (Graphs that are
in the process of being built can be searched at any time; you do not have to call
cleanup
first.)Searching the index:
GraphSearcher
is the entry point for searching. Results come back as a SearchResult
object that contains node IDs and scores, in
descending order of similarity to the query vector. GraphSearcher
objects are re-usable,
so unless you have a very simple use case you should use GraphSearcher.Builder
to
create them; GraphSearcher.search
is also available with simple defaults, but calling it
will instantiate a new GraphSearcher
every time so performance will be worse.RandomAccessVectorValues
you provided. You can get the original vector
back with GraphIndex.getVector
, if necessary, but since this is a disk-backed index
you should design your application to avoid doing so unnecessarily.JVector implements DiskANN-style search, meaning that vectors can be compressed using product quantization so that searches can be performed using the compressed representation that is kept in memory. You can enable this with the following steps:
VectorCompressor
object with your vectors using either ProductQuantization.compute
BinaryQuantization.compute
. PQ is more flexible than BQ and is less lossy: even at the same compressed size,
in the datasets tested by Bench, only the ada002 vectors in the wikipedia dataset
are large enough and/or overparameterized enough to benefit from BQ while achieving recall
competitive with PQ. However, if you are dealing with very large vectors and/or your
recall requirement is not strict, you may still want to try BQ since it is MUCH faster to both compute and search with.VectorCompressor::encode
or encodeAll
to encode your vectors, then call
VectorCompressor::createCompressedVectors
to create a CompressedVectors
object.CompressedVectors::approximateScoreFunctionFor
to create a NeighborSimilarity.ApproximateScoreFunction
for your query that uses the
compressed vectors to accelerate search, and pass this
to the GraphSearcher.search
method.OnDiskGraphIndex
and CompressedVectors
have write()
methods to save state to disk.
They initialize from disk using their constructor and load()
methods, respectively.
Writing just requires a DataOutput, but reading requires an
implementation of RandomAccessReader
and the related ReaderSupplier
to wrap your
preferred i/o class for best performance. See SimpleMappedReader
and SimpleMappedReaderSupplier
for an example.OnDiskGraphIndex
,
by contrast, is designed to live on disk and use minimal memory otherwise.OnDiskGraphIndex
in a CachingGraphIndex
to keep the most commonly accessed
nodes (the ones nearest to the graph entry point) in memory.PhysicalCoreExecutor
to limit the amount of operations to the physical core count. The default value is 1/2 the processor count seen by Java.
This may not be correct in all setups (e.g. no hyperthreading or hybrid architectures) so if you wish to override the default use the -Djvector.physical_core_count
property.SiftSmall
class demonstrates how to put all of the above together to index and search the
"small" SIFT dataset of 10,000 vectors.Bench
class performs grid search across the GraphIndexBuilder
parameter space to find
the best tradeoffs between recall and throughput. You can use plot_output.py
to graph the pareto-optimal
points found by Bench
.Some sample KNN datasets for testing based on ada-002 embeddings generated on wikipedia data are available in ivec/fvec format for testing at:
aws s3 ls s3://astra-vector/wikipedia_squad/ --no-sign-request
PRE 100k/
PRE 1M/
PRE 4M/
Bench (see below) automatically downloads the 100k dataset to the ./fvec
directory
This project is organized as a multimodule Maven build. The intent is to produce a multirelease jar suitable for use as
a dependency from any Java 11 code. When run on a Java 20+ JVM with the Vector module enabled, optimized vector
providers will be used. In general, the project is structured to be built with JDK 20+, but when JAVA_HOME
is set to
Java 11 -> Java 19, certain build features will still be available.
Base code is in jvector-base and will be built for Java 11 releases, restricting language features and APIs appropriately. Code in jvector-twenty will be compiled for Java 20 language features/APIs and included in the final multirelease jar targeting supported JVMs. jvector-multirelease packages jvector-base and jvector-twenty as a multirelease jar for release. jvector-examples is an additional sibling module that uses the reactor-representation of jvector-base/jvector-twenty to run example code. jvector-tests contains tests for the project, capable of running against both Java 11 and Java 20+ JVMs.
To run tests, use mvn test
. To run tests against Java 20+, use mvn test
. To run tests against Java 11, use mvn -Pjdk11 test
. To run a single test class,
use the Maven Surefire test filtering capability, e.g., mvn -Dtest=TestNeighborArray test
. You may also use method-level filtering and patterns, e.g.,
mvn -Dtest=TestNeighborArray#testRetain* test
.
You can run SiftSmall
and Bench
directly to get an idea of what all is going on here. Bench
will automatically download required datasets to the fvec
and hdf5
directories.
The files used by SiftSmall
can be found in the siftsmall directory in the project root.
To run either class, you can use the Maven exec-plugin via the following incantations:
mvn compile exec:exec@bench
or for Sift:
mvn compile exec:exec@sift
Bench
takes an optional benchArgs
argument that can be set to a list of whitespace-separated regexes. If any of the
provided regexes match within a dataset name, that dataset will be included in the benchmark. For example, to run only the glove
and nytimes datasets, you could use:
mvn compile exec:exec@bench -DbenchArgs="glove nytimes"
To run Sift/Bench without the JVM vector module available, you can use the following invocations:
mvn -Pjdk11 compile exec:exec@bench
mvn -Pjdk11 compile exec:exec@sift
The ... -Pjdk11
invocations will also work with JAVA_HOME
pointing at a Java 11 installation.
To release, configure ~/.m2/settings.xml
to point to OSSRH and run mvn -Prelease clean deploy
.