introduccion resumen

acorralTesis Algoritmos RTRee y procesamiento de consultas

Los requerimientos de aplicaciones actuales de bases de datos, tales como GIS (sistemas de
información geográfica), CAD (diseño asistido por ordenador), planificación urbana,
mantenimiento de recursos naturales, sistemas multimedia, etc., imponen la necesidad de
gestionar datos de diferente naturaleza y de encontrar algoritmospara dar respuesta a
consultas que expresen la relación que existe entre dichos datos. Para gestionar de forma
eficiente y rápida este gran volumen de datos se precisa del uso de métodos de acceso. El
procesamiento de consultas sobre métodos de acceso es un tema de investigación emergente
tanto desde el punto de vista de los algoritmos que las implementan como de las estructuras
de datosque las soportan.

Los requerimientos de aplicaciones actuales de bases de datos, tales como GIS (sistemas de
información geográfica), CAD (diseño asistido por ordenador), planificación urbana,
mantenimiento de recursos naturales, sistemas multimedia, etc., imponen la necesidad de
gestionar datos de diferente naturaleza y de encontrar algoritmos para dar respuesta a
consultas queexpresen la relación que existe entre dichos datos. Para gestionar de forma
eficiente y rápida este gran volumen de datos se precisa del uso de métodos de acceso. El
procesamiento de consultas sobre métodos de acceso es un tema de investigación emergente
tanto desde el punto de vista de los algoritmos que las implementan como de las estructuras
de datos que las soportan.

Cuando en unaconsulta intervienen objetos espaciales podemos preguntarnos acerca de
cuál es la relación espacial que existe entre ellos, por ejemplo, el join espacial sobre dos
conjuntos de objetos espaciales devuelve todos los pares de objetos que se solapan entre sí,
donde cada elemento del par pertenece a un conjunto diferente. Otra relación espacial es la
relación de cercanía, que representa el grado deproximidad entre los objetos espaciales, por
ejemplo, la consulta del vecino más próximo encuentra, entre un conjunto de objetos
espaciales, el objeto más próximo a uno previamente dado. La consulta basada en la relación
de cercanía entre dos conjuntos de objetos espaciales y que vamos a estudiar en esta tesis, la
vamos a denominar consulta de los pares más cercanos.

Branch-and-bound(ramificación y poda) es una técnica general de diseño de algoritmos
utilizada para buscar la solución óptima de un determinado problema. La idea principal
consiste en dividir el problema inicial en subproblemas parciales de tamaño más pequeño a
los que aplicamos heurísticas de poda que permiten descartar el espacio de soluciones del
problema que no conduce a la solución óptima. Esta técnicase suele utilizar en el diseño de
algoritmos para consultas en bases de datos espaciales, recorriendo los métodos de acceso
espaciales y calculando cotas relativas a soluciones parciales para limitar el número de
soluciones completas a examinar. En nuestro caso, los algoritmos que diseñaremos estarán
basados en esta técnica y utilizarán heurísticas de poda basadas en distancias paraacotar el
espacio de búsqueda.

En esta tesis estudiamos algoritmos branch-and-bound y aplicamos técnicas de
optimización sobre ellos para encontrar, dados dos conjuntos de objetos espaciales, los pares
de objetos espaciales más cercanos, perteneciendo cada elemento del par a un conjunto
diferente. Dichos conjuntos de objetos espaciales se encuentran indexados en R-trees (método
de accesoderivado del B-tree para gestionar información multidimensional), que son
estructuras de datos arbóreas basadas en rectángulos minimales definidos por dos puntos y
con sus caras paralelas a los ejes de coordenadas (MBRs), balanceadas en altura y
almacenadas en disco. Los algoritmos branch-and-bound son apropiados para implementar
consultas sobre estas estructuras de datos arbóreas, ya que...