Skip to content

Latest commit

 

History

History
38 lines (28 loc) · 1.22 KB

README.md

File metadata and controls

38 lines (28 loc) · 1.22 KB

[] Fudist: An efficient distance approximation tool to accelerate the search of approximate nearest neighbors

We benchmark the performance of the following algorithms w.r.t. the distance approximation part:

  1. ADSampling
  2. LSH-APG (LSH-pruning part)
  3. PQ
  4. OPQ
  5. PCA
  6. DWT

And we benchmark and combine many heuristic idea and engineering optimizations from SOTA papers. After that, we propose Fudist, the best tool for distance approximation and pruning in ANN search.

Prerequisites


Reproduction

The tested datasets are available at https://www.cse.cuhk.edu.hk/systems/hash/gqr/datasets.html.

  1. Download and preprocess the datasets. Detailed instructions can be found in ./data/README.md.

  2. Index the datasets. It could take several hours.

    # Index HNSW/HNSW+/HNSW++
    ./script/index_hnsw.sh
  3. Test the queries of the datasets. The results are generated in ./results/. Detailed configurations can be found in ./script/README.md.

    # Index HNSW/HNSW+/HNSW++
    ./script/search_hnsw.sh