Maritime Indexing from Nautical Networks
Authors
Falkesgaard, Jonas Noermark ; Pedersen, Kristian Morsing ; Jensen, Christopher Colberg
Term
4. term
Education
Publication year
2024
Submitted on
2024-05-22
Pages
21
Abstract
This thesis introduces Maritime Indexing from Nautical Networks (MINN), a method for indexing large collections of ship trajectories to make searches faster. The idea is to build a “nautical network”—a graph-like representation of common sea routes—from historical trajectories, align (map-match) new trajectories to this network, and then use the network structure to index the data. In databases, an index is a data structure that speeds up lookups; here, we focus on spatial range queries, which search for trajectories within a geographic area. We compare MINN to a standard spatial database index (GiST). We describe how to (1) construct the nautical network, (2) map-match trajectories to it using a new approach, and (3) exploit the network to build the index. Because MINN’s performance depends on the quality of the nautical network, we evaluate 108 different network configurations. The network is built from 44,509 trajectories recorded in January–February 2021, each at least 10 kilometers long, covering a total of 4,273,441 kilometers. We test the index on 71,941 trajectories from January 2022, totaling 2,104,914 kilometers, and we perform map-matching for each network configuration. In our experiments with spatial range queries, MINN reduces query response times by up to 72% compared to the GiST index.
Dette speciale præsenterer Maritime Indexing from Nautical Networks (MINN), en metode til at indeksere store mængder af skibstrajektorier, så søgninger bliver hurtigere. Idéen er at bygge et 'nautisk netværk'—en graf-lignende repræsentation af almindelige sejlruter—ud fra historiske trajektorier, tilpasse (map-matche) nye trajektorier til netværket og bruge netværkets struktur til at indeksere data. Et indeks i databaser er en datastruktur, der gør opslag hurtigere; her fokuserer vi på rumlige områdeforespørgsler, dvs. søgninger efter trajektorier inden for et geografisk område. Vi sammenligner MINN med et udbredt rumligt databaseindeks (GiST). Vi viser, hvordan man (1) konstruerer det nautiske netværk, (2) map-matcher trajektorier til det ved hjælp af en ny tilgang, og (3) udnytter netværket til at bygge indekset. Da MINNs ydelse afhænger af netværkets kvalitet, evaluerer vi 108 forskellige konfigurationer. Netværket bygges ud fra 44,509 trajektorier fra januar og februar 2021, hver mindst 10 kilometer lang, som tilsammen dækker 4,273,441 kilometer. Vi tester indekset på 71,941 trajektorier fra januar 2022, i alt 2,104,914 kilometer, og vi udfører map-matching for hver netværkskonfiguration. I vores forsøg med rumlige områdeforespørgsler reducerer MINN svartiderne med op til 72% sammenlignet med GiST-indekset.
[This apstract has been rewritten with the help of AI based on the project's original abstract]