dc.contributor.advisor | Hetland, Magnus Lie | |
dc.contributor.author | Moe, Helene Haukås | |
dc.contributor.author | Carlsen, Signe Marie Øen | |
dc.date.accessioned | 2021-09-15T16:12:07Z | |
dc.date.available | 2021-09-15T16:12:07Z | |
dc.date.issued | 2020 | |
dc.identifier | no.ntnu:inspera:57320302:23976729 | |
dc.identifier.uri | https://hdl.handle.net/11250/2777817 | |
dc.description.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. | |
dc.description.abstract | 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. | |
dc.language | | |
dc.publisher | NTNU | |
dc.title | Similarity Search in Metric Spaces with Weighted Multi-Focal Regions: Using the Ambit Region Type to Improve the Performance of the SSS-Tree | |
dc.type | Master thesis | |