Exploring Linked List-based Trajectory Traversal for Efficient Topological Queries in Spatial Data

Abstract

Den raske veksten av romlig data grunnet økt tilgjengelighet av IoT-enheter og smarttelefoner presenterer nye utfordringer for romlig datahåndtering. Databasesystemer designet for romlig data har vært effektive i spørring av romlig data i flere tiår, men imidlertid anses topologiske spørringer ofte som beregningsmessig dyre, og eksisterende datastrukturer som forbedrer slike spørringer, ofrer ofte ytelse på romlige spørringer. I denne oppgaven har vi som mål å forbedre effektiviteten av topologiske spørringer av romlig data uten å endre den underliggende datastrukturen. For å oppnå dette, foreslår vi å bruke lenkede lister til å traversere spor av noder som en graf, og dermed muliggjøre effektiv identifikasjon av start- og sluttnoder uten å måtte ha en indeks eller full tabellskanning. Vi gjennomførte ytelsestester som viser at den foreslåtte metoden er betydelig raskere enn tidligere tilnærminger, noe som indikerer at den fortjener ytterligere utforskning. Denne studien bidrar til feltet for romlig datahåndtering ved å presentere en ny tilnærming for å forbedre effektiviteten av topologiske spørringer, som kan ha praktiske implikasjoner for virkelige applikasjoner.

The rapid growth of spatial data due to the proliferation of IoT devices and smartphones presents new challenges for spatial data management. Spatial databases have been effective in querying spatial data for several decades, but topological queries are often considered computationally expensive, and existing data structures that improve such queries typically sacrifice performance on spatial queries. In this thesis, we aim to enhance the efficiency of topological queries in spatial data without altering the underlying data structure. To achieve this, we propose using linked lists to traverse trajectories as a graph, thereby enabling efficient identification of trajectory heads and tails without requiring expensive lookups. We conducted benchmarking tests that show the proposed method to be significantly faster than previous approaches, indicating that it merits further exploration. This study contributes to the field of spatial data management by presenting a novel approach to improve the efficiency of topological queries, which could have practical implications for real-world applications.