ARBOL BVH

UNIVERSIDAD CATÓLICA DE SANTA MARÍA
FACULTAD DE CIENCIAS E INGENIERÍAS FÍSICAS Y FORMALES
PROGRAMA PROFESIONAL DE INGENIERÍA DE SISTEMAS
X- SEMESTRE



ALGORITMOS Y ESTRUCTURA DE DATOS II
TEMA:
INFORME ÁRBOL-BV

DOCENTE:
ING. KARIM GUEVARA

ALUMNOS:
CUENTAS PICÓN, ERNESTO ANDRÉE

VARGAS ANGULO, JORGE ALEXIS

AREQUIPA – PERÚ
2013
ARBOL BV

INTRODUCCIÓN
El árbol BVrepresenta un intento de resolver el problema d-dimensional del árbol B, es decir ,para encontrar a una generalización del árbol B de dimensiones superiores. El árbol BV no está destinado a ser un método de acceso concreto. Representa un marco conceptual que puede ser aplicado a una variedad de métodos de acceso existentes, incluyendo el archivo BANG o el árbol HB.

DESARROLLO

La propuesta deFreeston se basa en la conjetura de que uno puede mantener los principales puntos fuertes del árbol B en dimensiones superiores, siempre y cuando uno relaje los requisitos estrictos que conciernen el balance del árbol y la utilización del almacenamiento. El árbol BV no es completamente balanceado. Por otra parte, mientras que el árbol B garantiza una utilización, en el peor de los casos, delalmacenamiento del 50% , Freeston argumenta que la utilización de alto de almacenamiento no se puede asegurar para dimensiones superiores por razones topológicas . Sin embargo , el árbol BV logra alcanzar 33 % menos del límite sugerido por Lomet y Salzberg ( 1989 ) .
Para lograr un rendimiento garantizado de búsqueda en el peor de los casos , el árbol BV combina el concepto de rompimiento ( Freeston 1987) con una técnica llamada promoción. Aquí, los intervalos desde los niveles inferiores del árbol se mueven hacia arriba, más cerca de la raíz. Para mantener un seguimiento de los cambios resultantes, con cada región promovida almacenamos un número de nivel (llamado guardia) que indica el nivel original de la región.
Los algoritmos de búsqueda se basan en una técnica de retroceso nocional. Aldescender del árbol, almacenamos las alternativas posibles (las guardias pertinentes de los distintos niveles de índices) En un conjunto de guardia. Las entradas de este conjunto actúan como puntos de rastreo y representan un solo camino desde la raíz hasta el nivel actualmente inspeccionado; para los puntos de consultas, que se pueden mantener como una pila. Para responder a un punto de consulta,comenzamos en la raíz e inspeccionamos todas las entradas del nodo si las regiones correspondientes se sobreponen al punto de búsqueda. Entre esas entradas inspeccionadas, elegimos la mejor entrada de coincidencia para investigar después.
Posiblemente también almacenamos algunos guardias en el conjunto de guardia. En el siguiente nivel se repite este procedimiento de forma recursiva, esta veztomando en cuenta los guardias almacenados. Antes de partir de la entrada más coincidente hasta el siguiente nivel, el conjunto de guardia se actualiza por la fusión mediante la coincidencia de nuevos guardias con los ya existentes. Dos guardias en el mismo nivel se fusionan al descartar el peor partido.
Esta búsqueda continúa de forma recursiva hasta llegar al nivel hoja. Hay que tener en cuenta quepara los puntos de consulta, la longitud de la ruta de búsqueda es igual a la altura del árbol-BV porque cada región en el espacio está representada por una entrada de nodo único.
La figura 1 muestra un árbol-BV y la correspondiente partición del espacio para el ejemplo de ejecución. A modo de ejemplo, no limitamos las regiones agrupadas u objetos por una línea poligonal ajustada, pero si conapenas un límite envuelto. En este ejemplo, la región D0 actúa como un guardia. Está claro desde el espacio de partición que originalmente D0 pertenece al nivel del índice inferior (nivel medio en la figura). Ya que funciona como un guardia de la región encerrada S1, sin embargo, ha sido ascendido al nivel de la raíz.
Supongamos que estamos interesados ​​en todos los objetos que intersecan al...