Utilising locality sensitive hashing for efficient trajectory similarity computation

Abstract

Den stadig voksende mengden av GPS-kompatible elektroniske enheter i stand til å registrere og lagre brukernes posisjons- og bevegelsesdata, har medført en økende interesse for analyse av denne type data. Fundamentalt i analyse av observasjondata er behovet for kvantifisering av similaritet mellom observasjonene. Det eksisterer flere similaritetsmål for dette formålet, men deres tidskompleksitet legger begrensninger for analyse av større mengder data.

I denne avhandlingen undersøker vi hvorvidt lokalitets-sensitive hashefunksjoner kan benyttes som alternativ til tradisjonelle similaritetsmål, med formål å forbedre tidsforbruket ved similaritetsberegning av GPS-spor. Vi tar utgangspunkt i to teknikker opprinnelig designet for topp-k spørringer, adapterer og implementerer disse, og analyserer aspekter som nøyaktighet og effektivitet, samt evaluerer de genererte similaritetenes ytelse under clustering.

The growing amount of GPS-compatible electronic devices capable of recording and storing users' position and movement data, has led to an increased interest in the analysis of this type of data. Fundamental in the analysis of observational data is the need for quantification of similarity between the observations. Several similarity measures exist for this purpose, but their time complexity limit the analysis of larger amounts of data.

In this thesis, we examine whether locality sensitive hashing functions can be utilised as an alternative to traditional similarity measures, with the aim of improving computation time when computing similarities between GPS-trajectories. As a starting point, we adapt and implement two techniques originally developed for top-k queries. We examine aspects such as accuracy and efficiency, in addition to evaluating how well the generated similarities performs in terms of clustering.