Scalable management of complex spatial data types

Abstract

Scalable spatial data management is crucial in both scientific and commercial domains, particularly in Geographic Information Systems (GIS), which handle massive volumes of geographic data. As spatial data continues to grow rapidly, the demand for efficient spatial data analytics tools has become increasingly pressing. A core functionality of such tools is the computation of spatial and topological joins over large collections of objects. These operations aim to identify intersecting object pairs (i.e., objects that share at least one common point), a fundamental task with applications in geospatial interlinking, spatial databases, and beyond. However, intersection testing is computationally intensive, especially for polygonal objects, which often contain a large number of vertices and require costly geometric processing.This dissertation investigates approximation techniques for handling high-complexity polygons, with the aim of making processing faster and more efficient. The central objective is to minimize reliance on original geometries, using them for computations only as a last resort. Our proposed solutions introduce efficient polygon approximation methods with a low memory footprint, along with filtering techniques that enable spatial joins to be evaluated without directly accessing the original geometries. The work addresses both scalability and accuracy challenges while striving to deliver solutions that are directly applicable to modern in-memory spatial databases.Scalable spatial data management has two key aspects. First, query processing algorithms must be highly parallelizable and independent, enabling them to fully leverage distributed and parallel spatial databases for both vertical and horizontal scalability. Second, they must maintain efficiency as geometric complexity increases, since complex shapes often become a major bottleneck in spatial query processing. In the second part of this dissertation, we design and implement a prototype distributed spatial data management framework that operates independently of underlying engines, focusing specifically on the performance and scalability of spatial query evaluation in tightly coupled clusters. The prototype integrates state-of-the-art indexing, approximation, and filtering techniques while carefully minimizing both communication overhead and memory usage.With the rapid advancement of Large Language Models (LLMs) and their expanding use across diverse domains, questions arise regarding their ability to handle complex tasks, particularly spatial reasoning over text. While LLMs excel at inferring and extracting information from large text collections, spatial knowledge is often domain-specific and not inherently intuitive for them. The first limitation is commonly mitigated through Retrieval-Augmented Generation (RAG), where external databases provide context at inference time, enhancing factual accuracy in responses. However, without fine-tuning or re-training, which can be costly and counterproductive to the goal of broad generalization, LLMs have consistently demonstrated weak performanceon spatial reasoning tasks.In the final part of this dissertation, we investigate how topological relations can help LLMs generate correct responses to spatial reasoning questions expressed in text. We first employ our efficient spatial topology algorithms to scalably compute key inter-dataset spatial relations and represent them as RDF (text) triplets. These are then leveraged through RAG-based mechanisms and indexing techniques to enable fast and accurate spatial context retrieval at inference time, with the dual objective of (i) supplying the LLM with domain-specific spatial knowledge and (ii) supporting it in producing factually correct responses.In summary, this dissertation presents a comprehensive study of scalable spatial data management. It introduces in-memory solutions that are both efficient and accurate, addressing key challenges across a broad spectrum of use cases. The proposed approaches are directly applicable to modern spatial databases and well-suited for data-intensive geospatial applications.

Η κλιμακώσιμη διαχείριση χωρικών δεδομένων είναι κρίσιμη τόσο στον επιστημονικό όσο και στον εμπορικό τομέα, ιδιαίτερα στα Γεωγραφικά Συστήματα Πληροφοριών (GIS), τα οποία διαχειρίζονται τεράστιους όγκους γεωγραφικών δεδομένων. Καθώς τα χωρικά δεδομένα συνεχίζουν να αυξάνονται ραγδαία, η ανάγκη για αποδοτικά εργαλεία χωρικής ανάλυσης γίνεται ολοένα και πιο επιτακτική. Βασική λειτουργικότητα τέτοιων εργαλείων αποτελεί ο υπολογισμός χωρικών και τοπολογικών συνενώσεων (joins) σε μεγάλες συλλογές οντωτήτων. Οι πράξεις αυτές αποσκοπούν στον εντοπισμό ζευγών που τέμνονται (δηλαδή αντικείμενα που μοιράζονται τουλάχιστον ένα κοινό σημείο), μια θεμελιώδης διαδικασία με εφαρμογές στη γεωχωρική διασύνδεση, στις χωρικές βάσεις δεδομένων και πέραν αυτών. Ωστόσο, ο έλεγχος τομής είναι υπολογιστικά δαπανηρός, ιδιαίτερα για πολυγωνικά αντικείμενα, τα οποία συχνά περιέχουν μεγάλο αριθμό κορυφών και απαιτούν κοστοβόρα γεωμετρική επεξεργασία. Η παρούσα διατριβή διερευνά τεχνικές προσεγγιστικής αναπαράστασης για την αποδοτική διαχείριση πολύπλοκων πολυγώνων, με στόχο την ταχύτερη και πιο αποτελεσματική επεξεργασία. Ο κεντρικός στόχος είναι η ελαχιστοποίηση της εξάρτησης από τις αρχικές γεωμετρίες, χρησιμοποιώντας τις μόνο ως έσχατη λύση για υπολογισμούς. Οι προτεινόμενες λύσεις εισάγουν αποδοτικές μεθόδους προσεγγιστικής αναπαράστασης πολυγώνων με μικρό αποτύπωμα μνήμης, καθώς και τεχνικές φιλτραρίσματος που επιτρέπουν την εκτέλεση χωρικών συνενώσεων χωρίς άμεση πρόσβαση στις αρχικές γεωμετρίες. Η εργασία αντιμετωπίζει τόσο ζητήματα επεκτασιμότητας όσο και ακρίβειας, ενώ παράλληλα επιδιώκει την ανάπτυξη λύσεων άμεσα εφαρμόσιμων σε σύγχρονες χωρικές βάσεις δεδομένων στη μνήμη. Η κλιμακώσιμη διαχείριση χωρικών δεδομένων έχει δύο βασικές διαστάσεις. Πρώτον, οι αλγόριθμοι επεξεργασίας ερωτημάτων πρέπει να είναι υψηλά παραλληλοποιήσιμοι και ανεξάρτητοι, ώστε να αξιοποιούν πλήρως τις κατανεμημένες και παράλληλες χωρικές βάσεις δεδομένων τόσο για κάθετη όσο και για οριζόντια κλιμάκωση. Δεύτερον, πρέπει να διατηρούν την αποδοτικότητά τους καθώς αυξάνεται η γεωμετρική πολυπλοκότητα, δεδομένου ότι τα πολύπλοκα σχήματα αποτελούν συχνά σημαντικό σημείο συμφόρησης στην επεξεργασία χωρικών ερωτημάτων. Στο δεύτερο μέρος της διατριβής, σχεδιάζουμε και υλοποιούμε ένα πρωτότυπο κατανεμημένο πλαίσιο διαχείρισης χωρικών δεδομένων, το οποίο λειτουργεί χωρίς εξάρτηση σε υποκείμενα συστήματα, εστιάζοντας ειδικά στην απόδοση και την κλιμακωσιμότητα της εκτέλεσης χωρικών ερωτημάτων σε στενά συνδεδεμένα, κατανεμημένα υπολογιστικά συστήματα. Το πρωτότυπο ενσωματώνει σύγχρονες τεχνικές δεικτοδότησης, προσεγγιστικής αναπαράστασης και φιλτραρίσματος, ελαχιστοποιώντας παράλληλα την επικοινωνιακή επιβάρυνση και τη χρήση μνήμης. Με τη ραγδαία πρόοδο των Μεγάλων Γλωσσικών Μοντέλων (LLMs) και την αυξανόμενη χρήση τους σε ποικίλους τομείς, προκύπτουν ερωτήματα σχετικά με την ικανότητά τους να χειρίζονται πολύπλοκες εργασίες, και ειδικότερα τη χωρική συλλογιστική μέσω κειμένου. Αν και τα LLMs διαπρέπουν στην εξαγωγή και επεξεργασία πληροφορίας από μεγάλες συλλογές κειμένων, η χωρική γνώση είναι συχνά εξειδικευμένη και όχι εγγενώς διαισθητική για αυτά. Ένας βασικός περιορισμός μετριάζεται μέσω της μεθόδου Retrieval-Augmented Generation (RAG), όπου εξωτερικές βάσεις δεδομένων παρέχουν συμφραζόμενα κατά το χρόνο εκτέλεσης, βελτιώνοντας την πραγματολογική ακρίβεια των απαντήσεων. Ωστόσο, χωρίς προσαρμοστική εκπαίδευση ή επανεκπαίδευση, διαδικασίες που είναι δαπανηρές και αντίθετες προς τον στόχο της γενικής χρήσης, τα LLMs εμφανίζουν σταθερά αδύναμες επιδόσεις σε χωρικές συλλογιστικές εργασίες. Στο τελικό μέρος της διατριβής, διερευνούμε πώς οι τοπολογικές σχέσεις μπορούν να βοηθήσουν τα LLMs να παράγουν ορθές απαντήσεις σε ερωτήσεις χωρικής συλλογιστικής που εκφράζονται σε κείμενο. Αρχικά, εφαρμόζουμε τους αποδοτικούς αλγόριθμους χωρικής τοπολογίας που αναπτύξαμε για να υπολογίσουμε με κλιμακώσιμο τρόπο βασικές διασυνόλου χωρικές σχέσεις και να τις αναπαραστήσουμε ως RDF τριάδες (κειμενικές). Στη συνέχεια, αυτές αξιοποιούνται μέσω μηχανισμών RAG και τεχνικών δεικτοδότησης, ώστε να καταστεί δυνατή η ταχεία και ακριβής ανάκτηση χωρικών συμφραζομένων κατά την εκτέλεση, με διττό στόχο: (i) τον εφοδιασμό του LLM με εξειδικευμένη χωρική γνώση και (ii) την υποστήριξή του στην παραγωγή πραγματολογικά ορθών απαντήσεων. Συνοψίζοντας, η διατριβή αυτή παρουσιάζει μία ολοκληρωμένη μελέτη για την κλιμακώσιμη διαχείριση χωρικών δεδομένων. Εισάγει λύσεις στη μνήμη που είναι ταυτόχρονα αποδοτικές και ακριβείς, αντιμετωπίζοντας κρίσιμες προκλήσεις σε ευρύ φάσμα περιπτώσεων χρήσης. Οι προτεινόμενες προσεγγίσεις είναι άμεσα εφαρμόσιμες σε σύγχρονες χωρικές βάσεις δεδομένων και κατάλληλες για εφαρμογές εντατικής γεωχωρικής επεξεργασίας δεδομένων.