1. Inicio
  2. Atrás
Título: Métodos de paginación paraíndices métricos basados en pivotes
Autores: Villegas, Ana
Chávez, Edgar
Herrera, Norma Edith
Fecha: 2012-10-11
2004
Publicador: Unversidad Nacional de La Plata
Fuente:

Tipo: Objeto de conferencia
Objeto de conferencia
Tema: Búsquedas por Similitud
Índices
Memoria Secundaria
SOFTWARE ENGINEERING
Metrics
Ciencias Informáticas
base de datos
Descripción: El problema de buscar objetos en una base de datos que sean similares a uno dado puede formalizarse por medio del modelo de Espacios Métricos. La mayoría de las soluciones existentes para búsquedas por similitud en espacios métricos suponen que tanto el espacio como el índice completo entran en memoria principal. En este artículo presentamos una implementación del Fixed Queries Trie (FQtrie) que permite manejar espacios métricos cuyo índice completo y/o datos exceda la capacidad de la memoria principal. Para ello, en lugar de modificar la estructura para que sea eficiente en memoria secundaria, particionamos el espacio de manera tal que cada una de las partes entre en memoria principal, las que posteriormente se indexan en forma separada. Luego, una búsqueda se resuelve buscando en cada parte, lo que puede ser hecho en memoria principal y en paralelo. Para particionar el espacio hemos diseñado un método basado en la distancia LCS (longest common subsequence). Mostramos experimentalmente que esta forma de particionar, ante una búsqueda, implica menor cantidad de accesos a disco que si el espacio se particiona en forma totalmente aleatoria.
Eje: I - Workshop de Ingeniería de Software y Base de Datos
Idioma: Español