kd-SNN: A Metric Data Structure Seconding the Clustering of Spatial Data

Bruno Filipe Faustino, Joao Moura-Pires, Maribel Yasmina Santos, Guilherme Moreira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

Large amounts of spatio-temporal data are continuously collected through the use of location devices or sensor technologies. One of the techniques usually used to obtain a first insight on data is clustering. 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(n(2)), compromising 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 x log n). The proposed algorithm, the kd-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.

Original languageEnglish
Title of host publicationCOMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2014, PT 1
EditorsB Murgante, S Misra, AMAC Rocha, C Torre, JG Rocha, MI Falcao, D Taniar, BO Apduhan, O Gervasi
PublisherSPRINGER-VERLAG BERLIN
Pages312-327
Number of pages16
ISBN (Print)978-3-319-09143-3
Publication statusPublished - 2014
Event14th International Conference on Computational Science and Its Applications (ICCSA) - Guimaraes, Portugal
Duration: 30 Jun 20143 Jul 2014

Publication series

NameLecture Notes in Computer Science
PublisherSPRINGER-VERLAG BERLIN
Volume8579
ISSN (Print)0302-9743

Conference

Conference14th International Conference on Computational Science and Its Applications (ICCSA)
CountryPortugal
CityGuimaraes
Period30/06/143/07/14

Keywords

  • kd-tree
  • SNN
  • spatial data
  • movement data
  • route identification

Cite this