46 Performing Similarity Search

To perform a similarity search against vectors stored in Coherence, you can use the SimilaritySearch aggregator. The easiest way to construct one is by using the Aggregators.similaritySearch factory method.

When constructing the SimilaritySearch aggregator, you need to specify three arguments:

1. A ValueExtractor that should be used to retrieve the vector attribute from the map entries.
2. The search vector with which to compare the extracted values.
3. The maximum number of the results to return.

For example, to search the map containing Book objects, and return up to ten most similar books, you would create a SimilaritySearch aggregator instance like this:

var searchVector = createEmbedding(searchQuery);  // outside of Coherence
var search       = Aggregators.similaritySearch(Book::getSummaryEmbedding, searchVector, 10);

By default, the aggregator uses cosine distance to calculate distance between vectors, but you can change that by calling the fluent algorithm method on the created aggregator instance and passing an instance of a different DistanceAlgorithm implementation:

var search = Aggregators.similaritySearch(Book::getSummaryEmbedding, searchVector, 10)
                        .algorithm(new L2SquaredDistance());

Out of the box, Coherence provides CosineDistance, L2SquaredDistance, and InnerProductDistance implementations, but you can easily add support for additional algorithms by implementing the DistanceAlgorithm interface yourself.

After you have an instance of a SimilaritySearch aggregator, you can perform a similarity search by calling the NamedMap.aggregate method like you normally would:

NamedMap<String, Book>          books   = session.getMap("books");
List<QueryResult<String, Book>> results = books.aggregate(search);

The result of the search is a list of up to the maximum specified QueryResult objects (10, in the previous example), which contain entry key, value, and calculated distance between the search vector and a vector extracted from the specified entry. The results are sorted by distance, in ascending order, from closest to farthest.

Security Prerequisites

Validate vector dimension and index parameters before calling native index code. Treat imported index files and native buffers as untrusted inputs unless their origin and integrity are established. A successful Java deserialization check does not validate a native index’s dimensions, capacity or file format.

For the complete configuration and policy, see Protecting Memcached Values and Native Indexes in Securing Oracle Coherence.

Index Lifecycle and Memory

An index is derived state for vectors with a defined dimension and similarity measure. Include native-library availability, index construction time, retained memory and import trust in deployment qualification. Preserve an exact brute-force comparison for representative data when assessing approximate search recall.

• Brute-Force Search
  
• Index-Based Search
  
• Metadata Filtering
  

Brute-Force Search

By default, if no index is defined for the vector attribute, Coherence performs a brute-force search by deserializing every entry, extracting the vector attribute from it, and performing a distance calculation between the extracted vector and the search vector using the specified distance algorithm.

This works for small or medium-sized datasets, because Coherence still performs the search in parallel across cluster members and aggregates the results, but can be very inefficient as the datasets get larger, in which case using one of the supported index types (described in later sections) is recommended.

However, even when using indexes, it may be beneficial to run the same query using brute force, to test recall by comparing the results returned by the (approximate) index-based search and the (exact) brute-force search.

To accomplish that, you can configure the SimilaritySearch aggregator to ignore any configured index and to perform a brute-force search anyway, by calling the bruteForce method on the aggregator instance:

var search = Aggregators.similaritySearch(Book::getSummaryEmbedding, searchVector, 10)
                        .bruteForce();

Indexed Brute-Force Search

It is possible to improve the performance of a brute-force search by creating a forward-only index on the vector attribute using DeserializationAccelerator:

NamedMap<String, Book> books = session.getMap("books");
books.addIndex(new DeserializationAccelerator(Book::getSummaryEmbedding));

This avoids repeated deserialization of Book values when performing a brute-force search, at the cost of additional memory consumed by the indexed vector instances.

The search still performs the exact distance calculation, so the results are exact, just like with the non-indexed brute-force search.

Index-Based Search

While brute-force searches work fine with small datasets, as the dataset gets larger, it is highly recommended that you create a vector index for a vector property.

Out of the box, Coherence supports two vector index types: HNSW index and Binary Quantization index.

HNSW Index

HNSW index performs approximate vector searches using Hierarchical Navigable Small World graphs, as described by Malkov and Yashunin.

Coherence uses an embedded native implementation of hnswlib for the HNSW index implementation. So, to use the HNSW index, you need to add a dependency on the coherence-hnsw module, which contains all Java code and pre-built native libraries for Linux (ARM and x86), Mac (ARM and x86), and Windows (x86 only) that you need:

<dependency>
  <groupId>${coherence.groupId}</groupId>
  <artifactId>coherence-hnsw</artifactId>
  <version>${coherence.version}</version>
</dependency>

After you add the dependency, creating the HNSW index is as simple as:

NamedMap<String, Book> books = session.getMap("books");
books.addIndex(new HnswIndex<>(Book::getSummaryEmbedding, 768));

The first argument to the HnswIndex constructor is the extractor for the vector attribute to index, and the second is the number of dimensions each indexed vector has (which must be identical), which lets the native index implementation preallocate the memory required for the index.

By default, HnswIndex uses cosine distance to calculate vector distances, but this can be overridden by specifying the spaceName argument in a constructor:

NamedMap<String, Book> books = session.getMap("books");
books.addIndex(new HnswIndex<>(Book::getSummaryEmbedding, "L2", 768));

The valid values for space name are COSINE, L2, and IP (inner product).

HnswIndex also provides a number of options that you can use to fine-tune its behavior, which you can specify using the fluent API:

var hnsw = new HnswIndex<>(Book::getSummaryEmbedding, 768)
                    .setEfConstr(200)
                    .setEfSearch(50)
                    .setM(16)
                    .setRandomSeed(100);
books.addIndex(hnsw);

The algorithm parameters in the preceding example are described in more detail in the hnswlib documentation.

You can also specify the maximum index size by calling the setMaxElements method. By default, the index is created with a maximum size of 4,096 elements, and is resized as necessary to accommodate dataset growth. However, the resize operation is somewhat costly and can be avoided if you know ahead of time how many entries are stored in the Coherence map on which you are creating the index, in which case you should configure the index size accordingly.

Note:

Remember that Coherence partitions indexes, so there are as many instances of the HNSW index as there are partitions.

This means that the ideal maxElements settings is just a bit over mapSize / partitionCount, and not the actual map size, which would be way too big.

After you create and configure an HNSW index, you can perform searches the same way as you did earlier using brute-force search. If one is available, then Coherence automatically detects and uses the HNSW index.

Binary Quantization

Coherence also supports the Binary Quantization-based index, which provides significant space savings (32x) compared to vector indexes that use float32 vectors, such as HNSW. It does this by converting each 32-bit float in the original vector into either 0 or 1, and representing it using a single bit in a BitSet.

The downside is that the recall may not be as accurate, especially with smaller vectors, but that can be largely addressed by oversampling and re-scoring the results, which Coherence automatically performs.

BinaryQuantIndex is implemented in pure Java, and is a part of the main Coherence distribution, so it requires no additional dependencies. To create it, call the NamedMap.addIndex method:

NamedMap<String, Book> books = session.getMap("books");
books.addIndex(new BinaryQuantIndex<>(Book::getSummaryEmbedding));

The only option you can specify is the oversamplingFactor, which is the multiplier for the maximum number of results to return, and is 3 by default, meaning that if your search aggregator is configured to return 10 results, binary quantization search initially returns 30 results based on the Hamming distance between the binary representation of the search vector and index vectors, rescores all 30 results using exact distance calculation, and then reorders and returns the top 10 results based on the calculated exact distance.

To change oversamplingFactor, you can specify it using the fluent API when creating an index:

NamedMap<String, Book> books = session.getMap("books");
books.addIndex(new BinaryQuantIndex<>(Book::getSummaryEmbedding).oversamplingFactor(5));

In the preceding example, this causes the SimilaritySearch aggregator to return and re-score 50 results initially, instead of 30.

Just like with the HNSW index, after you create and configure a Binary Quantization index, you can perform searches the same way as you did previously, using a brute-force search. Coherence automatically detects it and uses it.

Metadata Filtering

In addition to a vector-based similarity search, you can use standard Coherence filters to perform metadata-based filtering of the results. For example, if you wanted to search books by a specific author only, you could specify a metadata filter that the SimilaritySearch aggregator should use with a vector similarity search:

var search  = Aggregators.similaritySearch(Book::getSummaryEmbedding, searchVector, 3)
                         .filter(Filters.equal(Book::getAuthor, "Jules Verne"));
var results = books.aggregate(search);

The preceding example should return only the top 3 books written by Jules Verne, sorted according to vector similarity.

Metadata filtering works the same regardless of whether you use a brute-force or index-based search, and uses any indexes you may have on the metadata attributes on which you are filtering, such as Book::getAuthor in this case, to speed up filter evaluation.

If you are a long-time Coherence user, you may be wondering why we are setting the filter on the aggregator itself and performing a filter evaluation inside the aggregator, instead of using the aggregate method that accepts a filter and lets you pre-filter the set of entries to aggregate.

The reason is that both vector index implementations need to evaluate the filter internally, and only include the result if it evaluates to true, so the previous example works in all situations.

However, if you are using a brute-force search, you may achieve the same result, and likely improve performance, by pre-filtering the entries:

var search  = Aggregators.similaritySearch(Book::getSummaryEmbedding, searchVector, 3);
var results = books.aggregate(Filters.equal(Book::getAuthor, "Jules Verne"), search);