DEG: Fast Approximate Nearest Neighbor Search

The Dynamic Exploration Graph (DEG) is a graph-based algorithm for approximate nearest neighbor search (ANNS). It indexes both static and dynamic datasets using three algorithms: incremental extension, continuous edge optimization, and vertex deletion. The resulting graph demonstrates high efficiency in terms of queries per second relative to the achieved recall rate. DEG provides state-of-the-art performance for both indexed and unindexed queries (where the query is not part of the index).

For a short introduction on how to use deglib for vector search, see our Python Examples.

• [2024/05/01] Our paper An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval is accepted by ICMR2024 as oral presentation
• [2023/12/02] New continuous refining Exploration Graph (crEG) containing a more efficient and thread-safe way to extend DEG. Currently found in the crEG branch of this repository.
• [2023/07/19] First version of Dynamic Exploration Graph is out! For more details please refere to our paper: Fast Approximate nearest neighbor search with the Dynamic Exploration Graph using continuous refinement

In order to reproduce the results in our papers, please visit the corresponding github branch.

• crEG branch for "An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval"
• arxiv branch for "Fast Approximate nearest neighbor search with the Dynamic Exploration Graph using continuous refinement"

*NOTE: All experiments where conduced single threaded on a Ryzen 2700x CPU, operating at a constant core clock speed of 4GHz, and 64GB of DDR4 memory running at 2133MHz.

Approximate Nearest Neighbor Search

Exploratory Search (indexed queries)

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

@article{Hezel2023,
  author = {Hezel, Nico and Barthel, Uwe Kai and Schall, Konstantin and Jung, Klaus},
  ee = {https://arxiv.org/abs/2307.10479},
  journal = {CoRR},
  title = {Fast Approximate nearest neighbor search with the Dynamic Exploration Graph using continuous refinement.},
  volume = {abs/2307.10479},
  year = 2023
}