Exploring Exemplar Trajectory Queries

Abstract

Utbredelsen av GPS-kompatible mobile enheter som lar brukere loggføre sine geografiske posisjon samt spore bevegelser over tid, har gitt opphav til flere nye ulike applikasjoner. Disse applikasjonene har belyst nye problemer og utfordringer som krever nye smarte løsninger. Et eksempel på et slikt problem, er hvordan vi effektivt kan finne de k-likeste trajectories til en gitt trajectory. Et exemplar trajectory query er enn slik type spørring. Denne spørringen består av en samling med punkter i en gitt rekkefølge, hvor hvert punkt har en tekstlig beskrivelse. Resultatet av en slik spørring vil være de k likeste trajectories gitt ved en similaritetsfunksjon. I denne rapporten vil vi undersøke og implementere to algoritmer som kan brukes for å svare på slike spørringer. Videre vil vi utvide en av algoritmene til å håndtere store datamengder ved hjelp av Apache Spark.

The proliferation of mobile devices enables people to log their geographical positions andto trace historical movements, which has spawned various novel applications. These applications have revealed new problems that require new solutions. One in particular is that of efficiently finding the top-k trajectories according to spatial- and textual similarity. An exemplar trajectory query is a query which specifies an ordered list of points in space, wherein each point has a textual description. The goal is to find the top-k trajectories as ranked by a given similarity function. In this thesis we explore and attempt to implement two algorithms used two answer such queries. We will also attempt to extend one of these algorithms to process large volumes of data using Apache Spark.