ITU

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

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

View graph of relations

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
Pages1:1–1:3
Article number1
DOIs
Publication statusPublished - 2020
EventInternational Symposium on Experimental Algorithms (SEA 2020) -
Duration: 12 Jun 2020 → …
Conference number: 18

Conference

ConferenceInternational Symposium on Experimental Algorithms (SEA 2020)
Nummer18
Periode12/06/2020 → …
SeriesLeibniz International Proceedings in Informatics (LIPIcs)
ISSN1868-8969

ID: 85506483