An unbalanced approach to metric space searching

Proximity queries (the searching problem generalized beyond exact match) is mostly modeled as metric space. A metric space consists of a collection of objects and a distance function defined among them. The goal is to preprocess the data set (a slow procedure) to quickly answer proximity queries. Th...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Chávez, Edgar, Ludueña, Verónica, Reyes, Nora Susana
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2005
Materias:
Ciencias Informáticas
Unbalanced Approach
Algorithms
Metric Space Searching
Metrics
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/21087
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-21087
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Unbalanced Approach
Algorithms
Metric Space Searching
Metrics
spellingShingle Ciencias Informáticas
Unbalanced Approach
Algorithms
Metric Space Searching
Metrics
Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
An unbalanced approach to metric space searching
topic_facet Ciencias Informáticas
Unbalanced Approach
Algorithms
Metric Space Searching
Metrics
description Proximity queries (the searching problem generalized beyond exact match) is mostly modeled as metric space. A metric space consists of a collection of objects and a distance function defined among them. The goal is to preprocess the data set (a slow procedure) to quickly answer proximity queries. This problem have received a lot of attention recently, specially in the pattern recognition community. The Excluded Middle Vantage Point Forest (VP–forest) is a data structure designed to search in high dimensional vector spaces. A VP–forest is built as a collection of balanced Vantage Point Trees (VP–trees). In this work we propose a novel two-fold approach for searching. Firstly we extend the VP– forest to search in metric spaces, and more importantly we test a counterintuitive modification to the VP–tree, namely to unbalance it. In exact searching an unbalanced data structure perform poorly, and most of the algorithmic effort is directed to obtain a balanced data structure. The unbalancing approach is motivated by a recent data structure (the List of Clusters ) specialized in high dimensional metric space searches, which is an extremely unbalanced data structure (a linked list) outperforming other approaches.
format Objeto de conferencia
Objeto de conferencia
author Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
author_facet Chávez, Edgar
Ludueña, Verónica
Reyes, Nora Susana
author_sort Chávez, Edgar
title An unbalanced approach to metric space searching
title_short An unbalanced approach to metric space searching
title_full An unbalanced approach to metric space searching
title_fullStr An unbalanced approach to metric space searching
title_full_unstemmed An unbalanced approach to metric space searching
title_sort unbalanced approach to metric space searching
publishDate 2005
url http://sedici.unlp.edu.ar/handle/10915/21087
work_keys_str_mv AT chavezedgar anunbalancedapproachtometricspacesearching
AT luduenaveronica anunbalancedapproachtometricspacesearching
AT reyesnorasusana anunbalancedapproachtometricspacesearching
AT chavezedgar unbalancedapproachtometricspacesearching
AT luduenaveronica unbalancedapproachtometricspacesearching
AT reyesnorasusana unbalancedapproachtometricspacesearching
bdutipo_str Repositorios
_version_ 1764820465406181378

Ejemplares similares