Voronoi-Tree: Optimización y Dinamismo

Roberto Uribe, Fabián Granero, and Gonzalo Navarro

El Voronoi-Tree es una estructura de datos para búsquedas por similaridad en espacios métricos. Esta estructura ha demostrado tener buen desempeño en espacios de alta dimensión, sin embargo, es estática, es decir, no está diseñada para la inserción y eliminación de objetos una vez construida. Esto implica que no puede ser usada en una serie de aplicaciones interesantes.

El presente trabajo describe la propuesta de una versión dinámica del Voronoi-Tree con la implementación de las optimizaciones y del método de Planos Fantasmas propuestos para otras estructuras. Se demuestra que, como resultado, es posible dar pleno dinamismo a la estructura y ofrecer un método adecuado y de bajo costo para la eliminación, además manteniendo un buen desempeño en la búsqueda.