Abstract
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?
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?
| Originalsprog | Engelsk |
|---|---|
| Titel | 18th International Symposium on Experimental Algorithms (SEA 2020) |
| Forlag | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |
| Publikationsdato | 2020 |
| Sider | 1:1–1:3 |
| Artikelnummer | 1 |
| DOI | |
| Status | Udgivet - 2020 |
| Begivenhed | International Symposium on Experimental Algorithms (SEA 2020) - Varighed: 12 jun. 2020 → … Konferencens nummer: 18 |
Konference
| Konference | International Symposium on Experimental Algorithms (SEA 2020) |
|---|---|
| Nummer | 18 |
| Periode | 12/06/2020 → … |
| Navn | Leibniz International Proceedings in Informatics (LIPIcs) |
|---|---|
| ISSN | 1868-8969 |
Emneord
- Similarity search
- High-dimensional data
- Nearest neighbor search
- Euclidean distance
- Approximate algorithms