Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/30163

Titlekd-SNN : a metric data structure seconding the clustering of spatial data
Author(s)Faustino, Bruno Filipe
Pires, João Moura
Santos, Maribel Yasmina
Moreira, Guilherme
Keywordskd-tree
SNN
Spatial data
Movement data
Route identification
Issue date2014
PublisherSpringer International Publishing
JournalLecture Notes in Computer Science
Abstract(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.
TypeConference paper
DescriptionPublicado em "Computational science and its applications – ICCSA 2014 : proceedings...", Series title : Lecture notes in computer science, vol. 8579
URIhttp://hdl.handle.net/1822/30163
ISBN978-3-319-09143-3
DOI10.1007/978-3-319-09144-0_22
ISSN0302-9743
Peer-Reviewedyes
AccessRestricted access (UMinho)
Appears in Collections:CAlg - Artigos em livros de atas/Papers in proceedings

Files in This Item:
File Description SizeFormat 
ICCSA2014_BF_JMP_MYS_GM.pdf
  Restricted access
Documento Principal3,76 MBAdobe PDFView/Open    Request a copy!

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID