FROG

This repository is forked from cuVS.

FROG is a GPU index for range-filtering approximate nearest-neighbor search. This repository contains the FROG shared library and three command-line programs:

• frog: builds, saves, loads, and searches a FROG index.
• pre: exact pre-filtering baseline using a range-restricted GPU brute-force search.
• post: CAGRA post-filtering baseline.

The shared library is installed as libfrog.so.

Requirements

• Linux
• CMake 3.26 or newer
• GCC 9.3 or newer
• CUDA Toolkit 12.9
• NVIDIA GPU with compute capability 8.0 or newer
• Conda or Mamba

Environment

conda env create -n frog -f conda/environment.yaml
conda activate frog

Build And Install

Build and install the library into the active Conda environment:

cmake -S cpp -B build/lib \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_INSTALL_PREFIX="$CONDA_PREFIX"
cmake --build build/lib -j"$(nproc)"
cmake --install build/lib

The default build targets the GPU architecture detected on the current machine. To build for a specific architecture, add a CMake option such as -DCMAKE_CUDA_ARCHITECTURES=86.

Build the command-line programs:

cmake -S frog_test -B build/apps \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_PREFIX_PATH="$CONDA_PREFIX"
cmake --build build/apps -j"$(nproc)"

The resulting executables are build/apps/frog, build/apps/pre, and build/apps/post.

Dataset Formats

The repository-local frog_test/data/example dataset demonstrates every input format:

Path	Contents and binary layout
base.fbin	10,000 base vectors with 128 dimensions, sorted in ascending order by attribute value. The file starts with two 32-bit unsigned integers (10000, 128), followed by a row-major 10000 x 128 array of float32 values.
query.fbin	10,000 query vectors with 128 dimensions, using the same two-uint32 header and row-major float32 layout as base.fbin.
range/17.bin	A headerless 10000 x 2 array of uint32 values. Row i stores the inclusive (lower_rank, upper_rank) constraint for query i, where each rank is a row position in the attribute-sorted base.fbin, from 0 through 9,999.
gt/17.bin	A headerless 10000 x 10 row-major array of int32 base-vector IDs containing the exact top-10 neighbors for each query within its range.

The number of range and ground-truth rows must equal the number of vectors in query.fbin.

Usage

frog <build|search|both> <config.json>
pre both <config.json>
post <plan|build|search|both> <config.json>

Example configurations are available in frog_test/conf_examples. Paths in these configurations are relative to the repository root, so run the commands below from that directory.

build/apps/frog both frog_test/conf_examples/frog_example.json
build/apps/pre both frog_test/conf_examples/pre_example.json
build/apps/post both frog_test/conf_examples/post_example.json

The frog configuration fields are:

Field	Meaning
algo	Algorithm selector; must be "frog" for the frog executable.
output_path	Directory in which indexes and benchmark results are written.
experiments	Non-empty array of experiments to run.
experiments[].name	Experiment name used in logs and output filenames.
experiments[].enable_half	If true, convert input float vectors to FP16 before building and searching; the input files remain float32 .fbin files. Defaults to false.
experiments[].base	Path to the base-vector .fbin file.
experiments[].qVector	Path to the query-vector .fbin file.
experiments[].qRange	Path to the query range file.
experiments[].gt	Path to the exact query ground-truth file used to calculate recall.
build_params.degree_max	Maximum graph degree. It must be a power of two and at least 16.
build_params.ef_construction	Candidate-pool size used while constructing and merging graph layers. Larger values generally trade build time and memory for graph quality.
build_params.invalid_num	Number of deepest segment-tree levels omitted from the stored graph hierarchy. Larger values produce fewer graph layers.
build_params.patience	Number of consecutive merge iterations without an improved cutoff distance before candidate expansion stops.
build_params.alpha_temp	Diversification coefficient used when pruning the temporary PG.
build_params.alpha_final	Diversification coefficient used when pruning the ENCs (expansion neighbor candidates).
build_params.beta_final	Parameter β of fusion distance.
build_params.gamma_final	Parameter γ of fusion distance.
search_params	Non-empty array of search settings; every entry is benchmarked.
search_params[].k	Number of neighbors returned per query.
search_params[].ef_search	Internal top-candidate queue size. Larger values generally improve recall at additional search cost.
search_params[].search_max	Maximum number of ENs (expansion neighbors) per expansion.

Reproduction Guide

We provide detailed instructions for obtaining and preprocessing the full experimental datasets. The datasets are not distributed in this repository because their licenses and redistribution terms differ, and some official sources do not explicitly permit redistribution of the original data or our prepared copies. To avoid misrepresenting third-party rights under this repository's Apache-2.0 license, please download each dataset from its official source below, comply with its terms, and convert the vectors, query ranges, and ground truth to the formats described in Dataset Formats.

Dataset	Scale	Dim	Source format	Official Link
Deep	10,000,000	96	Image	Yandex Deep1B/Deep10M benchmark
Audio	1,000,000	128	Audio	YouTube-8M download；
SIFT	1,000,000	128	Image	TexMex ANN datasets
Crawl	1,989,995	300	Text	fastText crawl-300d-2M vectors
GIST	1,000,000	960	Image	TexMex ANN datasets
Wiki	1,000,000	2048	Image & Text	WIT dataset and downloads

We use the YouTube Data API v3 to obtain the Audio attribute, i.e., the number of likes.

The experimental configurations are under frog_test/conf_examples/experiments_conf: update their common base, qVector, qRange, gt, and output_path values for your local dataset layout, then pass the selected JSON file to the corresponding executable and mode shown in Usage.