Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/30163
Título: | kd-SNN : a metric data structure seconding the clustering of spatial data |
Autor(es): | Faustino, Bruno Filipe Pires, João Moura Santos, Maribel Yasmina Moreira, Guilherme |
Palavras-chave: | kd-tree SNN Spatial data Movement data Route identification |
Data: | 2014 |
Editora: | Springer International Publishing AG |
Revista: | Lecture Notes in Computer Science |
Resumo(s): | Large amounts of spatio-temporal data are continuously col- lected through the use of location devices or sensor technologies. One of the techniques usually used to obtain a first insight on data is clus- tering. The Shared Nearest Neighbour (SNN) is a clustering algorithm that finds clusters with different densities, shapes and sizes, and also identifies noise in data, making it a good candidate to deal with spatial data. However, its time complexity is, in the worst case, O(n2), com- promising its scalability. This paper presents the use of a metric data structure, the kd-Tree, to index spatial data and support the SNN in querying for the k-nearest neighbours, improving the time complexity in the average case of the algorithm, when dealing with low dimensional data, to at most O(n × log n). The proposed algorithm, the k d-SNN, was evaluated in terms of performance, showing huge improvements over existing approaches, allowing the identification of the main traffic routes by completely clustering a maritime data set. |
Tipo: | Artigo em ata de conferência |
Descrição: | Publicado em "Computational science and its applications – ICCSA 2014 : proceedings...", Series title : Lecture notes in computer science, vol. 8579 |
URI: | https://hdl.handle.net/1822/30163 |
ISBN: | 978-3-319-09143-3 |
DOI: | 10.1007/978-3-319-09144-0_22 |
ISSN: | 0302-9743 |
Arbitragem científica: | yes |
Acesso: | Acesso restrito UMinho |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
ICCSA2014_BF_JMP_MYS_GM.pdf Acesso restrito! | Documento Principal | 3,76 MB | Adobe PDF | Ver/Abrir |