ITU

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

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

Standard

Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk). / Aumüller, Martin.

18th International Symposium on Experimental Algorithms (SEA 2020). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020. p. 1:1–1:3 1 (Leibniz International Proceedings in Informatics (LIPIcs)).

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

Harvard

Aumüller, M 2020, Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk). in 18th International Symposium on Experimental Algorithms (SEA 2020)., 1, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics (LIPIcs), pp. 1:1–1:3, International Symposium on Experimental Algorithms (SEA 2020), 12/06/2020. https://doi.org/10.4230/LIPIcs.SEA.2020.1

APA

Aumüller, M. (2020). Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk). In 18th International Symposium on Experimental Algorithms (SEA 2020) (pp. 1:1–1:3). [1] Schloss Dagstuhl--Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics (LIPIcs) https://doi.org/10.4230/LIPIcs.SEA.2020.1

Vancouver

Aumüller M. Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk). In 18th International Symposium on Experimental Algorithms (SEA 2020). Schloss Dagstuhl--Leibniz-Zentrum für Informatik. 2020. p. 1:1–1:3. 1. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.SEA.2020.1

Author

Aumüller, Martin. / Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk). 18th International Symposium on Experimental Algorithms (SEA 2020). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2020. pp. 1:1–1:3 (Leibniz International Proceedings in Informatics (LIPIcs)).

Bibtex

@inproceedings{5d9a349ec59c4405aa167911c335284d,
title = "Algorithm Engineering for High-Dimensional Similarity Search Problems (Invited Talk)",
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 lowerdimensional 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 solvemeans 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 docurrent state-of-the-art algorithms work? (3) What are recent advances regarding similarity searchon GPUs, in distributed settings, or in external memory?",
author = "Martin Aum{\"u}ller",
year = "2020",
doi = "10.4230/LIPIcs.SEA.2020.1",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik",
pages = "1:1–1:3",
booktitle = "18th International Symposium on Experimental Algorithms (SEA 2020)",
note = "International Symposium on Experimental Algorithms (SEA 2020), SEA 2020 ; Conference date: 12-06-2020",

}

RIS

TY - GEN

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

AU - Aumüller, Martin

N1 - Conference code: 18

PY - 2020

Y1 - 2020

N2 - 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 lowerdimensional 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 solvemeans 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 docurrent state-of-the-art algorithms work? (3) What are recent advances regarding similarity searchon GPUs, in distributed settings, or in external memory?

AB - 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 lowerdimensional 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 solvemeans 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 docurrent state-of-the-art algorithms work? (3) What are recent advances regarding similarity searchon GPUs, in distributed settings, or in external memory?

U2 - 10.4230/LIPIcs.SEA.2020.1

DO - 10.4230/LIPIcs.SEA.2020.1

M3 - Article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1:1–1:3

BT - 18th International Symposium on Experimental Algorithms (SEA 2020)

PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik

T2 - International Symposium on Experimental Algorithms (SEA 2020)

Y2 - 12 June 2020

ER -

ID: 85506483