Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search

Elias Jääsaari, Ville Hyvönen, Teemu Roos

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Kuvaus

Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications. However, current indexing methods feature several hyperparameters that need to be tuned to reach an acceptable accuracy–speed trade-off. A grid search in the parameter space is often impractically slow due to a time-consuming index-building procedure. Therefore, we propose an algorithm for automatically tuning the hyperparameters of indexing methods based on randomized space-partitioning trees. In particular, we present results using randomized k-d trees, random projection trees and randomized PCA trees. The tuning algorithm adds minimal overhead to the index-building process but is able to find the optimal hyperparameters accurately. We demonstrate that the algorithm is significantly faster than existing approaches, and that the indexing methods used are competitive with the state-of-the-art methods in query time while being faster to build.
Alkuperäiskielienglanti
OtsikkoAdvances in Knowledge Discovery and Data Mining : 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II
Sivumäärä13
JulkaisupaikkaCham
KustantajaSpringer
Julkaisupäivä17 huhtikuuta 2019
Sivut590-602
ISBN (painettu)978-3-030-16144-6
ISBN (elektroninen)978-3-030-16145-3
DOI - pysyväislinkit
TilaJulkaistu - 17 huhtikuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaPacific-Asia Conference on Knowledge Discovery and Data Mining 2019 - Parisian Macao, Macao, Kiina
Kesto: 14 huhtikuuta 201917 huhtikuuta 2019
Konferenssinumero: 23
http://pakdd2019.medmeeting.org/en

Julkaisusarja

NimiLecture Notes in Artificial Intelligence
KustantajaSpringer
Vuosikerta11440
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Lainaa tätä

Jääsaari, E., Hyvönen, V., & Roos, T. (2019). Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search. teoksessa Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II (Sivut 590-602). (Lecture Notes in Artificial Intelligence; Vuosikerta 11440). Cham: Springer. https://doi.org/10.1007/978-3-030-16145-3_46
Jääsaari, Elias ; Hyvönen, Ville ; Roos, Teemu. / Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search. Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II. Cham : Springer, 2019. Sivut 590-602 (Lecture Notes in Artificial Intelligence).
@inproceedings{c41fb03ebca24cc3971580437e32ba4d,
title = "Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search",
abstract = "Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications. However, current indexing methods feature several hyperparameters that need to be tuned to reach an acceptable accuracy–speed trade-off. A grid search in the parameter space is often impractically slow due to a time-consuming index-building procedure. Therefore, we propose an algorithm for automatically tuning the hyperparameters of indexing methods based on randomized space-partitioning trees. In particular, we present results using randomized k-d trees, random projection trees and randomized PCA trees. The tuning algorithm adds minimal overhead to the index-building process but is able to find the optimal hyperparameters accurately. We demonstrate that the algorithm is significantly faster than existing approaches, and that the indexing methods used are competitive with the state-of-the-art methods in query time while being faster to build.",
keywords = "113 Computer and information sciences",
author = "Elias J{\"a}{\"a}saari and Ville Hyv{\"o}nen and Teemu Roos",
year = "2019",
month = "4",
day = "17",
doi = "10.1007/978-3-030-16145-3_46",
language = "English",
isbn = "978-3-030-16144-6",
series = "Lecture Notes in Artificial Intelligence",
publisher = "Springer",
pages = "590--602",
booktitle = "Advances in Knowledge Discovery and Data Mining",
address = "International",

}

Jääsaari, E, Hyvönen, V & Roos, T 2019, Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search. julkaisussa Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II. Lecture Notes in Artificial Intelligence, Vuosikerta 11440, Springer, Cham, Sivut 590-602, Pacific-Asia Conference on Knowledge Discovery and Data Mining 2019, Macao, Kiina, 14/04/2019. https://doi.org/10.1007/978-3-030-16145-3_46

Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search. / Jääsaari, Elias; Hyvönen, Ville; Roos, Teemu.

Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II. Cham : Springer, 2019. s. 590-602 (Lecture Notes in Artificial Intelligence; Vuosikerta 11440).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

TY - GEN

T1 - Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search

AU - Jääsaari, Elias

AU - Hyvönen, Ville

AU - Roos, Teemu

PY - 2019/4/17

Y1 - 2019/4/17

N2 - Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications. However, current indexing methods feature several hyperparameters that need to be tuned to reach an acceptable accuracy–speed trade-off. A grid search in the parameter space is often impractically slow due to a time-consuming index-building procedure. Therefore, we propose an algorithm for automatically tuning the hyperparameters of indexing methods based on randomized space-partitioning trees. In particular, we present results using randomized k-d trees, random projection trees and randomized PCA trees. The tuning algorithm adds minimal overhead to the index-building process but is able to find the optimal hyperparameters accurately. We demonstrate that the algorithm is significantly faster than existing approaches, and that the indexing methods used are competitive with the state-of-the-art methods in query time while being faster to build.

AB - Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications. However, current indexing methods feature several hyperparameters that need to be tuned to reach an acceptable accuracy–speed trade-off. A grid search in the parameter space is often impractically slow due to a time-consuming index-building procedure. Therefore, we propose an algorithm for automatically tuning the hyperparameters of indexing methods based on randomized space-partitioning trees. In particular, we present results using randomized k-d trees, random projection trees and randomized PCA trees. The tuning algorithm adds minimal overhead to the index-building process but is able to find the optimal hyperparameters accurately. We demonstrate that the algorithm is significantly faster than existing approaches, and that the indexing methods used are competitive with the state-of-the-art methods in query time while being faster to build.

KW - 113 Computer and information sciences

U2 - 10.1007/978-3-030-16145-3_46

DO - 10.1007/978-3-030-16145-3_46

M3 - Conference contribution

SN - 978-3-030-16144-6

T3 - Lecture Notes in Artificial Intelligence

SP - 590

EP - 602

BT - Advances in Knowledge Discovery and Data Mining

PB - Springer

CY - Cham

ER -

Jääsaari E, Hyvönen V, Roos T. Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search. julkaisussa Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II. Cham: Springer. 2019. s. 590-602. (Lecture Notes in Artificial Intelligence). https://doi.org/10.1007/978-3-030-16145-3_46