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

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:
Aportado por : SEDICI (UNLP) de Universidad Nacional de La Plata .
id I19-R120-10915-21087
record_format dspace
spelling I19-R120-10915-210872019-01-29T04:03:28Z http://sedici.unlp.edu.ar/handle/10915/21087 isbn:950-665-337-2 An unbalanced approach to metric space searching Chávez, Edgar Ludueña, Verónica Reyes, Nora Susana 2005-05 2005 2012-09-18T13:16:26Z en Ciencias Informáticas Unbalanced Approach Algorithms Metric Space Searching Metrics 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. Eje: Algoritmos Red de Universidades con Carreras en Informática (RedUNCI) Objeto de conferencia Objeto de conferencia http://creativecommons.org/licenses/by-nc-sa/2.5/ar/ Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Argentina (CC BY-NC-SA 2.5) application/pdf 339-343
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
_version_ 1734119360467828736

Ejemplares similares