δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Η ανάλυση οντοτήτων είναι μια κρίσιμη εργασία σε διάφορες εφαρμογές, αλλά αντιμετω-
πίζει την τετραγωνική πολυπλοκότητα. Για να καταστεί εφικτή η ανάλυση οντοτήτων με
μεγάλα σύνολα δεδομένων, χρησιμοποιείται η ομαδοποίηση. Συντακτικές μέθοδοι ομαδο-
ποίησης (blocking) συνήθως οργανώνουν παρόμοιες οντότητες σε αλληλοκαλυπτόμενα
μπλοκ, μειώνοντας τον αριθμό των απαραίτητων συγκρίσεων. Περαιτέρω κέρδη απόδο-
σης επιτυγχάνονται με τη μετα-ομαδοποίηση (meta-blocking), το οποίο περιορίζει τις πε-
ριττές συγκρίσεις σε επικαλυπτόμενα μπλοκ, βελτιώνοντας σημαντικά την ακρίβεια χωρίς
να μειώνεται πολύ η ανάκληση.
Παρά τη χρονική του απόδοση, η εφαρμογή της μετα-ομαδοποίησης (meta-blocking) για
την επίλυση προβλημάτων επίλυσης οντοτήτων σε πολύ μεγάλα σύνολα δεδομένων πα-
ραμένει μια πρόκληση. Για παράδειγμα, η επεξεργασία 7,4 εκατομμυρίων οντοτήτων μπο-
ρεί να διαρκέσει σχεδόν οκτώ ολόκληρες ημέρες σε έναν διακομιστή υψηλής τεχνολογίας.
Σε αυτή τη διατριβή, εξετάζουμε την παραλληλοποίηση του python πακέτου PyJedAI. Η
Python εισάγει νέες προκλήσεις λόγω του Global Interpreter Lock (GIL) και της ανάγκης
να ενσωματωθεί ένα μοντέλο fork-join αντί της δημιουργίας πολλαπλών νημάτων. Χρησι-
μοποιούμε τη βιβλιοθήκη MPIRE για την υλοποίηση των παράλληλων αλγορίθμων μετα-
ομαδοποίησης σε python.
Η πειραματική ανάλυση επικυρώνει την επεκτασιμότητα της παράλληλης υλοποίησης κα-
θώς και τη σημαντική μείωση χρόνου σε ορισμένα στάδια της μετα-ομαδοποίησης. Επίσης,
θα αναλύσουμε και τα αδιέξοδα που συναντήσαμε στη χρονική απόδοση της υλοποίησής
μας λόγω του μοντέλου fork-join και πώς είναι δυνατόν να τα ξεπεράσουμε.
(EL)
Entity resolution is a critical task in various applications, but it faces quadratic complex-
ity. To make entity resolution scalable to large datasets, blocking is typically employed.
Syntactic blocking methods usually group similar entities into overlapping blocks, redu-
cing the number of necessary comparisons. Further efficiency gains are achieved with
Meta-blocking, which prunes unnecessary comparisons in overlapping blocks, signific-
antly improving precision without sacrificing much recall.
However, despite its time efficiency, applying Meta-blocking to solve entity resolution prob-
lems on very large datasets remains a challenge. For instance, processing 7.4 million
entities can take almost eight full days on a high-end server.
In this thesis, we work with the parallelization of the python framework PyJedAI. Python
introduces new challenges due to the Global Interpreter Lock (GIL) which forces us to
implement a fork-join model instead of generating multiple threads. We use the MPIRE
python module to implement the parallel Meta-blocking algorithms.
The experimental analysis validates the scalability of the parallel implementation as well
as the significant time reduction in certain steps of the Meta-blocking. We also analyze the
deadlocks we encountered in the time efficiency of our implementation due to the fork-join
model and how it is possible to get over them.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
PyJedAI Parallelization with MPIRE
PyJedAI Parallelization with MPIRE
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
