### IVF + RaBitQ Index Construction Setup

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Demonstrates the initial steps for constructing an IVF index combined with RaBitQ, focusing on dataset download and KMeans clustering. This approach aims for minimal memory usage.

```shell
# Download dataset and perform KMeans clustering
wget http://www.cse.cuhk.edu.hk/systems/hash/gqr/dataset/deep1M.tar.gz
tar -zxvf deep1M.tar.gz

```

--------------------------------

### Querying IVF Index in C++

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/quick_start.md

This example demonstrates loading an IVF index and query files, performing searches with varying nprobes, and calculating recall and QPS. It requires the rabitq library headers and appropriate .fvecs and .ivecs data files.

```c++
#include <iostream>
#include <vector>

#include "defines.hpp"
#include "index/ivf/ivf.hpp"
#include "utils/io.hpp"
#include "utils/stopw.hpp"
#include "utils/tools.hpp"

using PID = rabitqlib::PID;
using index_type = rabitqlib::ivf::IVF;
using data_type = rabitqlib::RowMajorArray<float>;
using gt_type = rabitqlib::RowMajorArray<uint32_t>;

static std::vector<size_t> get_nprobes(
    const index_type& ivf,
    const std::vector<size_t>& all_nprobes,
    data_type& query,
    gt_type& gt
);

static size_t topk = 10;
static size_t test_round = 5;

int main(int argc, char** argv) {
    if (argc < 4) {
        std::cerr << "Usage: " << argv[0] << " <arg1> <arg2> <arg3> <arg4>\n"
                  << "arg1: path for index \n"
                  << "arg2: path for query file, format .fvecs\n"
                  << "arg3: path for groundtruth file format .ivecs\n"
                  << "arg4: whether use high accuracy fastscan, (\"true\" or \"false\"), "
                     "true by default\n\n";
        exit(1);
    }

    char* index_file = argv[1];
    char* query_file = argv[2];
    char* gt_file = argv[3];
    bool use_hacc = true;

    if (argc > 4) {
        std::string hacc_str(argv[4]);
        if (hacc_str == "false") {
            use_hacc = false;
            std::cout << "Do not use Hacc FastScan\n";
        }
    }

    data_type query;
    gt_type gt;
    rabitqlib::load_vecs<float, data_type>(query_file, query);
    rabitqlib::load_vecs<uint32_t, gt_type>(gt_file, gt);
    size_t nq = query.rows();
    size_t total_count = nq * topk;

    index_type ivf;
    ivf.load(index_file);

    std::vector<size_t> all_nprobes;
    all_nprobes.push_back(5);
    for (size_t i = 10; i < 200; i += 10) {
        all_nprobes.push_back(i);
    }
    for (size_t i = 200; i < 400; i += 40) {
        all_nprobes.push_back(i);
    }
    for (size_t i = 400; i <= 1500; i += 100) {
        all_nprobes.push_back(i);
    }
    for (size_t i = 2000; i <= 4000; i += 500) {
        all_nprobes.push_back(i);
    }

    all_nprobes.push_back(6000);
    all_nprobes.push_back(10000);
    all_nprobes.push_back(15000);

    rabitqlib::StopW stopw;

    auto nprobes = get_nprobes(ivf, all_nprobes, query, gt);
    size_t length = nprobes.size();

    std::vector<std::vector<float>> all_qps(test_round, std::vector<float>(length));
    std::vector<std::vector<float>> all_recall(test_round, std::vector<float>(length));

    for (size_t r = 0; r < test_round; r++) {
        for (size_t l = 0; l < length; ++l) {
            size_t nprobe = nprobes[l];
            size_t total_correct = 0;
            float total_time = 0;
            std::vector<PID> results(topk);
            for (size_t i = 0; i < nq; i++) {
                stopw.reset();
                ivf.search(&query(i, 0), topk, nprobe, results.data(), use_hacc);
                total_time += stopw.get_elapsed_micro();
                for (size_t j = 0; j < topk; j++) {
                    for (size_t k = 0; k < topk; k++) {
                        if (gt(i, k) == results[j]) {
                            total_correct++;
                            break;
                        }
                    }
                }
            }
            float qps = static_cast<float>(nq) / (total_time / 1e6F);
            float recall =
                static_cast<float>(total_correct) / static_cast<float>(total_count);

            all_qps[r][l] = qps;
            all_recall[r][l] = recall;
        }
    }

    auto avg_qps = rabitqlib::horizontal_avg(all_qps);
    auto avg_recall = rabitqlib::horizontal_avg(all_recall);

    std::cout << "nprobe\tQPS\trecall" << '\n';

    for (size_t i = 0; i < length; ++i) {
        size_t nprobe = nprobes[i];
        float qps = avg_qps[i];
        float recall = avg_recall[i];

        std::cout << nprobe << '\t' << qps << '\t' << recall << '\n';
    }

    return 0;
}

static std::vector<size_t> get_nprobes(
    const index_type& ivf,
    const std::vector<size_t>& all_nprobes,
    data_type& query,
    gt_type& gt
) {
    size_t nq = query.rows();
    size_t total_count = topk * nq;
    float old_recall = 0;
    std::vector<size_t> nprobes;

    for (auto nprobe : all_nprobes) {
        nprobes.push_back(nprobe);

        size_t total_correct = 0;
        std::vector<PID> results(topk);
        for (size_t i = 0; i < nq; i++) {
            ivf.search(&query(i, 0), topk, nprobe, results.data());
            for (size_t j = 0; j < topk; j++) {
                for (size_t k = 0; k < topk; k++) {
                    if (gt(i, k) == results[j]) {
                        total_correct++;
                        break;
                    }
                }
            }
        }
```

--------------------------------

### Indexing with Split Batched Vectors

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/rabitq/quantizer.md

Shows the setup and quantization process for batched vectors in an IVF index structure.

```cpp
#include <random>
#include <vector>

#include "quantization/rabitq.hpp"

int main() {
    size_t dim = 768;
    size_t batch_size = 32;

    std::vector<float> vector(dim * batch_size);
    std::vector<float> centroid(dim);
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::normal_distribution<float> dist(0, 1);

    // generate a random vector
    for (size_t i = 0; i < dim; ++i) {
        centroid[i] = dist(gen);
    }
    for (size_t i = 0; i < dim * batch_size; ++i) {
        vector[i] = dist(gen);
    }

    size_t bits = 5;  // num of bits for full codes
    // `batch_data` includes packed binary codes (dim / 8 bytes) and three factors - f_add,
    // f_rescale and f_error (12 bytes)
    // f_error can be dropped if the error bound is not used in your index (e.g., QG)
    std::vector<char> batch_data((dim / 8 + 12) * batch_size);

    // `ex_data` includes compact binary codes (dim / 8 bytes) and two factors - f_add_ex,
    // f_rescale_ex (8 bytes). Here, we drop f_error_ex since it is not used in this index.
    // You can also use rabitqlib::ExDataMap<float>::data_bytes(dim, bits-1) to get the ex
    // data bytes
    std::vector<char> ex_data((dim * (bits - 1) / 8 + 8) * batch_size);

    rabitqlib::quant::quantize_split_batch(
        vector.data(),
        centroid.data(),
        batch_size,
        dim,
        bits - 1,
        batch_data.data(),
        ex_data.data(),
        rabitqlib::METRIC_L2
    );

    // use fast implementation for the data format
    rabitqlib::quant::RabitqConfig config = rabitqlib::quant::faster_config(dim, bits);
    rabitqlib::quant::quantize_split_batch(
        vector.data(),
        centroid.data(),
        batch_size,
        dim,
        bits - 1,
        batch_data.data(),
        ex_data.data(),
        rabitqlib::METRIC_L2,
        config
    );

    return 0;
}
```

--------------------------------

### Install CMake on Ubuntu/Debian

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/tests/README.md

Use apt-get to install CMake on Ubuntu or Debian-based systems.

```bash
sudo apt-get update
sudo apt-get install cmake
```

--------------------------------

### Install CMake on macOS

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/tests/README.md

Use Homebrew to install CMake on macOS systems.

```bash
brew install cmake
```

--------------------------------

### Load and Query a Pre-built QG Index

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Shows how to initialize a QuantizedGraph from a saved file and execute a search operation.

```cpp
#include <vector>
#include <iostream>
#include "index/symqg/qg.hpp"

using PID = rabitqlib::PID;

int main() {
    size_t dim = 128;
    size_t topk = 10;
    size_t ef = 100;

    // Load pre-constructed index
    rabitqlib::symqg::QuantizedGraph<float> qg;
    qg.load("./qg_example.index");

    // Set search parameters
    qg.set_ef(ef);

    // Prepare query vector
    std::vector<float> query(dim);
    // Fill query with data...

    // Execute search
    std::vector<PID> results(topk);
    qg.search(query.data(), topk, results.data());

    // Results are stored in results vector
    std::cout << "Top-" << topk << " nearest neighbors: ";
    for (size_t i = 0; i < topk; i++) {
        std::cout << results[i] << " ";
    }
    std::cout << '\n';

    return 0;
}
```

--------------------------------

### Build RaBitQ with Tests Enabled

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/tests/README.md

Configure, build, and run tests for the RaBitQ library using CMake and make. Ensure tests are enabled by passing -DRABITQ_BUILD_TESTS=ON.

```bash
# Create build directory
mkdir build bin
cd build

# Configure with tests enabled (tests are OFF by default)
cmake .. -DRABITQ_BUILD_TESTS=ON

# Build the tests
make -j$(nproc)

# Run all tests
./tests/rabitq_tests

# Or use CTest for detailed output
ctest --output-on-failure
```

--------------------------------

### Execute HNSW + RaBitQ queries

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Load a pre-built index and perform batch searches across various ef values to measure QPS and recall.

```cpp
#include <iostream>
#include <vector>
#include <chrono>
#include "index/hnsw/hnsw.hpp"
#include "utils/io.hpp"

using PID = rabitqlib::PID;
using index_type = rabitqlib::hnsw::HierarchicalNSW;
using data_type = rabitqlib::RowMajorArray<float>;
using gt_type = rabitqlib::RowMajorArray<uint32_t>;

int main() {
    // Load queries and ground truth
    data_type query;
    gt_type gt;
    rabitqlib::load_vecs<float, data_type>("deep1M/deep1M_query.fvecs", query);
    rabitqlib::load_vecs<uint32_t, gt_type>("deep1M/deep1M_groundtruth.ivecs", gt);

    size_t nq = query.rows();
    size_t topk = 10;

    // Load pre-built index
    index_type hnsw;
    rabitqlib::MetricType metric_type = rabitqlib::METRIC_L2;
    hnsw.load("deep1M/deep1M_c16_b5.index", metric_type);

    // Search with different ef values
    std::vector<size_t> efs = {10, 20, 50, 100, 200, 500, 1000};

    for (size_t ef : efs) {
        auto start = std::chrono::high_resolution_clock::now();

        // Batch search
        std::vector<std::vector<std::pair<float, PID>>> results =
            hnsw.search(query.data(), nq, topk, ef, 1);  // 1 thread

        auto end = std::chrono::high_resolution_clock::now();
        float elapsed_us = std::chrono::duration<float, std::micro>(end - start).count();

        // Calculate recall
        size_t total_correct = 0;
        for (size_t i = 0; i < nq; i++) {
            for (size_t j = 0; j < topk; j++) {
                for (size_t k = 0; k < topk; k++) {
                    if (gt(i, k) == results[i][j].second) {
                        total_correct++;
                        break;
                    }
                }
            }
        }

        float qps = static_cast<float>(nq) / (elapsed_us / 1e6F);
        float recall = static_cast<float>(total_correct) / static_cast<float>(nq * topk);

        std::cout << "EF=" << ef << "\tQPS=" << qps << "\tRecall=" << recall << '\n';
    }

    return 0;
}
```

--------------------------------

### Construct and Query a QG Index

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Demonstrates the full workflow of generating random data, building a QuantizedGraph index, and performing nearest neighbor searches.

```cpp
#include <random>
#include <vector>
#include <iostream>
#include "index/symqg/qg.hpp"
#include "index/symqg/qg_builder.hpp"
#include "utils/stopw.hpp"

using PID = rabitqlib::PID;

int main() {
    size_t dim = 128;
    size_t N = 16000;

    // Generate random data vectors
    std::vector<float> data(dim * N);
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::normal_distribution<float> dist(0, 1);

    for (size_t i = 0; i < dim * N; i++) {
        data[i] = dist(gen);
    }

    size_t degree = 32;  // Degree bound (must be multiple of 32)
    size_t ef = 200;     // Search window size for indexing

    // Initialize QG index
    rabitqlib::symqg::QuantizedGraph<float> qg(N, dim, degree);

    // Initialize builder and construct index
    rabitqlib::symqg::QGBuilder builder(qg, ef, data.data());

    rabitqlib::StopW stopw;
    builder.build();  // Build index iteratively
    float total_time = stopw.get_elapsed_micro() / 1e6;
    std::cout << "Indexing time = " << total_time << "s\n";

    // Save index
    qg.save("./qg_example.index");

    // Querying
    size_t nq = 10;
    std::vector<float> queries(nq * dim);
    for (size_t i = 0; i < nq * dim; i++) {
        queries[i] = data[i];  // Use first nq vectors as queries
    }

    size_t topk = 10;
    size_t ef_search = 100;

    qg.set_ef(ef_search);  // Set search window size
    std::vector<PID> results(topk);

    for (size_t qid = 0; qid < nq; qid++) {
        qg.search(queries.data() + (dim * qid), topk, results.data());

        std::cout << "Query " << qid << "'s " << topk << " NNs: ";
        for (size_t i = 0; i < topk; i++) {
            std::cout << results[i] << " ";
        }
        std::cout << '\n';
    }

    return 0;
}
```

--------------------------------

### Load and Search QG Index

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/index/qg.md

Loads a pre-constructed QG index from a file and performs a k-NN search with a specified search window size ('ef').

```cpp
void QuantizedGraph::search(
    const T* __restrict__ query, 
    uint32_t k, 
    uint32_t* __restrict__ results);

```

```cpp
QuantizedGraph<float> qg;
qg.load("./qg_example.index"); // load pre-constructed index


size_t ef = 100;
size_t topk = 10;
std::vector<PID> results(topk); // result buffer
float* query = new float[cols]; // query vector (only for illustration)

qg.set_ef(ef);  // set search window size
qg.search(query, topk, results.data()); // search knn, result will be stored in results
```

--------------------------------

### Initialize RaBitQ Rotator (Default)

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/rabitq/rotator.md

Initializes the default rotator using FFHT + Kac’s Walk. Vectors are padded to the smallest multiple of 64. Time complexity is O(D * log D).

```cpp
rabitqlib::Rotator<float>* rotator = rabitqlib::choose_rotator<float>(
    dim = dim, 
    RotatorType type = RotatorType::FhtKacRotator);
```

--------------------------------

### Initialize QuantizedGraph and QGBuilder

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/index/qg.md

Initializes a QuantizedGraph and a QGBuilder for index construction. Ensure 'max_deg' is a multiple of 32. The 'data' pointer should point to the dataset of size num * dim.

```cpp
QuantizedGraph::QuantizedGraph(
        size_t num,
        size_t dim,
        size_t max_deg,
        RotatorType type = RotatorType::FhtKacRotator
    );

QGBuilder::QGBuilder(
        QuantizedGraph<float>& index,
        uint32_t ef_build,
        const float* data,
        size_t num_threads = std::numeric_limits<size_t>::max()
    )
```

```cpp
size_t rows = 1000000;
size_t cols = 128;
size_t degree = 32;
size_t ef = 200

float* data = new float[rows * cols]; // only for illustration

QuantizedGraph qg(rows, cols, degree); // init qg

QGBuilder builder(qg, ef, data.data()); // init builder
```

--------------------------------

### Basic Scalar Quantization with RaBitQ

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Demonstrates standard and faster scalar quantization using the RaBitQ library. Ensure correct dimensions and bit-widths are used.

```cpp
#include <random>
#include <vector>
#include "quantization/rabitq.hpp"

int main() {
    size_t dim = 768;

    std::vector<float> vector(dim);
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::normal_distribution<float> dist(0, 1);

    // Generate a random vector
    for (size_t i = 0; i < dim; ++i) {
        vector[i] = dist(gen);
    }

    size_t bits = 8;                  // Number of bits for total code
    std::vector<uint32_t> code(dim);  // Output code vector
    float delta;                      // Delta for scalar quantization
    float vl;                         // Lower value for scalar quantization

    // Standard scalar quantization (optimal accuracy)
    rabitqlib::quant::quantize_scalar(vector.data(), dim, bits, code.data(), delta, vl);

    // Faster version with near-optimal accuracy (must init config first)
    rabitqlib::quant::RabitqConfig config = rabitqlib::quant::faster_config(dim, bits);
    rabitqlib::quant::quantize_scalar(
        vector.data(), dim, bits, code.data(), delta, vl, config
    );

    return 0;
}
```

--------------------------------

### Build and Query QuantizedGraph in C++

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/quick_start.md

Demonstrates the full lifecycle of a QuantizedGraph index, including random data generation, index construction, and nearest neighbor search.

```cpp
#include <random>
#include <vector>

#include "index/symqg/qg.hpp"
#include "index/symqg/qg_builder.hpp"
#include "utils/stopw.hpp"

using PID = rabitqlib::PID;

int main() {
    size_t dim = 128;
    size_t N = 16000;

    std::vector<float> data(dim * N);

    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::normal_distribution<float> dist(0, 1);

    // generate N random data vectors
    for (size_t i = 0; i < dim * N; i++) {
        data[i] = dist(gen);
    }

    size_t degree = 32;  // degree bound for graph
    size_t ef = 200;     // size of search window for indexing

    rabitqlib::symqg::QuantizedGraph<float> qg(N, dim, degree);  // init index

    rabitqlib::symqg::QGBuilder builder(qg, ef, data.data());  // builder of index

    rabitqlib::StopW stopw;
    stopw.reset();

    builder.build();  // construct index

    float total_time = stopw.get_elapsed_micro();
    total_time /= 1e6;

    std::cout << "indexing time = " << total_time << "s" << '\n';

    size_t nq = 10;
    std::vector<float> query(nq * dim);

    // take first nq data vectors as query vectors
    for (size_t i = 0; i < nq * dim; i++) {
        query[i] = data[i];
    }

    size_t topk = 10;
    size_t ef_search = 100;

    qg.set_ef(ef_search);
    std::vector<PID> results(topk);

    for (size_t qid = 0; qid < nq; qid++) {
        qg.search(query.data() + (dim * qid), topk, results.data());
        std::cout << "query " << qid << "'s " << topk << "NNs:" << '\n';
        for (size_t i = 0; i < topk; i++) {
            std::cout << "{ID: " << results[i] << "}  ";
        }
        std::cout << '\n';
    }

    return 0;
}
```

--------------------------------

### Pack Quantized Codes with RaBitQLib

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/compact_code.md

Demonstrates packing quantized codes using the `packing_rabitqplus_code` function from RaBitQLib. This function is used for compact storage of codes with specified bit widths.

```cpp
#include <rabitqlib/quantization/pack_excode.hpp>
#include <stdint.h>
#include <random>

int main(){
    size_t dim = 768;
    size_t bits = 4;

    std::vector<uint8_t> code(dim);
    // Generate random 4-bit values (0-15) for each dimension
    for (size_t i = 0; i < dim; ++i) {
        code[i] = rand() % 16;  // 4-bit values range from 0 to 15
    }

    std::vector<uint8_t> compact_code(dim * bits / 8);

    rabitqlib::quant::rabitq_impl::ex_bits::packing_rabitqplus_code(
        code.data(), compact_code.data(), dim, bits
    );
}
```

--------------------------------

### Build and Save QG Index

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/index/qg.md

Constructs the QG index iteratively using the builder and then saves the constructed index to a file.

```cpp
builder.build();    // build index interatively

const char* index_file = "./qg_example.index"
qg.save(index_file);    // save index
```

--------------------------------

### Initialize and Process Query with Rabitq

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/rabitq/quantizer.md

Initializes a `SplitBatchQuery` object with specified dimensions and bit-width, then sets the 'g_add' factors using Euclidean distance and dot product. This prepares the query for distance estimation.

```cpp
    size_t dim = 768;  // the dimensionality
    size_t bits = 5;   // the bit-width of DATA vectors
    std::vector<float> rotated_query(dim);

    // The flag use_hacc controls the precision of FastScan.
    // `use_hacc = false` - each number in LUTs is quantized into 8 bits.
    // `use_hacc = true` - each number in LUTs is quantized into 16 bits.
    // By default, `use_hacc = true` as it works for all settings of `bits`,
    // i.e., the bit-width of queries is significantly larger than that for data.
    // When the bit-width of data <= 2, `use_hacc = false` does not harm accuracy.

    rabitqlib::SplitBatchQuery<float> processed_query(
        rotated_query.data(), dim, bits - 1, rabitqlib::METRIC_L2, true
    );

    // The factors should be set according to the centroid vector.
    // For ANN, this is preprocessed for every center vector when a query comes.
    processed_query.set_g_add(
        std::sqrt(rabitqlib::euclidean_sqr(rotated_query.data(), centroid.data(), dim)),
        rabitqlib::dot_product(rotated_query.data(), centroid.data(), dim)
    );
```

--------------------------------

### RaBitQ Test Directory Structure

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/tests/README.md

Overview of the RaBitQ test directory structure, including CMakeLists.txt for test configuration, main.cpp for the test runner, and subdirectories for utilities, unit tests, integration tests, and benchmarks.

```text
tests/
├── CMakeLists.txt              # Automatic test discovery & suite configuration
├── main.cpp                    # Test runner entry point
├── common/                     # Test utilities and helpers
│   ├── test_data.hpp           # Test data generation utilities
│   ├── test_data.cpp
│   └── test_helpers.hpp       # Custom assertions and helpers
├── unit/                       # Unit tests (auto-discovered)
├── integration/                # Integration tests (auto-discovered)
└── benchmark/                  # Performance benchmarks (to be added)
```

--------------------------------

### Index Construction - Command Line

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/index/ivf.md

Command-line interface for constructing the IVF index by partitioning raw data vectors.

```APIDOC
## Index Construction - Command Line

### Description
This command initiates the index construction process by running KMeans clustering on raw data vectors to partition them into buckets.

### Method
Shell Command

### Endpoint
N/A

### Parameters
#### Path Parameters
- **`/path/to/raw/data`** (string) - Required - Path to the raw data vectors in `.fvecs` format.
- **`number_of_clusters`** (integer) - Required - The desired number of clusters for KMeans.
- **`/path/to/output/centroids`** (string) - Required - Path to save the computed centroids.
- **`/path/to/output/cluster_ids`** (string) - Required - Path to save the cluster IDs for each data vector.
- **`distance_metric`** (string) - Required - The distance metric to use for clustering (e.g., `l2`).

### Request Example
```shell
python python/ivf.py /data/sift/sift_base.fvecs \
                     4096 \
                     /data/sift/sift_centroids_4096_l2.fvecs \
                     /data/sift/sift_clusterids_4096_l2.ivecs \
                     l2
```
```

--------------------------------

### Perform Scalar Quantization in C++

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/quick_start.md

Demonstrates scalar quantization and reconstruction using the RaBitQ library. Requires including 'quantization/rabitq.hpp' and initializing a config struct for the faster quantization variant.

```cpp
#include <random>
#include <vector>

#include "quantization/rabitq.hpp"

int main() {
    size_t dim = 128;

    std::vector<float> vector(dim);
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::normal_distribution<float> dist(0, 1);

    // generate a random vector
    for (size_t i = 0; i < dim; ++i) {
        vector[i] = dist(gen);
    }

    size_t bits = 8;                  // num of bits for total code
    std::vector<uint32_t> code(dim);  // code
    float delta;                      // delta for scalar quantization
    float vl;                         // lower value for scalar quantization

    // scalar quantization
    rabitqlib::quant::quantize_scalar(vector.data(), dim, bits, code.data(), delta, vl);

    // faster version, must init a config struct first
    rabitqlib::quant::RabitqConfig config = rabitqlib::quant::faster_config(dim, bits);
    rabitqlib::quant::quantize_scalar(
        vector.data(), dim, bits, code.data(), delta, vl, config
    );

    // reconstruct  
    float * reconstructed_data = new float [padded_dim];
    rabitqlib::quant::reconstruct_vec(code, delta, vl, padded_dim, reconstructed_data);

    return 0;
}
```

--------------------------------

### Initialize RaBitQ Rotator (Matrix)

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/rabitq/rotator.md

Initializes a rotator using the Random Orthogonal Transformation method. Vectors are padded to the smallest multiple of 64. Storage is O(D*D) floats, and time complexity is O(D * D).

```cpp
rabitqlib::Rotator<float>* rotator = rabitqlib::choose_rotator<float>(
    dim = dim, 
    RotatorType type = RotatorType::MatrixRotator);
```

--------------------------------

### Querying with Split Vectors

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/rabitq/quantizer.md

Demonstrates how to preprocess queries and compute estimated distances using split binary codes.

```cpp
... 
    size_t dim = 768;  // the dimensionality
    size_t bits = 5;   // the bit-width of DATA vectors
    std::vector<float> rotated_query(dim);

    // the config of fast quantizer is necessary for preprocessing queries
    rabitqlib::quant::RabitqConfig config = rabitqlib::quant::faster_config(dim, bits);

    rabitqlib::SplitSingleQuery<float> processed_query(
        rotated_query.data(), dim, bits - 1, config, rabitqlib::METRIC_L2
    );

    // set factors for distance estimation.
    // In ANN the factors are precomputed when a query comes.
    float norm =
        rabitqlib::euclidean_sqr(rotated_query.data(), centroid.data(), dim);
    float error = rabitqlib::dot_product(rotated_query.data(), centroid.data(), dim);

    // Compute estimated distances based on binary codes
    float ip_x0_qr;
    float est_dist;
    float low_dist;

    split_single_estdist(
        bin_data.data(), processed_query, dim, ip_x0_qr, est_dist, low_dist, -norm, error
    );

    // the kernel of computing inner product between compact codes and query vectors
    auto ip_func = rabitqlib::select_excode_ipfunc(bits - 1);

    // Compute more accurate distance based on full codes.
    float est_dist_ex;
    float low_dist_ex;
    float ip_x0_qr_ex;

    split_single_fulldist(
        bin_data.data(),
        ex_data.data(),
        ip_func,
        processed_query,
        dim,
        bits - 1,
        est_dist_ex,
        low_dist_ex,
        ip_x0_qr_ex,
        -norm,
        error
    );
```

--------------------------------

### Random Rotation Initialization and Application

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Shows how to initialize and use two types of rotators (FFHT + Kac's Walk and Random Orthogonal Transformation) for vector preprocessing. Remember to deallocate rotator objects after use.

```cpp
#include "utils/rotator.hpp"
#include <vector>

int main() {
    size_t dim = 768;

    // Initialize rotator - Version 1: FFHT + Kac's Walk (default)
    // Storage: 4D bits, Time: O(D * log D)
    rabitqlib::Rotator<float>* rotator = rabitqlib::choose_rotator<float>(
        dim,
        rabitqlib::RotatorType::FhtKacRotator
    );

    // Initialize rotator - Version 2: Random Orthogonal Transformation
    // Storage: D * D floats, Time: O(D * D)
    rabitqlib::Rotator<float>* matrix_rotator = rabitqlib::choose_rotator<float>(
        dim,
        rabitqlib::RotatorType::MatrixRotator
    );

    // Apply rotation to a vector
    std::vector<float> x(dim);
    std::vector<float> x_rotated(dim);

    // Fill x with data...

    rotator->rotate(x.data(), x_rotated.data());

    delete rotator;
    delete matrix_rotator;
    return 0;
}
```

--------------------------------

### Construct HNSW index with RaBitQ

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Load data and build an HNSW index using RaBitQ quantization. The faster_quant flag can be enabled to accelerate the construction process.

```cpp
#include <cstdint>
#include <iostream>
#include "index/hnsw/hnsw.hpp"
#include "utils/io.hpp"
#include "utils/stopw.hpp"

using PID = rabitqlib::PID;
using index_type = rabitqlib::hnsw::HierarchicalNSW;
using data_type = rabitqlib::RowMajorArray<float>;
using gt_type = rabitqlib::RowMajorArray<uint32_t>;

int main() {
    // Load data files
    data_type data;
    data_type centroids;
    gt_type cluster_id;

    rabitqlib::load_vecs<float, data_type>("deep1M/deep1M_base.fvecs", data);
    rabitqlib::load_vecs<float, data_type>("deep1M/deep1M_centroids_16.fvecs", centroids);
    rabitqlib::load_vecs<uint32_t, gt_type>("deep1M/deep1M_clusterids_16.ivecs", cluster_id);

    size_t num_points = data.rows();
    size_t dim = data.cols();
    size_t total_bits = 5;   // 1+4 bits quantization
    size_t m = 16;           // Degree bound for HNSW
    size_t ef = 100;         // ef for indexing
    size_t random_seed = 100;
    rabitqlib::MetricType metric_type = rabitqlib::METRIC_L2;

    // Initialize HNSW index
    auto* hnsw = new rabitqlib::hnsw::HierarchicalNSW(
        num_points, dim, total_bits, m, ef, random_seed, metric_type
    );

    rabitqlib::StopW stopw;

    // Construct index (faster_quant=true for faster quantization)
    hnsw->construct(
        centroids.rows(),
        centroids.data(),
        num_points,
        data.data(),
        cluster_id.data(),
        0,      // num_threads (0 = auto)
        true    // faster quantization
    );

    float total_time = stopw.get_elapsed_micro() / 1e6;
    std::cout << "Indexing time = " << total_time << "s\n";

    // Save index
    hnsw->save("deep1M/deep1M_c16_b5.index");
    std::cout << "Index saved\n";

    delete hnsw;
    return 0;
}
```

--------------------------------

### Construct HNSW Index in C++

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/docs/docs/quick_start.md

Loads raw data, centroids, and cluster IDs to build and save an HNSW index. Requires compiled RabitQ library headers and utility files.

```cpp
#include <cstdint>
#include <iostream>

#include "index/hnsw/hnsw.hpp"
#include "utils/io.hpp"
#include "utils/stopw.hpp"

using PID = rabitqlib::PID;
using index_type = rabitqlib::hnsw::HierarchicalNSW;
using data_type = rabitqlib::RowMajorArray<float>;
using gt_type = rabitqlib::RowMajorArray<uint32_t>;

int main(int argc, char* argv[]) {
    if (argc < 8) {
        std::cerr << "Usage: " << argv[0]
                  << " <arg1> <arg2> <arg3> <arg4> <arg5> <arg6> <arg7> <arg8>\n"
                  << "arg1: path for data file, format .fvecs\n"
                  << "arg2: path for centroids file, format .fvecs\n"
                  << "arg3: path for cluster ids file, format .ivecs\n"
                  << "arg4: m (degree bound) for hnsw\n"
                  << "arg5: ef for indexing \n"
                  << "arg6: total number of bits for quantization\n"
                  << "arg7: path for saving index\n"
                  << "arg8: metric type (\"l2\" or \"ip\")\n"
                  << "arg9: if use faster quantization (\"true\" or \"false\"), false by "
                     "default\n";
        exit(1);
    }

    char* data_file = argv[1];
    char* centroid_file = argv[2];
    char* cid_file = argv[3];
    size_t m = atoi(argv[4]);
    size_t ef = atoi(argv[5]);
    size_t total_bits = atoi(argv[6]);
    char* index_file = argv[7];

    rabitqlib::MetricType metric_type = rabitqlib::METRIC_L2;
    if (argc > 8) {
        std::string metric_str(argv[8]);
        if (metric_str == "ip" || metric_str == "IP") {
            metric_type = rabitqlib::METRIC_IP;
        }
    }
    if (metric_type == rabitqlib::METRIC_IP) {
        std::cout << "Metric Type: IP\n";
    } else if (metric_type == rabitqlib::METRIC_L2) {
        std::cout << "Metric Type: L2\n";
    }

    bool faster_quant = false;
    if (argc > 9) {
        std::string faster_str(argv[9]);
        if (faster_str == "true") {
            faster_quant = true;
            std::cout << "Using faster quantize for indexing...\n";
        }
    }

    data_type data;
    data_type centroids;
    gt_type cluster_id;

    rabitqlib::load_vecs<float, data_type>(data_file, data);
    rabitqlib::load_vecs<float, data_type>(centroid_file, centroids);
    rabitqlib::load_vecs<uint32_t, gt_type>(cid_file, cluster_id);

    size_t num_points = data.rows();
    size_t dim = data.cols();

    size_t random_seed = 100;  // by default 100
    auto* hnsw = new rabitqlib::hnsw::HierarchicalNSW(
        num_points, dim, total_bits, m, ef, random_seed, metric_type
    );

    rabitqlib::StopW stopw;
    stopw.reset();

    hnsw->construct(
        centroids.rows(),
        centroids.data(),
        num_points,
        data.data(),
        cluster_id.data(),
        0,
        faster_quant
    );

    float total_time = stopw.get_elapsed_micro();
    total_time /= 1e6;

    std::cout << "indexing time = " << total_time << "s" << '\n';
    hnsw->save(index_file);

    std::cout << "index saved..." << '\n';

    return 0;
}
```

--------------------------------

### Construct IVF Index with C++

Source: https://context7.com/vectordb-ntu/rabitq-library/llms.txt

Constructs an Inverted File (IVF) index using RaBitQ. This C++ code loads data, centroids, and cluster IDs to build the index, then saves it to disk. Ensure correct file paths for data and centroids.

```cpp
#include <cstdint>
#include <iostream>
#include "defines.hpp"
#include "index/ivf/ivf.hpp"
#include "utils/io.hpp"
#include "utils/stopw.hpp"

using PID = rabitqlib::PID;
using index_type = rabitqlib::ivf::IVF;
using data_type = rabitqlib::RowMajorArray<float>;
using gt_type = rabitqlib::RowMajorArray<uint32_t>;

int main() {
    // Load data files
    data_type data;
    data_type centroids;
    gt_type cids;

    rabitqlib::load_vecs<float, data_type>("deep1M/deep1M_base.fvecs", data);
    rabitqlib::load_vecs<float, data_type>("deep1M/deep1M_centroids_4096.fvecs", centroids);
    rabitqlib::load_vecs<PID, gt_type>("deep1M/deep1M_clusterids_4096.ivecs", cids);

    size_t num_points = data.rows();
    size_t dim = data.cols();
    size_t k = centroids.rows();
    size_t total_bits = 4;  // 1+3 bits quantization

    std::cout << "Data loaded: N=" << num_points << ", DIM=" << dim << '\n';

    // Initialize and construct IVF index
    rabitqlib::StopW stopw;
    index_type ivf(num_points, dim, k, total_bits);

    // faster_quant=true for faster quantization with near-optimal accuracy
    ivf.construct(data.data(), centroids.data(), cids.data(), true);

    float minutes = stopw.get_elapsed_mili() / 1000 / 60;
    std::cout << "IVF constructed in " << minutes << " minutes\n";

    // Save index to disk
    ivf.save("deep1M/deep1M_rabitqlib_ivf_4.index");

    return 0;
}

```

--------------------------------

### Define Test Executable and Link Libraries

Source: https://github.com/vectordb-ntu/rabitq-library/blob/main/tests/CMakeLists.txt

This section defines the main test executable 'rabitq_tests' and links it against Google Test, the rabitq library headers, and the pthread library. Ensure 'rabitq_headers' is correctly defined elsewhere in the CMake configuration.

```cmake
add_executable(rabitq_tests
    ${COMMON_SRCS}
    ${UNIT_TESTS}
    ${INTEG_TESTS}
)

target_link_libraries(rabitq_tests
    gtest
    gtest_main           
    rabitq_headers
    pthread
)
```