Parameter-based online optimization in metric indexing using Bentley-Saxe transformations

Abstract

Metrisk indeksering er et viktig verktøy for å kunne søke i store datamengder. Mange algoritmer og datastrukturer i dette feltet bruker en form for parameter i indekseringsprossessen. Det optimale valget for denne parameteren er i mange tilfeller avhengig av datasettet som blir indeksert. Denne rapporten introduserer BS-OPTPARAM, en generell metode for å finne den optimale parameteren for dynamiske datastrukturer brukt i metrisk indeksering. Rapporten beskriver og tester fire forskjellige algoritmer som bruker BS-OPTPARAM metoden. Det blir presentert noen lovende resultater hvor algoritmene presterer bedre enn forventet, som tyder på at BS-OPTPARAM er en nyttig metode for å løse problemet.

Metric indexing is an important tool when dealing with similarity searches of large datasets. Many of the algorithms and data structures in this area rely on some form of a parameter in the indexing process. The optimal choice for this parameter is often determined by the dataset that is being indexed, and choosing some non-optimal parameter will in some cases have a large impact on the performance of the index. This report introduces the BS-OPTPARAM, a general approach to finding the optimal parameter for dynamic metric indexing data structures that leverages Bentley-Saxe transformations. The paper also describes and tests four different algorithms that use the BS-OPTPARAM approach. Some promising results are presented, showing some cases where the algorithms perform better than expected, and indicating that the BS-OPTPARAM is a useful tool when solving this problem.