Selección espacial de pivotes dispersos para la búsqueda por similitud en espacios métricos

Abstract

La búsqueda por similitud es una operación fundamental en aplicaciones que trabajan con fuentes de datos no estructuradas. En este artículo proponemos un nuevo método de búsqueda por similitud basado en pivotes, que denominamos Sparse Spatial Selection (SSS). La principal característica de SSS es que garantiza una buena selección de pivotes con un coste computacional más bajo que otros métodos propuestos anteriormente. Además, SSS se adapta por sí sólo a la dimensionalidad del espacio métrico con el que estamos trabajando, sin que sea necesario especificar de antemano el número de pivotes que se van a extraer. Por otro lado, SSS es dinámico, es decir, es capaz de soportar inserciones de objetos en la base de datos sin que su eficiencia se vea reducida, puede usar tanto distancias continuas como discretas y se adapta bien a memoria secundaria. En este trabajo proporcionamos resultados experimentales que confirman las ventajas del método con distintos espacios vectoriales y métricos. Demostramos también que nuestra propuesta tiene una eficiencia similar a otras ya existentes en espacios vectoriales, aunque es mejor en espacios métricos generales.

Similarity search is a fundamental operation for applications that deal with unstructured data sources. In this paper we propose a new pivot-based method for similarity search, called Sparse Spatial Selection (SSS). The main characteristic of this method is that it guarantees a good pivot selection with a lower computational cost than other methods previously proposed. In addition, SSS adapts itself to the dimensionality of the metric space we are working with, without being necessary to specify in advance the number of pivots to extract. Furthermore, SSS is dynamic, this is, it is capable to support object insertions in the database without getting its ef ciency reduced, it can work with both continuous and discrete distance functions, and it is suitable for secondary memory storage. In this work we provide experimental results that con rm the advantages of the method with several vectorial and metric spaces. We also show that the ef ciency of our proposal is similar to that of other existing ones over vectorial spaces, although it is better over general metric spaces.