Similarity Search in Metric Spaces with Weighted Multi-Focal Regions: Using the Ambit Region Type to Improve the Performance of the SSS-Tree

Abstract

Metrisk indeksering er et nyttig verktøy for å søke i store datamengder. For å lage metriske indekser, kan man dele datamengden inn i klynger. De fleste eksisterende klyngebaserte metriske indekseringsmetoder, blant disse SSS-treet, bruker regioner med bare ett fokus. Vi testet ytelsen til en modifisert versjon av SSS-treet, kalt WSSS-treet, som bruker regioner med flere fokus (ambits). Formen til disse regionene er laget ved å trene dem til å unngå et sett med eksempelspørringer ved å gi fokusene ulik vekting. WSSS-treet presterte vesentlig bedre enn SSS-treet på spørringer fra én klynge, og noe bedre på spørringer fra to klynger. På spørringer fra to klynger testet vi også en modifisert versjon av WSSS-treet, kalt W2SSS-treet, som presterte vesentlig bedre enn både SSS-treet og WSSS-treet. Disse resultatene tyder på at å bruke regioner med flere vektete fokus (ambits) kan redusere antall avstandssammenligninger man trenger for å utføre en spørring hvis man på forhånd kan vite noe om fordelingen spørringene vil komme fra.

Similarity searching through metric indexing is an essential tool for retrieving data from large data sets. When creating metric indices, clustering can be used. Most existing clustering-based metric indexing methods, including the SSS-tree, use regions with one focus only. We tested the performance of a modified version of the SSS-tree, named the WSSS-tree, which uses multi-focal regions, so-called ambits, trained to avoid a set of example queries. The WSSS-tree significantly outperformed the SSS-tree when applied to queries from one cluster, and had a slight advantage when applied to queries from two clusters. For queries from two clusters, we also tested a modified version of the WSSS-tree, named W2SSS-tree, which significantly outperformed both the WSSS-tree and SSS-tree. These results suggest that using the ambit region type with multiple weighted foci in metric indices can reduce the number of distance calculations needed to search for a query if one knows the distribution that the queries will come from.