Elizabeth Carvalho, November 2008

CHUB – Um Modelo Cartográfico para a Visualização e Análise do Corpo Humano

Adérito Fernandes Marcos/Maribel Yasmina Santos/João Espregueira-Mendes (superv.), Universidade do Minho, November 2008
Keywords: clustering, shared nearest neighbour, movement data

Abstract: Current positioning and sensing technologies enable the collection of very large spatio-temporal data sets. When analysing movement data, researchers often resort to clustering techniques to extract useful patterns from these data. Density-based clustering algorithms, although being very adequate to the analysis of this type of data, can be very inefficient when analysing huge amounts of data. The SNN (Shared Nearest Neighbour) algorithm presents low efficiency when dealing with high quantities of data due to its complexity evaluated in the worst case by O(n2). This work presents a clustering method, based on the SNN algorithm that significantly reduces the processing time by segmenting the spatial dimension of the data into a set of cells, and by minimizing the number of cells that have to be visited while searching for the nearest neighbours of each vector.