Datenstrukturen für geometrische Clustering-Anfragen

• Antragsteller: Professor Dr. Kevin Buchin
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 550797858

Datenstrukturen für Bereichsanfragen sind ein wichtiges und grundlegendes Forschungsthema der Algorithmischen Geometrie. Eine solche Datenstruktur speichert geometrische Objekte, so dass gegeben ein Anfragebereich alle Objekte innerhalb des Bereiches effizient ausgegeben werden können. In vielen Anwendungen von Bereichsanfragen ist allerdings das Auflisten der Objekte im Bereich nicht das eigentliche Ziel der Anfrage, sondern eine weitere Analyse auf den Objekten im Anfragebereich. Ein wichtiges Beispiel für eine solche Analyse ist ein Clustering der Objekte im Bereich zu berechnen, insbesondere bei einer großen Anzahl von Objekten. Mit existierenden algorithmischen Techniken ist die Durchführung einer solchen Anfrage ein zweistufiger Prozess: Zunächst wird eine Datenstruktur für Bereichsanfragen verwendet, die alle Objekte extrahiert, die sich innerhalb des Anfragebereichs befinden; dann wird auf diesen Objekten ein Clustering-Algorithmus aufgerufen. Letzteres wird für jeden Anfragebereich immer wieder neu ausgeführt. Da Clustering-Algorithmen oft recht langsam sind, sind somit existierende Datenstrukturen für Bereichsanfragen ineffizient in der Beantwortung solcher Bereichs-Clustering Anfragen. Das Ziel der Forschung dieses Antrags ist es, geometrische Datenstrukturen zu entwickeln, die Bereichsanfragen mit Clustering für geometrische Objekte integrieren, so dass ein Clustering der Objekte innerhalb eines Anfragebereichs effizient beantwortet werden kann und nicht für jede Anfrage neu berechnet werden muss. Hierbei werden wir den Fokus auf Clustering mit einer gegebenen Anzahl von Cluster legen, insbesondere das k-Center Problem, das k-Means Problem und ähnliche Probleme. Unser erstes Teilziel ist es, solche Datenstrukturen für Punktmengen zu entwickeln. Für dieses Ziel sind sowohl exakte als auch approximative Methoden wichtig. Wir planen existierende Techniken für Bereichsanfragen auf unser komplexeres Problem zu erweitern. Eine besondere Herausforderung hierbei ist, dass Clustering Probleme nicht zerlegbar (engl. decomposible) sind. Unser zweites Teilziel ist es, diese Datenstrukturen auf Kurven zu erweitern. Eine zusätzliche Herausforderung hierbei ist, dass Clustering von Kurven unter Abstandsmaßen wie dem Fréchet Abstand als solches schon schwieriger ist als für Punkte. Unser drittes Teilziel ist es, Techniken für Daten mit geometrischer Ungenauigkeit in diese Datenstrukturen zu integrieren. Eine Herausforderung hierbei ist, dass Ungenauigkeit in geometrischen Daten bisher vor allem aus der algorithmischen Sicht, aber weniger aus der Sicht von Datenstrukturen betrachtet wurde. Das Projekt präsentiert eine neue Perspektive auf die Vorverarbeitung geometrischer Daten. Nicht nur werden neuen Datenstrukturen für lokalisiertes Clustering entwickelt, sondern die erzielten Techniken und Erkenntnisse können als Grundlage für andere komplexe Bereichsanfragen dienen und zu neuen Algorithmen für Clustering im Allgemeinen führen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Niederlande
• Kooperationspartner: Professor Mark de Berg; Dr. Maarten Löffler