Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk)

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Similarity search problems in high-dimensional data arise in many areas of computer science such as data bases, image analysis, machine learning, and natural language processing. One of the most prominent problems is finding the k nearest neighbors of a data point q 2 Rd in a large set of data points S Rd, under same distance measure such as Euclidean distance. In contrast to lower
dimensional settings, we do not know of worst-case efficient data structures for such search problems in high-dimensional data, i.e., data structures that are faster than a linear scan through the data set. However, there is a rich body of (often heuristic) approaches that solve nearest neighbor search problems much faster than such a scan on many real-world data sets. As a necessity, the term solve
means that these approaches give approximate results that are close to the true k-nearest neighbors.
In this talk, we survey recent approaches to nearest neighbor search and related problems.
The talk consists of three parts: (1) What makes nearest neighbor search difficult? (2) How do
current state-of-the-art algorithms work? (3) What are recent advances regarding similarity search
on GPUs, in distributed settings, or in external memory?
Original languageEnglish
Title of host publication18th International Symposium on Experimental Algorithms (SEA 2020)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication date2020
Article number1
Publication statusPublished - 2020
EventInternational Symposium on Experimental Algorithms (SEA 2020) -
Duration: 12 Jun 2020 → …
Conference number: 18


ConferenceInternational Symposium on Experimental Algorithms (SEA 2020)
Period12/06/2020 → …
SeriesLeibniz International Proceedings in Informatics (LIPIcs)


  • Similarity search
  • High-dimensional data
  • Nearest neighbor search
  • Euclidean distance
  • Approximate algorithms


Dive into the research topics of 'Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk)'. Together they form a unique fingerprint.

Cite this