Eligiendo raíces para el Árbol de aproximación espacial

Abstract

Muchas aplicaciones computacionales necesitan buscar información en una base de datos. En la actualidad el predominio de las bases de datos multimedia hace que la búsqueda por similitud o búsqueda por proximidad, es decir buscar elementos de la base de datos que sean similares a un elemento de consulta dado, se vuelva un concepto preponderante. El Árbol de Aproximación Espacial ha demostrado ser muy competitivo para la búsqueda por similitud en espacios métricos de media a alta dimensionalidad (espacios difíciles ) o para responder a consultas con baja selectividad. Sin embargo, para su construcción se elegía su raí z al azar y ello determinaba completamente el árbol tanto en su forma como en su desempe ño. Así , nuestro interés fue el de optimizar las búsquedas en dicha estructura tratando de que la raíz sea elegida de manera tal que re fleje alguna de las caracterí sticas propias del espacio métrico a indexar. Creemos que de esta forma permitimos que la estructura se adapte mejor a la dimensión intrí nseca del espacio métrico considerado, lo cual redunda en búsquedas más efi cientes.

Many computational applications need to search information in a database. At the present time the predominance of multimedia databases does that the similarity search or proximity search, that is to look for elements of the database that are similar to a given query element, becomes a preponderant concept. The Spatial Approximation Trees have shown to be competitive for similarity search in spaces with medium to high dimensionality ( dif cult spaces) or for queries with low selectivity. Nevertheless, for its construction its root was chosen randomly and it completely determines the tree, not only in its shape but also in its searching performance. Thus, our interest was to optimize searches in this data structure trying to choose the tree root in a way that the characteristics of indexed space can be re ected. We consider that, by this way, the data structure can adapt itself better to the dimension of the considered metric space, which results in more ef cient similarity searches.