GVS

KO | EN

gitlite — search

#python #golang #android #rust #deep-learning #linux #macos #nodejs #java #awesome #cli #awesome-list #security #openai

(★ 23)

An Experimental Evaluation of the State-of-the-Art Graph-Based Vector Search Methods and Techniques

GVS 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art
[📄 Read the paper on arXiv](https://arxiv.org/pdf/2502.05575)
## Introduction
Collections of vector data often expand to billions of vectors with thousands of dimensions, thereby escalating the complexity of analysis. Similarity search serves as the linchpin for numerous critical analytical tasks. Graph-based similarity search has recently emerged as the preferred method for analytical tasks that do not necessitate theoretical guarantees on the quality of answers.
In this survey, we undertake a thorough evaluation of twelve state-of-the-art in-memory graph-based similarity search methods :

Furthermore, we present a survey delineating the chronological evolution of these methods and evaluate their key design decisions, encompassing Seed Selection (SS) and Neighborhood Diversification (ND). This repository contains the code utilized to evaluate different design choices for SS and ND, and the indexing and search performance of the twelve SotA approaches. For each method, we include parametrization details and any changes done to the original code bases to ensure a fair comparison.

## Datasets
We use the following four real datasets covering a variety of domains from deep network embeddings, computer vision, neuroscience and seismology: (i) Deep contains 1 billion vectors of 96 dimensions extracted from the last layers of a convolutional
neural network; (ii) Sift consists of 1 billion SIFT vectors of size 128 representing image feature descriptions; (iii) SALD contains neuroscience MRI data and includes 200 million data series of size 128; (iv) Seismic  contains 100 million data series of size 256 representing earthquake recordings at seismic stations worldwide.

### Evaluation of Dataset Hardness
We employ both Local Intrinsic Dimensionality (LID) and Local Relative Contrast (LRC) to evaluate and compare the hardness of each dataset, using the relative set of queries. We provide script to eventually evaluate the hardness using random datapoint from the given dataset.

## ND/SS experiments
ND and SS experiments code is based on [nmslib/hnswlib code](https://github.com/nmslib/hnswlib)  for constructing insertion-based graphs with various ND approaches and executing searches using multiple SS techniques.

### Usage

### Prerequisites

- GCC 4.9+ with OpenMP
- CMake 3.5+

### Compilation on Linux
```shell
mkdir Release
cd Release
cmake -DCMAKE_BUILD_TYPE=Release ..
make
```

### Building
```shell
./Release/WTSS --dataset path/dataset.bin --dataset-size n --index-path path/indexdirname/ --timeseries-size dim  --K maxoutdegree  --L beamwidth --mode 0  --nd nd_type --prune prune_value --ep ep_type
```

Where:
- `path/dataset.bin` is the absolute path to the dataset binary file.
- `n` is the dataset size.
- `path/indexdirname/` is the absolute path where the index will be stored (the index folder should not already exist).
- `dim` is the dimension.
- `maxoutdegree` is the maximum outdegree for nodes during graph construction.
- `beamwidth` is the beamwidth during candidate neighbor search.
- `nd_type` is the type of ND method to use: 0 for RND, 1 for RRND, 2 for MOND and 3 for NoND.
- `prune_value` is the value used during ND. For RRND, a value between 1.3-1.5 is recommended; for MOND, 60 yields the best results.
- `ep` is the SS method to use during construction, with 0 for StackedNSW and 3 for KSREP.

#### ND Pruning Ratio
To output the ND pruning ratio during graph construction, uncomment the definition `STATSND` in `./include/PTK.h` lines 12, 13, 14.

#### Construction NDC
To output the number of distance calculations during indexing, uncomment the definition `DC_IDX` in `./include/PTK.h` lines 8, 9, 10.

### Search
```shell
./Release/WTSS --queries path/queries.bin --queries-size n --index-path path/indexdirname/ --timeseries-size dim  --K k  --L beamwidth --mode 1 --ep ep_type
```
Where:
- `path/queries.bin` is the absolute path to the query set binary file.
- `n` is the query set size.
- `k` is the number of NN results desired.
- `beamwidth` is the size of the priority queue used during beam search, with `beamwidth` >= `k`.
- `ep_type` is the type of SS method to use during search, with 0 for StackedNSW, 1 for medoid, 2 for SFREP, 3 for KSREP, and 4 for KDTrees.

## Supplementary Material 
Our supplementary material includes additional analysis that couldn't fit into the paper. We provide theoretical proofs of approximation for ND approaches and an empirical analysis of the theoretical complexity of the beam search algorithm. We also evaluate the performance of single priority queue vs. double priority queue beam search heuristics employed in NMSLIB/HNSW and conduct an empirical study of parameter tuning for GANNS using HNSW as the base case.

## Reference

Please cite our work in your publications if it helps your research:

```
@article{10.1145/3709693,
author = {Azizi, Ilias and Echihabi, Karima and Palpanas, Themis},
title = {Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art},
year = {2025},
url = {https://doi.org/10.1145/3709693},
doi = {10.1145/3709693},
journal = {Proc. ACM Manag. Data},
month = feb,
articleno = {43},
numpages = {31},
}
```

GVS

GVS 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

GVS

GVS 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README