Your browser does not support JavaScript!

Αρχική    On Computing Deltas of RDF/S Knowledge Bases with Blank Nodes  

Αποτελέσματα - Λεπτομέρειες

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 000379744
Τίτλος On Computing Deltas of RDF/S Knowledge Bases with Blank Nodes
Άλλος τίτλος Υπολογίζοντας τις διαφορές μεταξύ βάσεων γνώσεων RDF με ανώνυμους κόμβους.
Συγγραφέας Λαντζάκη, Χριστίνα Αντώνιος
Σύμβουλος διατριβής Τζίτζικας, Ιωάννης
Περίληψη Ο Σημασιολογικός Ιστός (ΣΙ) είναι μια εξελισσόμενη επέκταση του Παγκόσμιου Ιστού στην οποία το περιεχόμενο μπορεί να εκφραστεί όχι μόνο με φυσική γλώσσα αλλά και με τυπικές γλώσσες (π.χ. RDF/S ), που επιτρέπουν την παροχή προηγ- μένων υπηρεσιών αναζήτησης, διαμοιρασμού και ολοκλήρωσης πληροφορίας. Η ρήση του Ηράκλειτου «τα πάντα ρει» ισχύει και στον ΣΙ, αφού οι πόροι (resources), οι οντο- λογίες, τα μεταδεδομένα διαρκώς αλλάζουν και εξελίσσονται. Εκ τούτου η ικανότητα υπολογισμού των διαφορών μεταξύ δύο Βάσεων Γνώσεων (ΒΓ) RDF/S , στο εξής Δέλτα, είναι πολύ σημαντική. Συγκεκριμένα, τα Δέλτα μπορούν (α) να βοηθήσουν τους χρήστες στην κατανόηση της εξέλιξης της γνώσης, και (β) να μειώσουν τον όγκο των δεδομένων που χρειάζεται να ανταλλαχθούν και διαχειριστούν στο δίκτυο για την ανάπτυξη υπηρεσιών συγχρονισμού, διαχείρισης εκδόσεων και αντιγράφων. Το πρόβλημα της σύγκρισης δεν είναι απλό διότι η RDF υποστηρίζει ανώνυμους κόμβους. ΄Ενας ανώνυμος κόμβος είναι ένας κόμβος σε ένα ΡΔΦ γράφο, ο οποίος δεν είναι ούτε URI, ούτε literal και επομένως δεν έχει εξωτερική ταυτότητα. Αρκετές βάσεις γνώσεων περιλαμβάνουν μεγάλο ποσοστό ανώνυμων κόμβων (π.χ. το 7.5% των Διασυνδεδεμένων Δεδομένων εκτιμάται ότι αντιστοιχεί σε ανώνυμους κόμβους), καθώς είναι κατάλληλοι για την αναπαράσταση σύνθετων γνωρισμάτων ή κόμβων των οποίων η ταυτότητα είναι άγνωστη, αλλά οι ιδιότητες τους (είτε literals ή συνδέσεις τους με άλλους κόμβους) είναι γνωστές. Η θεώρηση των ανώνυμων κόμβων σαν μοναδικές σταθερές στους δύο γράφους δε βοηθάει ούτε στον εντοπισμό ισοδύναμων γράφων, ούτε στη μείωση του Δέλτα. Αντιθέτως, με την αντιστοίχιση των ανώνυμων κόμβων του ενός γράφου με τους ανώνυμους κόμβους του άλλου γράφου μπορούμε να μειώσουμε σημαντικά το παραγόμενο Δέλτα. Η παρούσα εργασία είναι η πρώτη εργα- σία που εστιάζει σε μεθόδους αντιστοίχισης των ανώνυμων κόμβων προσεγγίζοντας το πρόβλημα ως πρόβλημα βελτιστοποίησης με στόχο την εύρεση της αντιστοίχι- σης που οδηγεί στο ελάχιστο σε μέγεθος Δέλτα (ελάχιστο πλήθος τριπλετών που πρέπει να διαγραφούν και να προστεθούν για να γίνουν οι δύο γράφοι ισοδύναμοι). Αποδεικνύουμε ότι η εύρεση της βέλτιστης αντιστοίχισης είναι NP-Hard στη γενική περίπτωση ανάγοντας το πρόβλημα της αντιστοίχισης στο πρόβλημα του ισομορφισμού υπογράφων. Επιπλέον αποδυκνείουμε ότι όταν οι γράφοι δεν περιέχουν ανώνυμους κόμβους που συνδέονται άμεσα μεταξύ τους (ήτοι, καμία τριπλέτα δεν περιέχει πε- ρισσότερους από έναν ανώνυμους κόμβους), τότε ο πολυωνυμικής πολυπλοκότητας Ουγγρικός αλγόριθμος μπορεί να δώσει τη βέλτιστη λύση. Για τη γενική περίπτωση προτείνουμε διάφορους πολυωνυμικούς αλγορίθμους, που μπορούν να λύσουν το πρό- βλημα προσεγγιστικά. Για να είναι εφικτή η εφαρμογή των μεθόδων μας ακόμα και σε πολύ μεγάλες βάσεις γνώσεων, που περιέχουν μεγάλο πλήθος ανώνυμων κόμβων, δίνουμε έναν προσεγγιστικό αλγόριθμο με NlogN πολυπλοκότητα ο οποίος βασίζεται σε υπογραφές. Τέλος, για τους προτεινόμενους αλγόριθμους, αναφέρουμε εκτεταμέ- να συγκριτικά πειραματικά αποτελέσματα επί πραγματικών και συνθετικά παραγμένων ΒΓ, σχετικά με τις επιδόσεις τους στη μείωση του Δέλτα (και την απόκλιση τους από το βέλτιστο), στον εντοπισμό ισοδύναμων γράφων, και τις υπολογιστικές τους 7 απαιτήσεις. Τα αποτελέσματα είναι πολύ ενδιαφέροντα. Ενδεικτικά, ο αλγόριθμος που βασίζεται σε υπογραφές μπορεί να αντιστοιχίσει βάσεις που έχουν μέχρι και 150 χιλιάδες ανώνυμους κόμβους σε λίγα δευτερόλεπτα και U% απόκλιση από το βέλτιστο.
Φυσική περιγραφή vi, 96 σ. : εικ., πίν. ; 30 εκ.
Γλώσσα Αγγλικά
Θέμα Bases RDF
Blank Nodes
Delta
Knowledge
RDF
Ανώνυμοι κόμβοι
Βάσεις γνώσης
Ημερομηνία έκδοσης 2013
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 164

Ψηφιακά τεκμήρια
No preview available

Προβολή Εγγράφου
Εμφανίσεις : 25