Schnellere und deterministische Subtrajectory-Clustering

Gegeben ist eine Trajektorie T und eine Distanz, wir möchten eine Menge C von Kurven mit maximaler Komplexität finden, so dass wir T mit Subkurven abdecken können, die jeweils innerhalb der Fréchet-Distanz zu mindestens einer Kurve in C liegen. Wir nennen C ein (, ) -Clustering und zielen darauf ab, ein (, ) -Clustering mit minimaler Kardinalität zu finden. Dieses Problem wurde von Akitaya et al. (2021) eingeführt und als NP-vollständig nachgewiesen. Der Schwerpunkt lag daher auf bicriterialen Approximationsalgorithmen, die es erlauben, dass das Clustering ein (, () ) -Clustering von ungefähr optimaler Größe ist. Wir präsentieren Algorithmen, die (, 4) -Clustering von O (k n) Größe konstruieren, wobei k die Größe des optimalen (, ) -Clustering ist. Für die diskrete Fréchet-Distanz verwenden wir O (n n) Speicher und O (k n² ³ n) deterministische Worst-Case-Zeit. Für die kontinuierliche Fréchet-Distanz verwenden wir O (n² n) Speicher und O (k n³ ³ n) Zeit. Unsere Algorithmen verbessern erheblich die Clustering-Qualität (Verbesserung des Approximationsfaktors in) und die Größe (wann immer (n) ). Wir bieten deterministische Laufzeiten, die vergleichbar mit bekannten erwarteten Grenzen sind. Darüber hinaus bieten wir im kontinuierlichen Setting eine annähernd lineare Verbesserung des Speicherverbrauchs. Im Vergleich nur zu deterministischen Ergebnissen bieten wir einen nahezu linearen Geschwindigkeitszuwachs und eine annähernd quadratische Verbesserung des Speicherverbrauchs. Wenn wir uns darauf beschränken können, nur Cluster zu betrachten, bei denen alle Subtrajektorien Eck-zu-Eck-Subkurven sind, erzielen wir unter der kontinuierlichen Fréchet-Distanz sogar noch bessere Ergebnisse. Unser Algorithmus wird nahezu quadratisch und verwendet Speicher, der annähernd linear in n ist.