Knowledge Graph Embeddings are often used to bridge symbolic representations of Knowledge Graphs and the sub-symbolic representations that modern Machine Learning algorithms operate on. While embedding models provide users with a mapping from symbolic entities and relations to their sub-symbolic representations, a mapping in the opposite direction typically relies on a nearest neighbor search. Due to the computational complexity of this task, a plethora of approaches for approximate nearest neighbor search have been developed. The majority of these approaches outperform the default brute-force-based approach while providing a high recall. However, previous evaluations of these approaches focused on image data and word embeddings but did not consider Knowledge Graph Embeddings. We close this gap by carrying out a detailed comparison of 22 Approximate Nearest Neighbor Search systems on 16 datasets. In contrast to the state of the art, we fine-tune each approach in each experiment by using Bayesian optimization to ensure the fairness of our experiments. Our results suggest that the overall performance of approaches with respect to runtime and recall is contingent upon the similarity measure used to compare embeddings. Our source code, datasets and results are available at https://github.com/MichaelRoeder/ann-benchmarks/tree/main .