Overview

This repository is a concurrent dynamic approximate nearest neighbor search index built on the Microsoft DiskANN algorithm (commit #35f8cf7).

Commands

You can build the library and the python binding with with

python3 -m pip install --no-build-isolation -ve .

You may first need to install pybind11:

python3 -m pip install pybind11

If you get output saying pip is installing UNKNOWN, first run

python3 -m pip install setuptools --upgrade

You will also likely need to install the packages the original DiskANN needs:

sudo apt install make cmake g++ libaio-dev libgoogle-perftools-dev clang-format libboost-all-dev

and

sudo apt install libmkl-full-dev

You may also need to tell CMake where omp is installed in CMakeLists.txt by setting POSSIBLE_OMP_PATHS.

See the original readme (https://github.com/microsoft/DiskANN/tree/main#readme).

Experiment Code

Experiments are in concurrent_experiments. They can be run as e.g.

You can to configure the system in concurrent_experiments/utils.py. Parameters you can configure include the graph sparsity regularizer, graph degree limit, starting memory allocation, number of hyper-threads, and so on. To run experiments in batch, refer to concurrent_experiments/experiment_batch_runner.py. A sample batch experiment script is batch_run_experiment.sh.

To configure whether to use one or more algorithms proposed in our paper, please modify the compilation macro in src/index.cpp for now.

• LAYER_BASED_PATH_COMPRESSION corresponds to GuidedBridgeBuild.
• FIXES_DELETES_LOWER_LAYER corresponds to on-the-fly consolidation.
• MEMORY_COLLECTION corresponds to semi-lazy cleaning.

Datasets

The existing experiments expect the dataset to be downloaded in a folder named data in hdf5 format named as {dataset-name}-{dimension}-{metric}.hdf5. The hdf5 formatting is consistent with the ANN benchmarks project: in the hdf5 file, indexed data points are under the "train" dataset, and test data points are under the "test" dataset. Since almost all datasets do not come with sliding window update ground truths for the queries, concurrent_experiments/test_rolling_update.get_or_create_rolling_update_ground_truth computes and stores the ground truth for the dataset being tested on.

For the current manuscript, we conducted experiments on 7 datasets of different nature on various scales. The datasets used are listed below:

• RedCaps was embedded with CLIP and HuffPost was embedded with OpenAI's text-embedding-3 API. Both are sorted in timestamp to represent a realistic distribution shift.
• The script for generating Adversarial can be found in concurrent_experiments/adversarial-dataset-gen.py.

Paper

This repository is the artifact for the manuscript CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search.

Current Results

Acknowledgement

Redacted during the review period for anonymity purposes.