Getting started with C++

This tutorial will show you how to install SVS and run your first search with it!

Building 

Building SVS should be relatively straight-forward. We test on Ubuntu 22.04 LTS, but any Linux distribution should work.

Prerequisites 

A C++20 capable compiler:
- GCC >= 11.0
- Clang >= 13.0
OneMKL
- Make sure you set the OneMKL environment variables, e.g., source /opt/intel/oneapi/setvars.sh.
Click to expand installation details
OneMKL can be installed as part of the Intel oneAPI Base Toolkit by following one of the methods indicated in the oneAPI docs .

For example, the following commands show how to install the OneMKL component of the Intel oneAPI Base Toolkit on a Linux system using the offline installer:
wget [link to the offline installer] sudo sh [downloaded installer script] -a --components intel.oneapi.lin.mkl.devel --action install --eula accept -s source /opt/intel/oneapi/setvars.sh

CMake build 

To build SVS and the included examples, use the following:

mkdir build && cd build
cmake .. -DSVS_BUILD_EXAMPLES=YES
cmake --build . -j$(nproc)

Verifying the build 

Run the following command to verify that SVS was successfully installed. It should print some types, like float32.

examples/cpp/types

SVS search example 

In this tutorial we will showcase the most important features of SVS. The full example is available at the end of this tutorial. You can run it with the following command:

examples/cpp/vamana ../data/test_dataset/data_f32.fvecs ../data/test_dataset/queries_f32.fvecs ../data/test_dataset/groundtruth_euclidean.ivecs

Example data 

We will use the random dataset included in SVS for testing in data/test_dataset.

Before searching, we need to construct an index over that data. The index is a graph connecting related data vectors in such a way that searching for nearest neighbors yields good results. The first step is to define the hyper-parameters of the graph we wish to construct. Don’t worry too much about selecting the correct values for these hyper-parameters right now. This usually involves a bit of experimentation and is dataset dependent. See How to Choose Graph Building Hyper-parameters for details.

This is done by creating an instance of svs::index::vamana::VamanaBuildParameters.

auto parameters = svs::index::vamana::VamanaBuildParameters{
    1.2,  // alpha
    64,   // graph max degree
    128,  // search window size
    1024, // max candidate pool size
    60,   // prune to degree
    true, // full search history
};

Now that we have established our hyper-parameters, it is time to build the index. Passing the dims is optional, but may yield performance benefits if given.

size_t num_threads = 4;
svs::Vamana index = svs::Vamana::build<float>(
    parameters, svs::VectorDataLoader<float>(data_vecs), svs::DistanceL2(), num_threads
);

Note the use of svs::VectorDataLoader to indicate both the path to the dataset file data_vecs and the data type of the file on disk (see I/O and Conversion Tools for supported file formats). See svs::Vamana::build() for details about the build function.

Searching the index 

The graph is now built and we can perform queries over the graph. First, we load the queries from a file on disk.

After searching, we compare the search results with ground truth results which we also load from the SVS test dataset.

// Load the queries and ground truth.
auto queries = svs::load_data<float>(query_vecs);
auto groundtruth = svs::load_data<uint32_t>(groundtruth_vecs);

Performing queries is easy. First establish a base-line search window size. This provides a parameter by which performance and accuracy can be traded. The larger search_window_size is, the higher the accuracy but the lower the performance. Note that search_window_size must be at least as large as the desired number of neighbors. See How to Set the Search Window Size for details.

We use the search function to find the 10 approximate nearest neighbors to each query. See svs::Vamana::search() for details about the search function. Then, we compute the 10-recall at 10 of the returned neighbors, checking to confirm the accuracy against the ground truth.

index.set_search_window_size(30);
svs::QueryResult<size_t> results = index.search(queries, 10);
double recall = svs::k_recall_at_n(groundtruth, results);
check(0.8215, recall);

Saving the index 

If you are satisfied with the performance of the generated index, you can save it to disk to avoid rebuilding it in the future.

See svs::Vamana::save() for details about the save function.

index.save("example_config", "example_graph", "example_data");

Note

The save index function currently uses three folders for saving. All three are needed to be able to reload the index.

One folder for the graph.
One folder for the data.
One folder for metadata.

This is subject to change in the future.

Reloading a saved index 

To reload the index from file, use the corresponding constructor with the three folder names used to save the index. Note that the second argument, the one corresponding to the file for the data, requires a svs::VectorDataLoader and the corresponding data type.

After reloading, performing queries is identical to before. See the entire example code for details about the run_recall function used to check the search results against ground truth.

// We can reload an index from a previously saved set of files.
index = svs::Vamana::assemble<float>(
    "example_config",
    svs::GraphLoader("example_graph"),
    svs::VectorDataLoader<float>("example_data"),
    svs::DistanceType::L2,
    4 // num_threads
);

recall = run_recall(index, queries, groundtruth, 30, 10, "Reload");
check(0.8215, recall);

Search using vector compression 

Vector compression can be used to speed up search. It can be done with a svs::quantization::lvq::LVQDataset.

See How to Choose Compression Parameters for details on setting the compression parameters.

// Quantization
size_t padding = 32;
namespace lvq = svs::quantization::lvq;

// Wrap the compressor object in a lazy functor.
// This will defer loading and compression of the LVQ dataset until the threadpool
// used in the index has been created.
auto compressor = svs::lib::Lazy([=](svs::threads::ThreadPool auto& threadpool) {
    auto data = svs::VectorDataLoader<float, 128>("example_data").load();
    return lvq::LVQDataset<8, 0, 128>::compress(data, threadpool, padding);
});
index = svs::Vamana::assemble<float>(
    "example_config", svs::GraphLoader("example_graph"), compressor, svs::DistanceL2()
);

recall = run_recall(index, queries, groundtruth, 30, 10, "Compressed Load");
check(0.8215, recall);

Note

Vector compression is usually accompanied by an accuracy loss for the same search window size and may require increasing the window size to compensate.

Saving an index with compressed vectors 

SVS has support to save and load indices with a previously compressed dataset. The saving and loading procedures are the same as with uncompressed vectors.

Entire example 

This ends the example demonstrating the features of the Vamana index. The entire executable code is shown below. Please reach out with any questions.

//! [Example All]

//! [Includes]
// SVS Dependencies
#include "svs/orchestrators/vamana.h"  // bulk of the dependencies required.
#include "svs/core/recall.h"           // Convenient k-recall@n computation.
#include "svs/extensions/vamana/lvq.h" // LVQ extensions for the Vamana index.

// Alternative main definition
#include "svsmain.h"

// stl
#include <map>
#include <string>
#include <string_view>
#include <vector>
//! [Includes]

//! [Helper Utilities]
double run_recall(
    svs::Vamana& index,
    const svs::data::SimpleData<float>& queries,
    const svs::data::SimpleData<uint32_t>& groundtruth,
    size_t search_window_size,
    size_t num_neighbors,
    std::string_view message = ""
) {
    index.set_search_window_size(search_window_size);
    auto results = index.search(queries, num_neighbors);
    double recall = svs::k_recall_at_n(groundtruth, results, num_neighbors, num_neighbors);
    if (!message.empty()) {
        fmt::print("[{}] ", message);
    }
    fmt::print("Windowsize = {}, Recall = {}\n", search_window_size, recall);
    return recall;
}

const bool DEBUG = false;
void check(double expected, double got, double eps = 0.001) {
    double diff = std::abs(expected - got);
    if constexpr (DEBUG) {
        fmt::print("Expected {}. Got {}\n", expected, got);
    } else {
        if (diff > eps) {
            throw ANNEXCEPTION("Expected ", expected, ". Got ", got, '!');
        }
    }
}
//! [Helper Utilities]

// Alternative main definition
int svs_main(std::vector<std::string> args) {
    //! [Argument Extraction]
    const size_t nargs = args.size();
    if (nargs != 4) {
        throw ANNEXCEPTION("Expected 3 arguments. Instead, got ", nargs, '!');
    }
    const std::string& data_vecs = args.at(1);
    const std::string& query_vecs = args.at(2);
    const std::string& groundtruth_vecs = args.at(3);
    //! [Argument Extraction]

    // Building the index

    //! [Build Parameters]
    auto parameters = svs::index::vamana::VamanaBuildParameters{
        1.2,  // alpha
        64,   // graph max degree
        128,  // search window size
        1024, // max candidate pool size
        60,   // prune to degree
        true, // full search history
    };
    //! [Build Parameters]

    //! [Index Build]
    size_t num_threads = 4;
    svs::Vamana index = svs::Vamana::build<float>(
        parameters, svs::VectorDataLoader<float>(data_vecs), svs::DistanceL2(), num_threads
    );
    //! [Index Build]

    // Searching the index

    //! [Load Aux]
    // Load the queries and ground truth.
    auto queries = svs::load_data<float>(query_vecs);
    auto groundtruth = svs::load_data<uint32_t>(groundtruth_vecs);
    //! [Load Aux]

    //! [Perform Queries]
    index.set_search_window_size(30);
    svs::QueryResult<size_t> results = index.search(queries, 10);
    double recall = svs::k_recall_at_n(groundtruth, results);
    check(0.8215, recall);
    //! [Perform Queries]

    //! [Search Window Size]
    auto expected_recall =
        std::map<size_t, double>({{10, 0.5509}, {20, 0.7281}, {30, 0.8215}, {40, 0.8788}});
    for (auto windowsize : {10, 20, 30, 40}) {
        recall = run_recall(index, queries, groundtruth, windowsize, 10, "Sweep");
        check(expected_recall.at(windowsize), recall);
    }
    //! [Search Window Size]

    // Saving the index

    //! [Saving]
    index.save("example_config", "example_graph", "example_data");
    //! [Saving]

    // Reloading a saved index

    //! [Loading]
    // We can reload an index from a previously saved set of files.
    index = svs::Vamana::assemble<float>(
        "example_config",
        svs::GraphLoader("example_graph"),
        svs::VectorDataLoader<float>("example_data"),
        svs::DistanceType::L2,
        4 // num_threads
    );

    recall = run_recall(index, queries, groundtruth, 30, 10, "Reload");
    check(0.8215, recall);
    //! [Loading]

    // Search using vector compression

    //! [Compressed Loader]
    // Quantization
    size_t padding = 32;
    namespace lvq = svs::quantization::lvq;

    // Wrap the compressor object in a lazy functor.
    // This will defer loading and compression of the LVQ dataset until the threadpool
    // used in the index has been created.
    auto compressor = svs::lib::Lazy([=](svs::threads::ThreadPool auto& threadpool) {
        auto data = svs::VectorDataLoader<float, 128>("example_data").load();
        return lvq::LVQDataset<8, 0, 128>::compress(data, threadpool, padding);
    });
    index = svs::Vamana::assemble<float>(
        "example_config", svs::GraphLoader("example_graph"), compressor, svs::DistanceL2()
    );
    //! [Compressed Loader]

    //! [Search Compressed]
    recall = run_recall(index, queries, groundtruth, 30, 10, "Compressed Load");
    check(0.8215, recall);
    //! [Search Compressed]

    //! [Build Index Compressed]
    // Compressed building
    index =
        svs::Vamana::build<float>(parameters, compressor, svs::DistanceL2(), num_threads);
    recall = run_recall(index, queries, groundtruth, 30, 10, "Compressed Build");
    check(0.8212, recall);
    //! [Build Index Compressed]

    //! [Only Loading]
    // We can reload an index from a previously saved set of files.
    index = svs::Vamana::assemble<float>(
        "example_config",
        svs::GraphLoader("example_graph"),
        svs::VectorDataLoader<float>("example_data"),
        svs::DistanceType::L2,
        4 // num_threads
    );
    //! [Only Loading]

    //! [Set n-threads]
    index.set_num_threads(4);
    //! [Set n-threads]

    return 0;
}

// Special main providing some helpful utilties.
SVS_DEFINE_MAIN();
//! [Example All]