crEG: An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval

The continuous refining Exploration Graph (crEG) is a graph-based approximate nearest neighbor search (ANNS) algorithm. It can index static data set using an incremental extension, a continuous edge optimization. The resulting graph is highly efficient in regards to the queries per seconds in relation to the received recall rate. crEG delivers state-of-the-art performance for indexed and unindexed queries (query is not part of the index).

For the four data set above crEG delievered the best ANNS and exploration efficiency amoung all the tested graph-based algorithms.

*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 and ideal start seed of for the graph search)

Statistics of the graphs used in the experiments

In order to reproduce our results please checkout the \cpp\ directory and its readme file for more information about the parameters settings of the graphs.

The provided continuous refining Exploration Graph are used in the experiments section of our paper.

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

@inproceedings{crEG,
  author = {Hezel, Nico and Barthel, Kai Uwe and Schall, Konstantin and Jung, Klaus},
  title = {An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval},
  year = 2024,
  booktitle = {Proc. International Conference on Multimedia Retrieval (ICMR’24)},
  ublisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  booktitle = {Proceedings of the 2024 International Conference on Multimedia Retrieval},
  location = {Phuket, Thailand},
  series = {ICMR '24}
}