Η παρούσα διατριβή διερευνά την αποτελεσματική εφαρμογή της αναζήτησης k
Closest Pairs Query (kCPQ) σε μεγάλης κλίμακας γεωχωρικά σύνολα δεδομένων
χρησιμοποιώντας παράλληλες δυνατότητες εντός της Scala. Εφαρμόζονται και
συγκρίνονται τέσσερις προσεγγίσεις λύσεων: η σειριακή Brute Force ως βάση
αναφοράς, μια παράλληλη έκδοση Brute Force, ο αλγόριθμος Plane Sweep και η
παράλληλη έκδοση Plane Sweep. Οι παράλληλες σχεδιαστικές λύσεις αξιοποιούν το
οικοσύστημα ταυτόχρονης εκτέλεσης της Scala (Futures/Promises, παράλληλες
συλλογές και μοτίβα βασισμένα σε actors) για την κατανομή της εργασίας μεταξύ των
πυρήνων της CPU, αλλά και για τον έλεγχο της μετακίνησης των δεδομένων και της
συγχώνευσης των αποτελεσμάτων.
Τα σύνολα δεδομένων δύο σημείων με έως 115 εκατομμύρια και 120 εκατομμύρια
σημεία υποβάλλονται σε δοκιμές για την αξιολόγηση των προκλήσεων που
παρουσιάζει η επεκτασιμότητα. Τα πειράματα εκτελέστηκαν σε έναν σταθμό εργασίας
με AMD Ryzen 9 7900X (12 πυρήνες), 32 GB RAM και Windows 11 Pro. Η
αξιολόγηση ποικίλλει ως προς το μέγεθος του συνόλου δεδομένων, το k, τον αριθμό
των νημάτων και το μέγεθος/επικάλυψη των τμημάτων, προκειμένου να εξεταστεί η
ευαισθησία τόσο στις φάσεις που εξαρτώνται από την CPU όσο και σε αυτές που
εξαρτώνται από την I/O.
Τα πλεονεκτήματα του Plane Sweep είναι σαφή: είναι σταθερά ανώτερο σε κάθε
μέγεθος που δοκιμάστηκε. Ακολουθεί το Parallel Plane Sweep, μετά το Parallel Brute
Force και τελευταίο το Serial Brute Force. Συνολικά, παρατηρούμε ότι το μέγεθος
επηρεάζει την αύξηση του χρόνου εκτέλεσης περισσότερο από ό,τι ο αριθμός k ή ο
αριθμός νημάτων εντός των εξεταζόμενων ευρών. Το μέγεθος των τμημάτων/η
επικάλυψη επηρεάζουν σε μεγάλο βαθμό την απόδοση στις παράλληλες μεθόδους. Σε
εισόδους πολλών εκατομμυρίων σημείων, το παράλληλο Plane Sweep μειώνει τον
χρόνο εκτέλεσης σε σύγκριση με τη σειριακή βάση αναφοράς, ενώ το σειριακό Plane
Sweep εξακολουθεί να ξεπερνά όλες τις μεθόδους όταν η τοπικότητα της μνήμης και
το φιλτράρισμα σάρωσης είναι αποτελεσματικά.
Συνοψίζοντας, η Scala έχει αποδειχθεί μια βιώσιμη λύση για αποτελεσματικές
παράλληλες γεωχωρικές αναλυτικές διαδικασίες. Είναι εκφραστική, ασφαλής ως προς
τον τύπο και εκτελείται εγγενώς σε JVM, παρέχοντας διαλειτουργικότητα. Η μελέτη
περιγράφει μοτίβα υλοποίησης και εμπειρικές οδηγίες για τους επαγγελματίες, ώστε να
επιλύσουν το kCPQ σε πολύ μεγάλα σύνολα σημείων.
Λέξεις-κλειδιά: k Closest Pairs Query (kCPQ), γεωχωρικά δεδομένα, Scala, Akka,
Plane Sweep, παράλληλος υπολογισμός, αξιολόγηση απόδοσης.

This thesis explores the efficient implementation of k Closest Pairs Query (kCPQ) on
large-scale geospatial datasets using parallel capabilities within Scala. Four solution
approaches are implemented and compared: serial Brute Force as baseline, a parallel
Brute Force version, Plane Sweep algorithm and parallel Plane Sweep. The parallel
designs leverage Scala's concurrency ecosystem (Futures/Promises, parallel collections
and actor-based patterns) for distributing work among CPU cores but controlling data
movement and result merging.
The synthetic two-set point datasets up to 115M and 120M points are stress-tested for
scalability challenges. The experiments were run on a workstation with an AMD Ryzen
9 7900X (12 cores), 32 GB RAM, and Windows 11 Pro. Evaluation varies dataset size,
k, number of threads, and chunk size/overlap to examine sensitivity across both CPU
bound and I/O-bound phases.
The benefits of Plane Sweep are clear: it is consistently superior with every size tested.
Parallel Plane Sweep comes next, followed by parallel Brute Force, with serial Brute
Force placed last. Overall, we see that size affects runtime growth more than k or thread
count have within the ranges examined. Chunk sizings/overlap do much to effect
performance in the parallel methods. On inputs of multi-million points, parallel Plane
Sweep cuts wall-clock time compared to the serial baseline while the serial Plane Sweep
still outpaces all formats when memory locality and sweep filtering are effective.
In summary, Scala has proven to be a viable avenue for efficient parallel geospatial
analytic processes; expressive, type-safe, and run native on JVM provides
interoperability. The study describes implementation patterns and empirical guidance
to practitioners to solve kCPQ over very large point sets.
Keywords: k Closest Pairs Query (kCPQ); geospatial data; Scala; Akka; Plane Sweep;
parallel computing; performance evaluation.