Incremental Construction of Neighborhood Graphs Using the Ants Self-Assembly Behavior

In this paper we present a new incremental algorithm for building neighborhood graphs between data. It is inspired from the self-assembly behavior observed in real ants where ants progressively become attached to an existing support and then successively to other attached ants. Each artificial ant represents one data. The way ants move and build a graph depends on the similarity between the data. We have compared our results to those obtained by the relative neighborhood algorithm on several databases (either artificial or real), and we show that our method is competitive especially with respect to execution times.