2026-07-25T00:57:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12075 2024-03-06T10:49:17Z ddc:004 open_access

Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk) Aumüller, Martin Nearest neighbor search Benchmarking 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 ∈ ℝ^d in a large set of data points S ⊂ ℝ^d, 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? Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Aumüller 2020 Is Part Of LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2020.1 urn:nbn:de:0030-drops-120751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.1 eng https://creativecommons.org/licenses/by/3.0/legalcode