Optimizing the Spatial Approximation Tree from the Root

Many computational applications need to look for informa-tion in a database. Nowadays, the predominance of non-conventional databases makes the similarity search (i.e., searching elements of the database that are “similar ” to a given query) becomes a preponderant concept. The Spatial Approximation Tree has been shown that it compares favorably against alternative data structures for similarity searching in metric spaces of medium to high di-mensionality (“difficult ” spaces) or queries with low selec-tivity. However, for the construction process the tree root has been randomly selected and the tree,in its shape and performance, is completely determined by this selection. Therefore, we are interested in improve mainly the searches in this data structure trying to select the tree root so to re-flect some of the own characteristics of the metric space to be indexed. We regard that selecting the root in this way it allows a better adaption of the data structure to the intrin-sic dimensionality of the metric space considered, so also it achieves more efficient similarity searches