Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk)
Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review
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?
|Title of host publication||18th International Symposium on Experimental Algorithms (SEA 2020)|
|Publisher||Schloss Dagstuhl--Leibniz-Zentrum für Informatik|
|Publication status||Published - 2020|
|Event||International Symposium on Experimental Algorithms (SEA 2020) - |
Duration: 12 Jun 2020 → …
Conference number: 18
|Conference||International Symposium on Experimental Algorithms (SEA 2020)|
|Periode||12/06/2020 → …|
|Series||Leibniz International Proceedings in Informatics (LIPIcs)|