Cover tree based dynamization of clustering algorithms

In this work, cover trees are the main focus, and they serve as a data structure to efficiently store metric data. We utilize them for dynamically handling the k-center problem, both with and without outliers. The cover tree data structure is designed to retrieve a coreset, a very succinct summary of the data, which is then fed to an offline clustering algorithm to quickly obtain a solution for the whole dataset. With respect to the original definition, the cover tree implemented is augmented, to maintain additional information crucial for extracting reasonable coresets. The solutions obtainable for the mentioned problems are (α + ε)-approximations, where α represents the best-known approximation achievable in polynomial time in the standard offline setting, and ε>0 is a user-provided accuracy parameter. The main objective in using a dynamic data structure is to obtain a reasonable solution, in comparison to the solution obtained by applying the clustering algorithms from scratch to all the data points. To ascertain the quality of our solution, we conduct a series of experiments to evaluate its performance and to fine-tune the involved parameters.

In questo lavoro, i Cover Tree sono l'obiettivo principale e servono come struttura di dati per memorizzare in modo efficiente i dati. Li utilizziamo per gestire dinamicamente il k-Center problem, sia con che senza outlier. La struttura Cover Tree è progettata per recuperare un coreset, una rappresentazione molto piccola dei dati, che viene poi fornito a un algoritmo di clustering offline per ottenere rapidamente una soluzione per l'intero set di dati. Rispetto alla definizione originale, il Cover Tree implementato viene aumentato con nuovi campi, per mantenere informazioni aggiuntive cruciali per l'estrazione di coreset ragionevoli. Le soluzioni ottenibili per i problemi citati sono approssimazioni (α + ε), dove α rappresenta la migliore approssimazione nota ottenibile in tempo polinomiale nell'impostazione standard offline e ε>0 è un parametro di precisione fornito dall'utente. L'obiettivo principale dell'utilizzo di una struttura dati dinamica è quello di ottenere una soluzione ragionevole, rispetto a quella ottenuta applicando gli algoritmi di clustering da zero a tutti i dati. Per verificare la qualità della nostra soluzione, conduciamo una serie di esperimenti per valutarne le prestazioni e mettere a punto i parametri coinvolti.