<img src='/~hdms2010/modules/languageicons/flags/el.png'  class="language-icon" alt="Ελληνικά" width="16" height="12" /><img src='/~hdms2010/modules/languageicons/flags/en.png'  class="language-icon" alt="English" width="16" height="12" />

Περιλήψεις Εργασιών


eXO: Αποκεντρωμένη Κοινωνική Δικτύωση με Αυτονομία, Κλιμακωσιμότητα και Αποδοτικότητα

Ανδρέας Λουπασάκης (Πανεπιστήμιο Πάτρας), Παναγιώτης Τριανταφύλλου (Πανεπιστήμιο Πάτρας)

Τα κοινωνικά δίκτυα απολαμβάνουν πρόσφατα τεράστιο ενδιαφέρον από την ερευνητική κοινότητα, τη βιομηχανία και τους χρήστες. Με τη σημερινή τους μορφή, οι χρήστες αναγκάζονται να ανεβάσουν το περιεχόμενό τους σε κεντρικούς ιστότοπους. Αυτό συνήθως προκαλεί την απώλεια ελέγχου του περιεχόμενου από τους χρήστες. Ήδη έχουν ξεκινήσει (και δικαστικές) διαμάχες αναφορικά με το ιδιοκτησιακό καθεστώς, την εκμετάλλευση του περιεχομένου από τους ιδιοκτήτες των ιστότοπων κοινωνικής δικτύωσης και το σεβασμό της ιδιωτικότητας χρηστών.

Με αυτήν την εργασία προσπαθούμε να απαντήσουμε στα ακόλουθα θεμελιώδη ερωτήματα: Είναι δυνατόν να σχεδιάσουμε και να υλοποιήσουμε αποκεντρωμένες υπηρεσίες κοινωνικής δικτύωσης που να σέβονται τα ιδιοκτησιακά δικαιώματα των χρηστών και να έχουν πλήρη έλεγχο του διαμοιραζόμενου περιεχομένου, ενώ παράλληλα να προσφέρουν υψηλές επιδόσεις και κλιμακωσιμότητα; Μπορεί αυτό να επιτευχθεί ενώ παρέχεται η δυνατότητα σε χρήστες να προσπελάζουν το περιεχόμενο του δικτύου, να το σχολιάζουν κατάλληλα μέσω επισημειώσεων (tags) και να αναζητούν σχετικό περιεχόμενο και χρήστες μέσω ερωτημάτων-κλειδολέξεων; Παρουσιάζουμε το σύστημα eXO, που αποτελείται από (α) αλγόριθμους κατανεμημένης δεικτοδότησης περιεχομένου, (β) αλγόριθμους για κατανεμημένα top-k ερωτήματα, (γ) κατάλληλους ορισμούς ομοιότητας που επιτρέπουν αφενός κοινωνικά χαρακτηριστικά να αναδειχτούν και αφετέρου την γρήγορη εκτέλεση ερωτημάτων, (δ) κατανεμημένους αλγόριθμους ανάκτησης σχετικού περιεχομένου, (ε) τεχνικές για την αποδοτική και κλιμακώσιμη διαχείριση επισημειώσεων και την εκμετάλλευσή τους για τον εμπλουτισμό ερωτημάτων χρηστών και (στ) τεχνικές για την ταυτοποίηση, δημιουργία και εκμετάλλευση προσωπικών δικτύων για τον εμπλουτισμό απαντήσεων στις ερωτήσεις χρηστών. Τέλος, παρουσιάζουμε πειραματικά αποτελέσματα αναφορικά με το κόστος επεξεργασίας ερωτημάτων στο υλοποιημένο σύστημα με πραγματικά δεδομένα, που καταδεικνύουν την κλιμακωσιμότητα του συστήματος. O πηγαίος κώδικας του eXO σύντομα 8α είναι διαθέσιμος στην κοινότητα.

PDF


PerK: Εξατομικευμένη Αναζήτηση σε Σχεσιακές Βάσεις Δεδομένων με βάση Λέξεις-Κλειδιά

Κώστας Στεφανίδης (Πανεπιστήμιο Ιωαννίνων), Μαρίνα Δρόσου (Πανεπιστήμιο Ιωαννίνων), Ευαγγελία Πιτουρά (Πανεπιστήμιο Ιωαννίνων)

Η αναζήτηση με βάση λέξεις-κλειδιά σε σχεσιακές βάσεις δεδομένων επιτρέπει στους χρήστες να βρουν χρήσιμη πληροφορία χωρίς να χρειάζεται να γνωρίζουν το σχήμα της βάσης ή να διατυπώνουν σύνθετα ερωτήματα. Όμως, αυτού του είδους η αναζήτηση είναι γενικά ασαφής και συχνά επιστρέφει ένα μεγάλο αριθμό αποτελεσμάτων τα οποία μπορεί να μη συνδέονται στενά με τις πληροφοριακές ανάγκες του χρήστη. Στην εργασία αυτή, προτείνουμε την εξατομίκευση αυτής της αναζήτησης μέσω της χρήσης προτιμήσεων. Συγκεκριμένα, για την διάταξη των αποτελεσμάτων της ερώτησης του χρήστη λαμβάνουμε υπόψη τόσο τη σχετικότητά τους ως προς την ερώτηση αλλά και τα ενδιαφέροντα του χρήστη όπως αυτά εκφράζονται μέσω προτιμήσεων. Για τη βελτίωση της ποιότητας των αποτελεσμάτων εισάγουμε επίσης τα παρακάτω δύο νέα μέτρα τα οποία αντιμετωπίζουν το αποτέλεσμα της ερώτησης ως σύνολο: (α) την κάλυψη, που εξετάζει το ποσοστό των ενδιαφερόντων του χρήστη που καλύπτει το σύνολο των αποτελεσμάτων και (β) τη διαφορετικότητα, που εξετάζει την ομοιότητα του περιεχομένου του συνόλου των αποτελεσμάτων. Στη συνέχεια, προτείνουμε έναν αλγόριθμο για την επεξεργασία ερωτήσεων ο οποίος εκμεταλλεύεται την σειρά προτίμησης μεταξύ των λέξεων-κλειδιών για να κατευθύνει την συνένωση σχετικών με την ερώτηση πλειάδων της βάσης. Δείχνουμε επίσης πως μπορούμε να μειώσουμε την πολυπλοκότητα του αλγορίθμου εκμεταλλευόμενοι επαναλαμβανόμενα κοινά υπολογιστικά βήματα. Τέλος, παρουσιάζουμε πειραματικά αποτελέσματα σχετικά με την αποδοτικότητας και την αποτελεσματικότητα της μεθόδου μας.

PDF




Αναθεωρώντας  την αποτίμηση XML ερωτημάτων χρησιμοποιώντας υλοποιημένες όψεις

Xiaoying Wu (New Jersey Institute of Technology), Δημήτρης Θεοδωράτος (New Jersey Institute of Technology), Wendy Hui Wang (Stevens Institute of Technology)

Η αποτίμηση ερωτημάτων χρησιμοποιώντας υλοποιημένες όψεις είναι μία καλά θεμελιωμένη τεχνική στο χώρο των βάσεων δεδομένων. Στην παρούσα εργασία, υιοθετούμε ένα πρόσφατο μοντέλο αποτίμησης XML ερωτημάτων που ονομάζεται μοντέλο ανεστραμμένων λιστών. Το μοντέλο αυτό σε συνδυασμό με ολιστικούς αλγορίθμους έχει αναδειχτεί στην πιο εξέχουσα τεχνική για την αποτίμηση ερωτημάτων σε μεγάλου μεγέθους XML δεδομένα αποθηκευμένα στο δίσκο. Στο πλαίσιο αυτό επικεντρωνόμαστε στο πρόβλημα της αποτίμησης ενός ερωτήματος χρησιμοποιώντας αποκλειστικά και μόνο μία ή περισσότερες υλοποιημένες όψεις και στο πρόβλημα της εύρεσης του καλύτερου τρόπου αποτίμησης του ερωτήματος από τις υλοποιημένες όψεις. Το πλαίσιο αυτό αναθεωρεί αυτά τα προβλήματα δεδομένου ότι απαιτούνται νέες συνθήκες για τη χρήση υλοποιημένων όψεων και νέες τεχνικές για την αποτίμηση των ερωτημάτων από τις υλοποιημένες όψεις. Προτείνουμε μια νέα τεχνική για την υλοποίηση των όψεων η οποία αποθηκεύει για κάθε κόμβο όψης μόνο την υπολίστα των XML κόμβων που είναι απαραίτητοι για να υλοποιηθεί η όψη. Προσδιορίζουμε ικανές και αναγκαίες συνθήκες για την απάντηση δενδρικών ερωτημάτων χρησιμοποιώντας υλοποιημένες όψεις με όρους ομοιομορφισμών από τις όψεις προς τα ερωτήματα. Προτείνουμε επιπλέον βελτιστοποιήσεις στο χρόνο και στο χώρο χρησιμοποιώντας bitmaps για την υλοποίηση των όψεων και bitmap πράξεων στην αποτίμηση των ερωτημάτων. Τέλος, πραγματοποιήσαμε μία εκτεταμένη πειραματική ανάλυση που καταδεικνύει ότι η προσέγγιση πετυχαίνει εντυπωσιακή χρήση των αποθηκευμένων όψεων, κατορθώνει σημαντικές μειώσεις σε χρόνο αποτίμησης και χώρο αποθήκευσης και επιδεικνύει ομαλή κλιμάκωση.

PDF




Ανωνυμοποίηση για την προστασία της ιδιωτικότητας σε πλειότιμα δεδομένα.

Μανόλης Τερροβίτης (ΙΠΣΥΠ Ε.Κ. Αθηνά), Νίκος Μαμουλής (University of Hong Kong), Πάνος Καλνής (KAUST)

Σε αυτό το άρθρο μελετάμε το πρόβλημα της προστασίας της ιδιωτικότητας στην δημοσίευση πλειότιμων δεδομένων. Ας υποθέσουμε μία συλλογή από δεδομένα δοσοληψιών που περιέχουν λεπτομερείς πληροφορίες για προϊόντα που έχουν αγοραστεί μαζί από πρόσωπα. Ακόμη και αν αφαιρέσουμε όλα τα ατομικά χαρακτηριστικά του αγοραστή, τα οποία μπορούν να οδηγήσουν στην ταυτότητα του, η δημοσίευση τέτοιων δεδομένων είναι ακόμη έκθετη σε επιθέσεις αντιπάλων που έχουν μερική γνώση για τα δεδομένα. Σε αντίθεση με τις περισσότερες προηγούμενες εργασίες, δεν διακρίνουμε τα δεδομένα σε ευαίσθητα και μη-ευαίσθητα, αλλά θεωρούμε ότι μπορούν να λειτουργήσουν ταυτόχρονα και σαν ψευδοαναγνωστικά και σαν ευαίσθητα δεδομένα, ανάλογα με την προοπτική που αντιπάλου. Ορίζουμε μία νέα εκδοχή της εγγύησης k-ανωνυμία, την km-ανωνυμία, που περιορίζει τις επιδράσεις των πολλών διαστάσεων των δεδομένων και προτείνουμε αποδοτικούς αλγορίθμους για τον μετασχηματισμό της βάσης. Το μοντέλο ανωνυμοποίησης βασίζεται στην γενίκευση αντί στην απόκρυψη, που είναι η συνηθέστερη πρακτική σε συγγενείς εργασίες σε τέτοια δεδομένα. Αρχικά, αναπτύσσουμε έναν αλγόριθμο, ο οποίος βρίσκει την βέλτιστη λύση, αλλά με τέτοιο υπολογιστικό κόστος που καθίσταται ανεφάρμοστος για μεγάλα, ρεαλιστικά προβλήματα. Στην συνέχεια προτείνουμε δύο άπληστους ευριστικούς αλγορίθμους που κλιμακώνονται πολύ καλύτερα και στις περισσότερες περιπτώσεις βρίσκουν λύση κοντά στην βέλτιστη. Οι προτεινόμενοι αλγόριθμοι αξιολογούνται πειραματικά με πραγματικά δεδομένα.

PDF




Αποδοτικοί Αλγόριθμοι για Επερωτήσεις Αντίστροφων Κορυφαίων-Κ

Ακριβή Βλάχου (Norwegian University of Science and Technology), Χρήστος Δουλκερίδης (Norwegian University of Science and Technology), Γιάννης Κωτίδης (Οικονομικό Πανεπιστήμιο Αθηνών), Kjetil Nørvåg (Norwegian University of Science and Technology)

Η επεξεργασία επερωτήσεων κατάταξης είναι σημαντική για πολλές εφαρμογές που ανακτούν τα κορυφαία-Κ αντικείμενα με βάση τις ιδιαίτερες προτιμήσεις του κάθε χρήστη. Οι επερωτήσεις κορυφαίων-Κ έχουν μελετηθεί κυρίως από την οπτική του χρήστη, εστιάζοντας στην αποδοτική επεξεργασία. Σε αυτή την εργασία, για πρώτη φορά, μελετούμε τις επερωτήσεις κορυφαίων-Κ από την οπτική του κατασκευαστή προϊόντων. Δοθέντος ενός προϊόντος, για ποιες προτιμήσεις χρηστών ανήκει αυτό το προϊόν στα κορυφαία-Κ προϊόντα; Προτείνουμε έναν καινούργιο τύπο επερωτήσεων, που καλείται επερώτηση αντίστροφων κορυφαίων-Κ και είναι ουσιώδης για κατασκευαστές, ώστε να αποτιμήσουν την αγορά και τον αντίκτυπο των προϊόντων τους με βάση τον ανταγωνισμό. Διατυπώνουμε με τυπικό τρόπο τις επερωτήσεις αντίστροφων κορυφαίων-Κ και εισάγουμε δύο παραλλαγές της επερώτησης, μονοχρωματική και διχρωματική. Αρχικά, παρέχουμε τη γεωμετρική ερμηνεία της μονοχρωματικής επερώτησης αντίστροφων κορυφαίων-Κ στο χώρο λύσης, υποβοηθώντας την κατανόησή της εννοιολογικά. Στη συνέχεια, μελετούμε σε μεγαλύτερη λεπτομέρεια την περίπτωση της διχρωματικής επερώτησης αντίστροφων κορυφαίων-Κ, που είναι περισσότερο ενδιαφέρουσα για πρακτικές εφαρμογές. Μια τέτοια επερώτηση, εφόσον υπολογισθεί με απλό τρόπο, απαιτεί την αποτίμηση μιας επερώτησης κορυφαίων-Κ για κάθε προτίμηση χρήστη στη βάση δεδομένων, που έχει απαγορευτικό κόστος ακόμη και για σύνολα δεδομένων μέτριου μεγέθους. Σε αυτό το άρθρο, παρουσιάζουμε ένα αποδοτικό αλγόριθμο με χρήση κατωφλιού που εξαλείφει υποψήφιες προτιμήσεις χρηστών, δίχως την επεξεργασία των αντίστοιχων επερωτήσεων κορυφαίων-Κ. Επιπρόσθετα, προτείνουμε μια δομή ευρετηρίασης που στηρίζεται σε αποθηκευμένες όψεις αντίστροφων κορυφαίων-Κ για να επιταχύνουμε την επεξεργασία επερωτήσεων. Οι αποθηκευμένες όψεις αντίστροφων κορυφαίων-Κ προσθέτουν κόστος προεπεξεργασίας για να κερδίσουν επιτάχυνση στην επεξεργασία επερωτήσεων, με ελεγχόμενο τρόπο. Η πειραματική μας αποτίμηση δείχνει την αποδοτικότητα των τεχνικών μας, οι οποίες μειώνουν τον απαιτούμενο αριθμό υπολογισμών κορυφαίων-Κ από μία έως τρεις τάξεις μεγέθους.

PDF




Αποδοτικοί Φυσικοί Τελεστές για Εκτέλεση Επερωτήσεων XPath

Χάρης Γεωργιάδης (Οικονομικό Πανεπιστήμιο Αθηνών), Μηνάς Χαραλαμπίδης (Οικονομικό Πανεπιστήμιο Αθηνών), Βασίλης Βασσάλος (Οικονομικό Πανεπιστήμιο Αθηνών)

Η δημιουργία μιας γενικής και σπονδυλωτής υποδομής βελτιστοποίησης και επεξεργασίας επερωτήσεων μπορεί να δώσει σημαντικά οφέλη στην επεξεργασία δεδομένων XML. Κομβικά δομικά στοιχεία μιας τέτοιας αρχιτεκτονικής είναι οι φυσικοί τελεστές που είναι διαθέσιμοι στη μηχανή εκτέλεσης, για να χρησιμοποιηθούν στα πλάνα εκτέλεσης επερωτήσεων. Οι τελεστές, για να είναι αποδοτικοί, πρέπει να υλοποιούν εξελιγμένους αλγορίθμους για τους λογικούς τελεστές της XPath ή της XQuery. Επιπλέον, για να επιτρέψουν σε ένα κοστοστρεφή βελτιστοποιητή να επιλέξει μεταξύ διαφορετικών φυσικών τελεστών, κάθε υλοποίηση φυσικού τελεστή πρέπει να συνοδεύεται από μοντέλο κόστους.

Σε αυτό το άρθρο παρουσιάζουμε δυο οικογένειες αλγορίθμων για φυσικούς τελεστές της γλώσσας XPath, ονόματι LookUp (LU) και Sort-Merge-based (SM) μαζί με λεπτομερή μοντέλα κόστους. Οι αλγόριθμοί μας έχουν σημαντικά καλύτερες επιδόσεις από υπάρχουσες τεχνικές όταν υλοποιούνται πάνω από μια πληθώρα διαφορετικών μηχανών αποθήκευσης XML που προσφέρουν ένα κοινό σύνολο από βασικές μεθόδους πρόσβασης. Για να επιβεβαιώσουμε την ευρωστία και την αποτελεσματικότητα των φυσικών τελεστών που προτείνουμε, αξιολογούμε τις επιδόσεις τους πάνω από τέσσερις διαφορετικές μηχανές αποθήκευσης XML έναντι τελεστών που έχουν υλοποιηθεί χρησιμοποιώντας υπάρχοντες αλγορίθμους επεξεργασίας XML. Αποδεικνύουμε επίσης πειραματικά τις καλύτερες επιδόσεις πλάνων που χρησιμοποιούν τους δικούς μας τελεστές και αλγορίθμους επεξεργασίας συγκριτικά με τις πιο προηγμένες τεχνικές twig processing, και συγκεκριμένα την τεχνική Twig2Stack. Τέλος, αξιολογούμε την ακρίβεια των μοντέλων κόστους μας και πραγματοποιούμε ανάλυση ευαισθησίας των αλγορίθμων μας σε διάφορες παραμέτρους.

PDF


Βελτιστοποίηση Συναλλαγών με υψηλές απαιτήσεις λειτουργίας Εισόδου/Εξόδου σε έντονα διαδραστικές εφαρμογές.

Mohamed A. Sharaf (University of Pittsburgh), Πάνος Κ. Χρυσάνθης (University of Pittsburgh), Αλέξανδρος Λαμπρινίδης (University of Pittsburgh), Cristiana Amza (University of Toronto)

Η επίδοση που επιτυγχάνεται από ένα διαδραστικό διαδικτυακό σύστημα βάσεων δεδομένων τυπικά μετριέται στον βαθμό ικανοποίησης κάποιων προκαθορισμένων Συμφωνιών Επιπέδου Υπηρεσιών (ΣΕΥ). Ο πιο κοινός τύπος ΣΕΥ είναι η αναμενόμενη καθυστέριση εκτέλεσης κάποιας συναλλαγής. Αυτή η μορφή ΣΕΥ διαδραματίζει τον ρόλο χαλαρής προθεσμίας για κάθε συναλλαγή, και η ικανοποίηση του χρήστη από την υπηρεσία μπορεί να μετρηθεί ως συνάρτηση της ελαχιστοποίησης της καθυστέρισης ή βραδύτητας, δηλαδή της απόκλισης από τη ΣΕΥ. Αυτός ο αντικειμενικός στόχος περιπλέκεται ακόμα περισσότερο σε συναλλαγές με υψηλές απαιτήσεις λειτουργίας εισόδου/εξόδου (Ε/Ε), όπου το σύστημα αποθήκευσης δεδομένων καθίσταται ανασχετικός παράγοντας. Επιπλέον, οι διαδεδομένες  τακτικές δρομολόγισης αιτημάτων Ε/Ε τις οποίες χρησιμοποιούν τα Λειτουργικά Συστήματα για την βελτιστοποίηση της απόδωσης έργου ή της μέσης επιβράδυνσης μπορούν να λειτουργούν αντίθετα στην βελτιστοποίηση της ανα-συναλλαγής επίδοσης αφού συνήθως το Λειτουργικό Σύστημα δεν αναγνωρίζουν τα ΣΕΥ που είναι καθορισμένα σε επίπεδο εφαρμογών. Σε αυτή την εργασία, προτείνουμε μια καινοτομική τακτική δρομολόγισης αιτημάτων Ε/Ε για συναλλαγές βάσεων δεδομένων η οποία λαμβάνει υπ΄'οψη τα ΣΕΥ. Η προτεινόμενη τακτική συνδιάζει τακτικές δρομολόγισης  συναλλαγών βάσεων δεδομένων με προθεσμίες, με χαρακτηριστηκά από τακτικές δρομολόγησης που χρησιμοποιούνται σε Λειτουργικά Συστήματα για την βελτιστοποίηση του παραγόμενου έργου από αιτήματα Ε/Ε. Αυτό επιτρέπει στην προτεινόμενη τακτική δρομολόγισης να προσαρμόζεται δυναμικά στο φόρτο εργασίας και συνεπώς να παρέχει την καλύτερη επίδοση.

PDF




Βελτιώνοντας την κλιμάκωση του OLTP χρησιμοποιώντας εικοτολογική κληρονόμηση κλειδιών

Ιπποκράτης Πανδής (Carnegie Mellon University), Ryan Johnson (Carnegie Mellon University), Αναστασία Αϊλαμάκη (Ecole Polytechnique Fédérale de Lausanne)

Οι φόρτοι εργασίας εξυπηρέτησης δοσοληψιών παρέχουν επαρκές επίπεδο ταυτοχρονισμού το οποίο οι παράλληλες αρχιτεκτονικές θα μπορούσαν να αξιοποιήσουν. Όμως, η έντονη χρήση των εσωτερικών υπηρεσιών του συστήματος εξυπηρέτησης δοσοληψιών προκαλεί ανταγωνισμό μεταξύ των διαφόρων νημάτων και περιορίζει την κλιμάκωση της ρυθμαπόδοσης. Πολλοί φόρτοι εργασίας εξυπηρέτησης δοσοληψιών αποτελούνται από σύντομες δοσοληψίες οι οποίες απαιτούν πρόσβαση σε λίγες πλειάδες της βάσης, απαιτώντας ως επί το πλείστον πολύ σύντομο χρόνο απάντησης. Ο χρόνος απάντησης καθορίζεται σε μεγάλο βαθμό από τις λειτουργικές επιβαρύνσεις που προσθέτουν υπηρεσίες του συστήματος επεξεργασίας συναλλαγών όπως η διατήρηση ημερολογίου, η διαχείριση κλειδιών και συναλλαγών.

Αυτή η εργασία τονίζει την αρνητική επίδραση στην κλιμάκωση από την διαχείριση κλειδιών του συστήματος εξυπηρέτησης δοσοληψιών, μια συνέπεια ιδιαίτερα σοβαρή σε φόρτους εργασίας σύντομων δοσοληψιών που διεξάγονται σε πολυ-πύρηνο υλικό υπολογιστών. Προτείνουμε και αξιολογούμε την ‘Εικοτολογική Κληρονόμηση Κλειδιών’ (ΕΚΚ) μια τεχνική η οποία μεταφέρει τα δημοφιλή κλειδιά από συναλλαγή σε συναλλαγή αποφεύγοντας την αλληλεπίδραση με τον διαχειριστή κλειδιών. Υλοποιούμε την ΕΚΚ στο Shore-MT σύστημα αποθήκευσης δεδομένων. Δείχνουμε πως η ΕΚΚ βελτιώνει σημαντικά την κλιμάκωση διαχωρίζοντας το πλήθος των αιτημάτων για δημοφιλή κλειδιά από το πλήθος των νημάτων στο σύστημα, εξαλείφοντας έτσι τον ανταγωνισμό μέσα στο διαχειριστή κλειδιών. Επιτυγχάνουμε αυτό το αποτέλεσμα μόνο με μικρές αλλαγές στον διαχειριστή κλειδιών και χωρίς αλλαγές στη συνέπεια ή σε άλλα αποτελέσματα φανερά στην εφαρμογή.

PDF


Δεδομενο-κεντρική εκτέλεση δοσοληψιών

Ιπποκράτης Πανδής (Carnegie Mellon University), Ryan Johnson (Carnegie Mellon University), Νίκος Χαρδαβέλλας (Northwestern University), Αναστασία Αϊλαμάκη (Ecole Polytechnique Fédérale de Lausanne)

Ενώ την τελευταία δεκαετία έχουν γίνει σημαντικότατες αλλαγές στις τεχνολογίες υλικού υπολογιστών, ο σχεδιασμός των συστημάτων εκτέλεσης δοσοληψιών έχει παραμείνει σχεδόν αμετάβλητος. Το πλήθος των επεξεργαστικών πυρήνων αυξάνεται εκθετικά, ακολουθώντας το νόμο του Moore, επιτρέποντας σε ένα αυξανόμενο πλήθος δοσοληψιών να εκτελείται παράλληλα. Καθώς το πλήθος των παράλληλα εκτελούμενων δοσοληψιών αυξάνει, ο ανταγωνισμός μεταξύ των νημάτων για κρίσιμα τμήματα κώδικα γίνεται εμπόδιο για την κλιμάκωση της ρυθμαπόδοσης του συστήματος. Στα συμβατικά συστήματα εκτέλεσης δοσοληψιών συχνά ο κεντρικός διαχειριστής κλειδιών είναι η πρώτη συνιστώσα του συστήματος στην οποία παρατηρούνται ανταγωνισμοί μεταξύ νημάτων και γίνεται εμπόδιο στην κλιμάκωση.

Σε αυτή την εργασία, καταδικνίουμε την συμβατική μέθοδο ανάθεσης εργασίας νήματος σε δοσοληψία, ως την βασική υπαίτιο για τους ανταγωνισμούς στο σύστημα. Εν συνεχεία, σχεδιάζουμε το DORA, ένα σύστημα το οποίο κατακερματίζει κάθε δοσοληψία σε μικρότερα κομμάτια ή ενέργειες και αναθέτει τις ενέργειες σε νήματα ανάλογα με το ποια δεδομένα κάθε ενέργεια πρόκειται να προσπελάσει. Το αποτέλεσμα της αλλαγής του τρόπου ανάθεσης εργασίας σε νήματα, επιτρέπει στα νήματα να προσπελαύνουν ως επί το πλείστον ιδιωτικές δομές δεδομένων, και ελαχιστοποιεί την αλληλεπίδραση με τον κεντρικό διαχειριστή κλειδιών. Λειτουργώντας πάνω από ένα συμβατικό σύστημα αποθήκευσης δεδομένων, το DORA διατηρεί τις ACID ιδιότητες. Η αξιολόγηση ενός DORA πρωτοτύπου δείχνει ότι το DORA επιτυγχάνει έως και 4.6 φορές υψηλότερη ρυθμαπόδοση από ένα προηγμένης τεχνολογίας σύστημα αποθήκευσης δεδομένων σε ένα πλήθος φόρτων εργασίας OLTP, όπως οι δοκιμασίες επιδόσεων TPC-C, TPC-B, και TM1.

PDF


Δένδρα Επεξεργασίας Ερωτημάτων με Ελάχιστα Hotspots σε Ασύρματα Δίκτυα Αισθητήρων

Γεώργιος Χατζημηλιούδης (University of California Riverside), Δημήτρης Ζεϊναλιπούρ (Πανεπιστήμιο Κύπρου), Δημήτριος Γουνόπουλος (Πανεπιστήμιο Αθηνών)

Σε αυτό το άρθρο παρουσιάζουμε έναν κατανεμημένο αλγόριθμο για την δημιουργία ενός ισοζυγισμένου δένδρου επικοινωνίας που αποσκοπεί στην συλλογή δεδομένων από ένα ασύρματο δίκτυο αισθητήρων. Ο αλγόριθμος αυτός έχει ελάχιστο κόστος εκτέλεσης και το απορρέον δένδρο επικοινωνίας έχει σχεδόν βέλτιστη ισορροπία. Κατά την συλλογή δεδομένων κάθε σύγκρουση μεταξύ πακέτων προκαλεί την επαναποστολή τους. Η ίση κατανομή των βαθμών μεταξύ των κόμβων στο δένδρο επικοινωνίας έχει ως αποτέλεσμα την ελαχιστοποίηση των συγκρούσεων αυτών και συνεπώς την εξοικονόμηση ενέργειας και την αύξηση του χρόνου ζωής του ασύρματου δικτύου αισθητήρων. Συγκρίνουμε τον αλγόριθμό μας με έναν υπάρχον αλγόριθμο και έναν κεντρικό αλγόριθμο. Τα αποτελέσματα δείχνουν ότι ο αλγόριθμός μας υπερέχει του ανταγωνισμού για την πλειοψηφία των δικτυακών τοπολογιών και επιτυγχάνει σχεδόν βέλτιστη ισορροπία στο δέντρο. Επίσης, έχει το ελάχιστο δυνατό κόστος εκτέλεσης συντελώντας έτσι ακόμα περισσότερο στην εξοικονόμηση ενέργειας στο δίκτυο.

PDF




Δημιουργώντας Κώδικα για Ολιστική Επεξεργασία Επερωτήσεων

Κωνσταντίνος Κρικέλλας (Greenplum Inc.), Στρατής Δ. Βίγλας (University of Edinburgh), Marcelo Cintra (University of Edinburgh)

Παρουσιάζουμε την εφαρμογή δημιουργίας προσαρμοσμένου κώδικα για επεξεργασία επερωτήσεων. Η βασική ιδέα είναι η χρησιμοποίηση μίας συλλογής από πρότυπα κώδικα υψηλής απόδοσης και η δυναμική συγκεκριμενοποίησή τους προκειμένου να δημιουργήσουμε κώδικα προσαρμοσμένο στην επερώτηση και στο υλικό. Ο κώδικας μεταφράζεται και συνδέεται με τον εξυπηρετητή της βάσης για επεξεργασία της επερώτησης. Η δημιουργία κώδικα ελαχιστοποιεί την επίδραση των αφαιρέσεων υψηλού επιπέδου που είναι αναγκαίες για την υλοποίηση γενικευμένων μηχανών επεξεργασίας επερωτήσεων που βασίζονται στη μεταγλώττιση SQL. Επιπλέον, ο κώδικας που δημιουργείται είναι προσαρμοσμένος στο υλικό που θα τον εκτελέσει. Αυτή την προσέγγιση την ονοματίζουμε ολιστική επεξεργασία επερωτήσεων. Παρουσιάζουμε το σχεδιασμό και την ανάπτυξη ενός πρωτότυπου συστήματος που ονομάζεται HIQUE: η ολιστική ολοκληρωμένη μηχανή επεξεργασίας επερωτήσεων (Holistic Integrated Query Engine), η οποία βασίζεται στις προτάσεις μας. Κάνουμε μία λεπτομερή πειραματική μελέτη της απόδοσης του συστήματος. Τα αποτελέσματά μας δείχνουν ότι η HIQUE ικανοποιεί όλους τους στόχους σχεδιασμού της, ενώ η απόδοσή της είναι καλύτερη από αυτή τόσο καθιερωμένων όσο και νέων τεχνικών επεξεργασίας επερωτήσεων.

PDF




Διαχείριση  Υπερφόρτισης σε Κατανεμημένα Συστήματα Επεξεργασίας Ροών Δεδομένων

Γιάννης Δρούγκας (Environmental Systems Research Institute), Βάνα Καλογεράκη (Οικονομικό Πανεπιστήμιο Αθηνών)

Τα κατανεμημένα συστήματα επεξεργασίας ροών δεδομένων τα τελευταία χρόνια έχουν γίνει  ιδιαίτερα σημαντικά, αφού εφαρμογές όπως εφαρμογές πολυμέσων, συστήματα παρακολούθησης δικτύων αισθητήρων, καθώς και συστήματα ανάλυσης δεδομένων, βασίζονται όλο και περισσότερο στην επεξεργασία και ανάλυση δεδομένων σε πραγματικό χρόνο. Σε αυτήν την εργασία παρουσιάζουμε το σύστημα BARRE (Burst Accommodation through Rate REconfiguration), το σύστημα που έχουμε αναπτύξει για την αντιμετώπιση του προβλήματος της υπερφόρτισης σε κατανεμημένα συστήματα ροών δεδομένων. Με την εμφάνιση υψηλού φόρτου, το BARRE κάνει κρατήσεις πόρων δυναμικά στο κατανεμημένο σύστημα, ανάλογα με τις απαιτήσεις των εφαρμογών και τη διαθεσιμότητα των πόρων. Τα πειραματικά μας αποτελέσματα πάνω από το κατανεμημένο σύστημα Synergy δείχνουν την αποτελεσματικότητα της προσέγγισης μας. 

PDF




Ένα Κατανεμημένο, Ανεκτικό σε Σφάλματα Σύστημα Αποθήκης Δεδομένων

Κατερίνα Δόκα (ΕΜΠ), Δημήτριος Τσουμάκος (ΕΜΠ), Νεκτάριος Κοζύρης (ΕΜΠ)

Στην εργασία αυτή παρουσιάζουμε το Brown Dwarf,ένα κατανεμημένο σύστημα δεικτοδότησης, αποθήκευσης και ανανέωσης πολυδιάστατων δεδομένων (κύβων) σε ένα αδόμητο δίκτυο ομοτίμων, χωρίς τη χρήση κάποιου εξειδικευμένου εργαλείου. Το σύστημά μας κατανέμει μια πολυ αποδοτική κεντρική δομή δεικτοδότησης μεταξύ κόμβων καθώς διαβάζονται οι εγγραφές, μειώνοντας τον απαιτούμενο χρόνο για τη δημιουργία του κύβου και τις επερωτήσεις σε αυτόν, επιβάλλοντας παραλληλοποίηση. Ερωτήματα σημείων αλλά και διαστημάτων απαντώνται μέσω συνεργαζόμενων κόμβων που κρατούν μέρος ενός κύβου δεδομένων. Οι ανανεώσεις εκτελούνται καθώς συμβαίνουν, εξαλείφοντας την συνήθως δαπανηρή διαδικασία εκτός λειτουργίας του συστήματος. Το σύστημα επιπλέον χρησιμοποιεί μια μέθοδο αντιγραφής που προσαρμόζεται σε ξαφνικές αλλαγές της πόλωσης του φορτιου αλλά και σε αστοχίες κόμβων. Η αρχική μας αξιολόγηση αποδεικνύει ότι το Brown Dwarf, επιφέροντας μια μικρή μόνο επιβάρυνση αποθηκευτικού χώρου σε σχέση με τον κεντρικοποιημένο αλγόριθμο, επιταχύνει τη δημιουργία του κύβου μέχρι 5 φορές και των επερωτήσεων πολλές δεκάδες φορές εκμεταλλευόμενο τις δυνατότητες των διαθέσιμων δικτυακών κόμβων που δουλέυουν παράλληλα. Επίσης επιτυγχάνει τη γρήγορη προσαρμογή του ακόμα και μετά από αναπάντεχες αυξομειώσεις του φορτίου και παραμένει ανεπηρρέαστο από ένα σημαντικό ποσοστό συχνών αστοχιών κόμβων. Αυτά τα πλεονεκτήματα γίνονται πιο εμφανή για πυκνούς κύβους και πολωμένα φορτία.

PDF




Εναποθήκευση δυναμκής πληροφορίας σε δίκτυα οχημάτων (VANET)

Νικόλας Λουλλούδης (Πανεπιστήμιο Κύπρου), Γεώργιος Πάλλης (Πανεπιστήμιο Κύπρου), Μάριος Δ. Δικαιάκος (Πανεπιστήμιο Κύπρου)

Η μετάδοση περιεχομένου μεταξύ οχημάτων αποτελεί μία από τις πιο υποσχόμενες εφαρμογές δημιουργώντας νέες προοπτικές στην επικοινωνία μεταξύ των οχημάτων. Η απόκτηση καθολικής ή ακόμα και μερικής πληροφορίας σχετικά με την οδική κυκλοφορία, προνοεί τη δημιουργία ενός μεγάλου αριθμού ερωτημάτων που έχουν ως αποτέλεσμα την επιβάρυνση του ασύρματου δικτύου και ακολούθως την υποβίβαση της επίδοσης καθώς και της ποιότητας των υπηρεσιών που παρέχονται από ένα δίκτυο οχημάτων (VANET). Σε αυτή την εργασία, αξιολογούμε την επίδραση της εναποθήκευσης των δεδομένων στα VANETs. Μέσω ενός αναλυτικού περιβάλλοντος προσομοίωσης σε μεγάλης κλίμακας αστικά οδικά δίκτυα κάτω από ρεαλιστικές συνθήκες κίνησης αξιολογούμε τα πλεονεκτήματα της εναποθήκευσης της οδικής πληροφορίας διά μέσου του VITP, ενός πρωτοκόλλου επικοινωνίας για VANET, το οποίο επεκτείνουμε με σκοπό την υποστήριξη εναποθήκευσης. Τα αποτελέσματα προσδιορίζουν τις κρίσιμες παραμέτρους που επηρεάζουν τη ποιότητα της οδικής πληροφορίας και επιδεικνύουν τη βιωσιμότητα καθώς και την αποτελεσματικότητα του VITP.

PDF




Ενεργειακά-επικερδής τοποθέτηση τελεστών και εκπομπή αποτελεσμάτων ερωτημάτων διάρκειας.

Παναγιώτης Νεοφύτου (University of Pittsburgh), Mohamed Sharaf (University of Pittsburgh), Πάνος Κ. Χρυσάνθης (University of Pittsburgh), Αλεξανδρος Λαμπρινίδης (University of Pittsburgh)

Η επισήμανση πολύπλοκων γεγονότων μέσα από ροές δεδομένων έχει ευρέως διαδοθεί με τη χρήση αισθητήρων, ασύρματων επικοινωνιών και τη διάδοση ποικίλων φορητών συσκευών. Συνήθως, τέτοια επισήμανση γεγονότων επιτυχάνεται με τη βοήθεια κάποιου Εξυπηρετητή Διαχείρισης Ροών Δεδομένων, ο οποίος εκτελεί ερωτήματα διάρκειας, που έχουν υποβληθεί προηγουμένως από τους χρήστες. Σε αυτή την εργασία, μελετούμε το σενάριο όπου οι χρήστες υποβάλλουν τα ερωτήματά τους από φορητές συσκευές. Τα αποτελέσματα των ερωτημάτων διάρκειας, τα οποία είναι υπό την μορφή ξεχωριστών ροών δεδομένων, επιστρέφονται στους χρήστες μέσω ενός συμμερισμένου (κοινού) μέσου ασύρματης εκπομπής. Συγκεκριμένα, προτείνουμε τρεις ενεργειακά-ευαίσθητους αλγορίθμους τοποθέτησης τελεστών ερωτημάτων. Οι αλγόριθμοι αυτοί προσδιορίζουν ποιο μέρος ενός σχεδίου εκτέλεσης ερωτημάτων διάρκειας θα εκτελεστεί στον εξυπηρετητή διαχείρισης ροών δεδομένων και ποιο στη φορητή συσκευή του χρήστη. Η αποτελεσματικότητα των αλγορίθμων σε σχέση με την κατανάλωση ενέργειας αξιολογήθηκε με τη χρήση εξομοιωτή.

PDF




Εξαρτώμενα από το περιβάλλον πιθανοτικά ερωτήματα κορυφογραμμής

Δημήτρης Σαχαρίδης (ΙΠΣΥΠ Ε.Κ. Αθηνά), Αναστάσιος Αρβανίτης (Εθνικό Μετσόβιο Πολυτεχνείο), Τίμος Σελλής (ΙΠΣΥΠ Ε.Κ. Αθηνά & Εθνικό Μετσόβιο Πολυτεχνείο)

Ένα ερώτημα κορυφογραμμής επιστρέφει τις πιο "ενδιαφέρουσες" εγγραφές σύμφωνα με ένα σύνολο ρητά προσδιορισμένων προτιμήσεων στις τιμές των γνωρισμάτων τους. Η συγκεκριμένη εργασία χαλαρώνει αυτή την απαίτηση επιτρέποντας στους χρήστες να θέτουν ερωτήματα κορυφογραμμής χωρίς να εκφράζουν ρητά τις προτιμήσεις τους. Προς αναπλήρωση της ελλιπούς γνώσης για τις προτιμήσεις των χρηστών, αρχικά διαμορφώνουμε ένα σύνολο αβέβαιων προτιμήσεων βασισμένων σε πληροφορία που έχουμε συλλέξει από τους χρήστες σε προηγούμενες καταστάσεις (contexts). Στη συνέχεια, δίνουμε τον ορισμό ενός "εξαρτώμενου από το περιβάλλον πιθανοτικού ερωτήματος κορυφογραμμής" (PCSQ) το οποίο επιστρέφει τις εγγραφές που θα ενδιέφεραν ένα χρήστη με μεγάλη πιθανότητα. Δίνουμε έμφαση στο γεγονός ότι σε αντίθεση με προηγούμενες εργασίες, η αβεβαιότητα έγκειται στο ίδιο το ερώτημα και όχι στα δεδομένα, δηλαδή βρίσκεται στις σχέσεις προτίμησης μεταξύ των εγγραφών και όχι στις τιμές των γνωρισμάτων τους. Επιπλέον, εξαιτίας της φύσης αυτής της αβεβαιότητας, οι κλασικές μέθοδοι αποτίμησης ερωτημάτων κορυφογραμμής οι οποίες βασίζονται σε μια συγκεκριμένη διάταξη επίσκεψης των εξεταζόμενων εγγραφών, δεν μπορούν να εφαρμοστούν στα PCSQs. Για το λόγο αυτό, παρουσιάζουμε ένα σύνολο νέων αλγορίθμων, βασισμένων ή όχι σε δεικτοδότηση των εξεταζόμενων δεδομένων, για την αποτίμηση PCSQs. Με βάση την πειραματική αξιολόγηση προκύπτει το συμπέρασμα ότι οι προτεινόμενοι αλγόριθμοι είναι σημαντικά πιο αποδοτικοί συγκρινόμενοι με μια απλή μέθοδο εμφωλευμένων βρόχων.

PDF




Εξέλιξη οντολογιών σε συστήματα ολοκλήρωσης πληροφορίας

Χαρίδημος Κονδυλάκης (Πανεπιστήμιο Κρήτης & Ίδρυμα Τεχνολογίας και Έρευνας), Δημήτρης Πλεξουσάκης (Πανεπιστήμιο Κρήτης & Ίδρυμα Τεχνολογίας και Έρευνας), Γιάννης Τζίτζικας (Πανεπιστήμιο Κρήτης & Ίδρυμα Τεχνολογίας και Έρευνας)

Λόγω της ταχείας επιστημονικής ανάπτυξης, οι οντολογίες και τα σχήματα που χρησιμοποιούνται για να μοντελοποιήσουν την επιστημονική γνώση πρέπει να αλλάζουν. Όταν οι οντολογίες εξελίσσονται, οι αλλαγές θα πρέπει με κάποιο τρόπο να ενσωματωθούν και να χρησιμοποιηθούν από τα προ-υπάρχοντα συστήματα ολοκλήρωσης πληροφοριών. Στα περισσότερα από τα συστήματα αυτά, όταν οι οντολογίες αλλάζουν, οι συσχετίσεις τους με τις πηγές των δεδομένων δημιουργούνται από το μηδέν χειρονακτικά, μια διαδικασία η οποία είναι γνωστό ότι είναι επιρρεπής σε λάθη και χρονοβόρα. Στην εργασία αυτή, προτείνουμε μια λύση που επιτρέπει την απάντηση ερωτήσεων χρησιμοποιώντας οντολογίες που εξελίσσονται χωρίς επαναπροσδιορισμό των συσχετίσεων με τις πηγές. Προκειμένου να επιτευχθεί αυτό, μοντελοποιούμε την εξέλιξη μιας οντολογίας με υψηλού επιπέδου αλλαγές και στη συνέχεια παρουσιάζουμε έναν αλγόριθμο που χρησιμοποιεί αυτές τις αλλαγές για να ξαναγράψει τα ερωτήματα μεταξύ των διαφόρων εκδόσεών της. Σε ένα τέτοιο περιβάλλον, προχωρούμε ακόμη περισσότερο στον εντοπισμό των προβλημάτων, και δείχνουμε πως είναι δυνατόν να υπολογίσουμε τα maximally contained-rewriting για τις πηγές. Αποδεικνύουμε ότι η προσέγγιση μας επιβαρύνει ελάχιστα τους παραδοσιακούς αλγορίθμους για query rewriting και μειώνει σημαντικά την ανθρώπινη προσπάθεια που δαπανάται στο συνεχή επαναπροσδιορισμό των συσχετίσεων.

PDF




Επεξηγώντας Δομημένες  Επερωτήσεις σε Φυσική Γλώσσα

Γεωργία Κούτρικα (Stanford University), Άλκης Σημιτσής (HP Labs, Palo Alto), Γιάννης Ε. Ιωαννίδης (Πανεπιστήμιο Αθηνών)

Πολλές εφαρμογές χρησιμοποιούν προγραμματιστικά περιβάλλοντα βασισμένα σε χρήση φορμών, για να απλοποιήσουν την πρόσβαση σε συστήματα διαχείρισης πληροφορίας σε χρήστες μη εξοικειωμένους με τη χρήση δομημένων γλωσσών επερωτήσεων. Οι χρήστες χρησιμοποιούν τις φόρμες για να συνθέσουν δομημένες επερωτήσεις οι οποίες στη συνέχεια εκτελούνται. Καθώς είναι πιθανόν ο χρήστης να μη γνωρίζει τη σημασιολογία που συνδέει τα γνωρίσματα των φορμών, συχνά είναι χρήσιμο να του παρέχουμε μια επεξήγηση των παραγόμενων επερωτήσεων σε φυσική γλώσσα. δηλαδή, στο πλέον φυσικό μέσο επικοινωνίας. Σε αυτό το άρθρο, ακολουθούμε μια γραφοθεωρητική προσέγγιση του προβλήματος της μετάφρασης επερωτήσεων. Αναπαριστούμε διαφορετικές μορφές δομημένων επερωτήσεων ως κατευθυνόμενους γράφους και εμπλουτίζουμε τις ακμές των γράφων με πρότυπες επισημειώσεις, χρησιμοποιώντας έναν επεκτάσιμο μηχανισμό προτύπων. Παρουσιάζουμε τεχνικές διάσχισης γράφων αποσκοπώντας στην αποδοτική εξερεύνησή τους για την περιγραφή επερωτήσεων σε φυσική γλώσσα. Τέλος, παρουσιάζουμε αναλυτικά πειραματικά αποτελέσματα που δείχνουν την αποδοτικότητα και αποτελεσματικότητα των προτεινόμενων μεθόδων.

PDF




Επιλογή Συλλογών Εγγράφων XML με Βάση τους Χαμηλότερους Κοινούς Προγόνους

Γεωργία Κολωνιάρη (Πανεπιστήμιο Ιωαννίνων), Ευαγγελία Πιτουρά (Πανεπιστήμιο Ιωαννίνων)

Σε αυτήν την εργασία, μελετάμε το πρόβλημα της επιλογής βάσεων δεδομένων για βάσεις δεδομένων που αποτελούνται από συλλογές XML εγγράφων. Συγκεκριμένα, δεδομένου ενός συνόλου από συλλογές XML εγγράφων και ενός ερωτήματος χρήστη, μελετάμε πώς να διαβαθμίσουμε τις συλλογές με βάση τη χρησιμότητα τους ως προς το ερώτημα. Η χρησιμότητα καθορίζεται από την σχετικότητα των εγγράφων της συλλογής με το ερώτημα. Θεωρούμε ερωτήματα με λέξεις-κλειδιά και για τον ορισμό των αποτελεσμάτων τους υποστηρίζουμε σημασιολογία χαμηλότερου κοινού προγόνου, όπου η σχετικότητα κάθε εγγράφου με ένα ερώτημα καθορίζεται από τις ιδιότητες του χαμηλότερου κοινού προγόνου των κόμβων του XML εγγράφου που περιέχουν τις λέξεις-κλειδιά του ερωτήματος. Για να αποφύγουμε την αποτίμηση των ερωτημάτων έναντι κάθε εγγράφου μιας συλλογής, προτείνουμε μέσω μίας φάσης προ-επεξεργασίας τη διατήρηση πληροφορίας για τους χαμηλότερους κοινούς προγόνους όλων των ζευγών λέξεων-κλειδιών που εμφανίζονται σε ένα έγγραφο. Η πληροφορία αυτή χρησιμοποιείται για την προσέγγιση των ιδιοτήτων του αποτελέσματος ενός ερωτήματος. Για την βελτίωση της απόδοσης τόσο σχετικά με την αποθήκευση όσο και με την επεξεργασία, χρησιμοποιούμε κατάλληλες περιλήψεις της πληροφορίας για τους χαμηλότερους κοινούς προγόνους βασισμένες στα φίλτρα Bloom. Εφαρμόζουμε την προσέγγιση μας για την επίλυση μίας δυαδικής και μία ζυγισμένης εκδοχής του προβλήματος. Τα πειραματικά μας αποτελέσματα δείχνουν ότι η μέθοδος μας επιφέρει χαμηλά σφάλματα στην εκτίμηση της χρησιμότητας μιας συλλογής και παρέχει διαβαθμίσεις συλλογών πολύ κοντά στις πραγματικές.

PDF




Θεσιακός Χειρισμός των Ενημερώσεων Τιμών σε Βάσεις Στηλικής Αποθήκευσης.

Sandor Heman (Vectorwise), Marcin Zukowski (Vectorwise), Niels Nes (Centrum Wiskunde & Informatica), Λευτέρης Σιδηρουργός (Centrum Wiskunde & Informatica), Peter Boncz (Centrum Wiskunde & Informatica)

Σε αυτή την εργασία εξετάζουμε τεχνικές που επιτρέπουν την γρήγορη ενημέρωση τιμών σε βάσεις στηλικής αποθήκευσης, χωρίς να επηρεάζεται αρνητικά ο χρόνος της αποτίμησης των επόμενων επερωτήσεων. Παρατηρούμε ότι είναι προτιμότερο να διατηρούμε δομές διαφορών που περιγράφουν την θέση της πλειάδας προς ενημέρωση (την θέση εισαγωγής ή διαγραφής), εν αντιθέση με την ως τώρα πρακτική της αποθήκευσης των ανανεωμένων τιμών σε ενδιάμεσες δομές. Για τον λόγο αυτόν, εισάγουμε μία νέα δομή διαφορών που ονομάζετε Θεσιακό Δέντρο Διαφορών, και περιγράφουμε αναλυτικά τους αλγόριθμους για την σύζευξη αυτών με τις στήλες δεδομένων της βάσης, την ενημέρωση τους, και την χρήση αυτών σε περιβάλλοντα διαχείρισης συναλλαγών. Τέλος, παραθέτουμε πειραματικά αποτελέσματα που αποδεικνύουν την λειτουργικότητα και την υψηλή απόδοση των Θεσιακών Δέντρων Διαφορών.

PDF




Καταλληλότητα Υλοποιημένων Όψεων για την Απάντηση Κατατακτήριων Ερωτημάτων με άνω Όριο Αποτελεσμάτων

Ευτυχία Μπαϊκούση (Πανεπιστήμιο Ιωαννίνων), Παναγιώτης Βασιλειάδης (Πανεπιστήμιο Ιωαννίνων)

Στην παρούσα εργασία, εξετάζουμε το πρόβλημα της απάντησης ερωτημάτων με άνω όριο αποτελεσμάτων κάνοντας χρήση υλοποιημένων όψεων. Παρέχουμε θεωρητικές εγγυήσεις για την επάρκεια μιας υλοποιημένης όψης για να απαντήσει ένα ερώτημα με άνω όριο αποτελεσμάτων. Επίσης, παρέχουμε αλγοριθμικές τεχνικές για να υπολογιστεί η απάντηση του ερωτήματος σε περίπτωση που η χρήση μιας υλοποιημένης όψης επαρκεί για την απάντηση του ερωτήματος. Διερευνούμε το πρόβλημα της απάντησης σε ένα ερώτημα με άνω όριο αποτελεσμάτων, κάνοντας χρήση συνδυασμού περισσοτέρων από μία όψης. Τέλος, αξιολογούμε πειραματικά την προσέγγισή μας για την αποτελεσματικότητα και την αποδοτικότητα της.

PDF




Κατανεμημένη δεικτοδότηση μεγάλου όγκου δεδομένων σε υπολογιστικά νέφη.

Ιωάννης Κωνσταντίνου (Εθνικό Μετσόβιο Πολυτεχνείο), Ευάγγελος Αγγέλου (Εθνικό Μετσόβιο Πολυτεχνείο), Δημήτριος Τσουμάκος (Πανεπιστήμιο Κύπρου), Νεκτάριος Κοζύρης (Εθνικό Μετσόβιο Πολυτεχνείο)

Σε αυτή την εργασία παρουσιάζουμε μια κατανεμημένη αρχιτεκτονική δεικτοδότησης, αποθήκευσης και επερώτησης διαφορετικών δεδομένων μεγάλου όγκου. Περιλαμβάνει και επεκτείνει την λειτουργικότητα του Hadoop, από το πλαίσιο MapReduce, και της HBase, μιας κατανεμημένης, αραιής, NoSQL βάσης δεδομένων, ώστε να δημιουργήσει ένα πλήρως παράλληλο σύστημα δεικτοδότησης. Πειράματα με δομημένα, ημι-δομημένα και αδόμητα δεδομένα διαφόρων μεγεθών επιδεικνύουν την προσαρμοστικότητα, ταχύτητα και ελαστικότητα της υλοποίησης μας και την αντιπαραβάλλουν με παρόμοια έργα. Το πρωτότυπό μας σύστημα σε 11 κόμβους δεικτοδότησε δεδομένα 150 GB σε λιγότερο από 3 ώρες, ενώ η απόκριση υπό φορτία μεγαλύτερα των 1000 ερωτήσεων ανά δευτερόλεπτο κρατήθηκε σε τάξη μεγέθους milliseconds.

PDF




Κατανεμημένη διήθηση XML δεδομένων βάσει δομής και τιμών

Ίρις Μηλιαράκη (Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών), Μανόλης Κουμπαράκης (Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών)

Τα τελευταία χρόνια έχουνε εμφανιστεί πολλά συστήματα δημοσιεύσεων/συνδρομών που προσφέρουν δημοφιλείς υπηρεσίες ειδοποίησης για ειδήσεις, ιστολόγια ή επιστημονικές δημοσιεύσεις. Καθώς το μοντέλο δεδομένων XML έχει ευρέως διαδοθεί σαν ο καθιερωμένος τρόπος ανταλλαγής δεδομένων στο διαδίκτυο, ο στόχος πολλών ερευνητικών δραστηριοτήτων είναι ο σχεδιασμός αποδοτικών και κλιμακωτών συστημάτων διήθησης XML δεδομένων πάνω από ένα σύνολο XPath/XQuery ερωτήσεων. Η πλειοψηφία αυτών των συστημάτων επικεντρώνονται στην αποδοτική εύρεση XML δεδομένων που ταιριάζουν δομικά με τις αντίστοιχες ερωτήσεις. Συχνά όμως, εκτός από το δομικό ταίριασμα, πρέπει να γίνει και ταίριασμα των τιμών που περιέχονται στα XML δεδομένα. Σε αυτό το πλαίσιο, προτείνουμε διάφορες μεθόδους για να συνδυάσουμε την αποδοτική διήθηση XML δεδομένων τόσο δομικά όσο και βάσει των τιμών που περιέχονται σε ένα κατανεμημένο περιβάλλον. Στόχος είναι η κλιμάκωση των μεθόδων μας τόσο σε σχέση με το σύνολο των συνδρομών/ερωτήσεων που έχουν υποβληθεί στο σύστημα όσο και με το σύνολο των περιορισμών των τιμών που θέτει η κάθε ερώτηση. Όλες οι μέθοδοι που περιγράφονται έχουν υλοποιηθεί σε ένα σύστημα διήθησης XML δεδομένων χρησιμοποιώντας τον κατανεμημένο πίνακα κατακερματισμού Pastry. Συγκρίνουμε τις μεθόδους και παρουσιάζουμε την πειραματική τους αξιολόγηση σε δύο περιβάλλοντα, σε ένα πραγματικό κατανεμημένο περιβάλλον που προσφέρεται από το δίκτυο PlanetLab και σε ένα ελεγχόμενο περιβάλλον ενός υπολογιστικού συστήματος πλέγματος.

PDF




Κοινωνικά-ενήμερη Δρομολόγηση Επερωτήσεων  σε Κινητά Δίκτυα

Ανδρέας Κωνσταντινίδης (Πανεπιστήμιο Κύπρου), Δημήτρης Ζεϊναλιπούρ (Πανεπιστήμιο Κύπρου) και Kun Yang (University of Essex, UK)

Τα Δένδρα Δρομολόγησης Επερωτήσεων (ΔΔΕ) αποτελούν σήμερα βασικές δομές επικοινωνίας σε διαφορετικά είδη δικτύων, όπως Δίκτυα Ομοτίμων, Ασύρματα Δίκτυα Αισθητήρων και Κινητά Δίκτυα, για διάδοση απαντήσεων ερωτημάτων σε ένα κεντρικοποιημένο επεξεργαστή. Ο επικρατέστερος μηχανισμός δημιουργίας αυτών των δομών είναι συνήθως βασισμένος σε ένα μονάχα, ή κανένα, κριτήριο βελτιστοποίησης (π.χ., συνολική ενέργεια, ύψος δένδρου, κτλ.) Σε αυτή τη δουλειά, επιχειρούμε να δημιουργήσουμε βέλτιστες δομές ΔΔΕ, οι οποίες μπορούν ταυτόχρονα να βελτιστοποιήσουν πολλαπλά κριτήρια. Το μοντέλο συστήματος αυτής της εργασίας στηρίζεται στην έννοια ενός Κινητού Δικτύου Δικτύωσης (Mobile Social Network), το οποίο είναι ένα δίκτυο όπου οι χρήστες αλληλεπιδρούν μέσω κάποιων έξυπνων συσκευών (smartphones). Στόχος μας είναι να δημιουργήσουμε ΔΔΕ τα οποία ταυτόχρονα βελτιστοποιούν πολλαπλά, συχνά αντικρουόμενα, κριτήρια. Για να λύσουμε το πρόβλημα αυτό, ορίζουμε ένα Πρόβλημα Βελτιστοποίησης Πολλαπλών Στόχων, το οποίο ταυτόχρονα παρουσιάζει το ελάχιστο κόστος δρομολόγησης, τα μέγιστα επίπεδα ποιότητας απαντήσεων και τα μέγιστα επίπεδα κοινωνικών αλληλεπιδράσεων μεταξύ των χρηστών που συμμετέχουν. Στη συνέχεια λύνουμε το ορισμένο πρόβλημα με γενετικούς αλγορίθμους βελτιστοποίησης πολλαπλών στόχων, συγκεκριμένα τον MOEA/D και τον NSGA-II. Τα αποτελέσματα μας πάνω από προσομοιωμένα δίκτυα WIFI, δείχνουν ότι ο MOEA/D είναι ένας αποδοτικός αλγόριθμος για παροχή βέλτιστων ΔΔΕ σε Κινητά Δίκτυα Δικτύωσης.

PDF




Πολυδιάστατη Δεικτοδότηση σε Δίκτυα Ομοτίμων

Γιώργος Τσατσανίφος (Εθνικό Μετσόβιο Πολυτεχνείο), Τίμος Σελλής (Εθνικό Μετσόβιο Πολυτεχνείο)

Η εργασία αυτή παρουσιάζει ένα πρωτότυπο πολυδιάστατο ευρετήριο για μεγάλης κλίμακας αποκεντρωμένα δίκτυα και δυναμικά περιβάλλοντα όπου κόμβοι εισέρχονται, εξέρχονται κι αποτυγχάνουν αυθαίρετα. Παρουσιάζουμε μια νέα peer-to-peer εφαρμογή κατ' εικόναν του προσαρμοστικού kd δέντρου, καθώς κι αλγόριθμους για πολυδιάστατη αναζήτηση, αναζήτηση εύρους, και K πλησιέστερων γειτόνων. Χαρακτηριστικά της μεθόδου μας, είναι ότι κάθε peer διατηρεί O (logn) πληροφορία για το υπόλοιπο δίκτυο και τα αιτήματα ικανοποιούνται σε O(logn) βήματα, σε σχέση με το μέγεθος n του δικτύου. Στο πειραματικό μέρος της δουλειάς μας συγκρίνουμε το MIDAS με άλλες γνωστές μεθόδους.

PDF




Προσεγγιστικός Υπολογισμός Ακραίων Τιμών σε Περιβάλλοντα Ασύρματων Δικτύων Αισθητήρων

Νίκος Γιατράκος (Πανεπιστήμιο Πειραιά), Γιάννης Κωτίδης (Οικονομικό Πανεπιστήμιο Αθηνών), Αντώνιος Δεληγιαννάκης (Πολυτεχνείο Κρήτης), Βασίλης Βασσάλος (Οικονομικό Πανεπιστήμιο Αθηνών), Γιάννης Θεοδωρίδης (Πανεπιστήμιο Πειραιά)

Τα ασύρματα δίκτυα αισθητήρων γίνονται όλο και περισσότερο δημοφιλή σε πληθώρα εφαρμογών. Ωστόσο, οι χρήστες τους έρχονται αντιμέτωποι με το γεγονός ότι οι μετρήσεις των αισθητηρίων οργάνων των αισθητήρων συχνά περιλαμβάνουν μεγάλο αριθμό ακραίων τιμών. Οι ακραίες τιμές μπορεί να επηρεάσουν σημαντικά εφαρμογές που απαιτούν την έγκαιρη λήψη αξιόπιστων δεδομένων προκειμένου να παρέχουν τις επιθυμητές λειτουργίες. Κατά συνέπεια, πρόσφατα έχει αναπτυχθεί η τάση διερεύνησης του τρόπου με τον οποίο τεχνικές που προσδιορίζουν ακραίες τιμές μπορούν να εφαρμοστούν στον καθαρισμό δεδομένων αισθητήρων. Δυστυχώς, οι περισσότερες από τις υπάρχουσες τέτοιες προσεγγίσεις απαιτούν υπερβολικά μεγάλα κόστη επικοινωνίας, κάτι που περιορίζει την εφαρμοσιμότητά τους. Στην παρούσα εργασία εισάγουμε ένα πλαίσιο προσδιορισμού ακραίων τιμών εντός του δικτύου, βασισμένο στον κατακερματισμό με ευαισθησία στην ομοιότητα, επεκταμένο με μια καινοτόμα διαδικασία ποσοτικής αύξησης της ακρίβειας (boosting) καθώς και απoδοτικές τεχνικές ισοκατανομής φόρτου και περικοπής συγκρίσεων. Οι μέθοδοί μας επιτηδεύουν ευθέως την κατανάλωση εύρους ζώνης σε σχέση με την ακρίβεια και υποστηρίζουν πληθώρα μέτρων ομοιότητας.

PDF




Συνεργατική εκπαίδευση συναρτήσεων ταξινόμησης για εξατομίκευση αναζήτησης.

Γιώργος Γιαννόπουλος (ΙΠΣΥΠ, Ε.Κ. "Αθηνά" -- Ε.Μ.Π.), Θοδωρής Δαλαμάγκας (ΙΠΣΥΠ, Ε.Κ. "Αθηνά"), Τίμος Σελλής (ΙΠΣΥΠ, Ε.Κ. "Αθηνά" -- Ε.Μ.Π.)

Σε αυτή τη δημοσίευση παρουσιάζουμε ένα πλαίσιο για τη βελτίωση της διαδικασίας εκπαίδευσης συναρτήσεων ταξινόμησης και της διαδικασίας αναταξινόμησης αποτελεσμάτων για την εξατομίκευση αναζήτησης. Η μέθοδος μας βασίζεται στην εκμετάλλευση μεταδεδομένων αναζήτησης από διάφορους χρήστες με σκοπό τη δημιουργία πολλαπλών συναρτήσεων ταξινόμησης που αντιστοιχούν σε διαφορετικές θεματικές περιοχές. Αυτές οι συναρτήσεις συνδυάζονται κάθε φορά που ο χρήστης θέτει ένα νέο ερώτημα, έτσι ώστε να παράγουν μία νέα ταξινομημένη λίστα αποτελεσμάτων, υπολογίζοντας την ομοιότητα του ερωτήματος με κάθε μία από τις παραπάνω θεματικές περιοχές. Συγκρίνουμε τη μέθοδό μας με με τις κλασσικές προσσεγίσεις εκπαίδευσης μίας συνάρτησης ανά χρήστη ή εκπαίδευσης μίας κοινής συνάρτησης για ομάδα χρηστών και δείχνουμε αρχικά πειραματικά αποτελέσματα.

PDF




Συσταδοποίηση τροχιών κινούμενων αντικειμένων σε ένα αβέβαιο περιβάλλον

Νίκος Πελέκης (Πανεπιστήμιο Πειραιώς), Ιωάννης Κοπανάκης (Τεχνολογικό Ίδρυμα Κρήτης), Ευάγγελος Ε. Κοτσιφάκος (Πανεπιστήμιο Πειραιώς), Ηλίας Φρέντζος (Πανεπιστήμιο Πειραιώς), Γιάννης Θεοδωρίδης (Πανεπιστήμιο Πειραιώς)

Η εξόρυξη γνώσης σε βάσεις τροχιών κινούμενων αντικειμένων (Trajectory Databases - TD) έχει κινήσει πρόσφατα μεγάλο ενδιαφέρον λόγω της ευρείας διάδοσης των συσκευών πλοήγησης. Η έμφυτη όμως αβεβαιότητα που υπάρχει στα δεδομένα μιας TD (πχ. λόγω σφαλμάτων του GPS) δε λαμβάνεται υπόψη στη διαδικασία της εξόρυξης. Στην παρούσα εργασία, μελετάμε την επίδραση της αβεβαιότητας στη συσταδοποίηση τροχιών και παρουσιάζουμε μία διαδικασία τριών βημάτων για την αντιμετώπισή της. Καταρχάς προτείνουμε μία διαισθητική διανυσματική αναπαράσταση των τροχιών που περιέχει την αβεβαιότητα και εισάγουμε μία αποτελεσματική μετρική απόστασης που τη λαμβάνει υπόψη. Δεύτερον, παρουσιάζουμε τον CenTra, έναν καινοτόμο αλγόριθμο για το πρόβλημα της ανακάλυψης της κεντρικής τροχιάς (centroid) σε ένα σύνολο τροχιών. Τρίτον, προτείνουμε μία παραλλαγή του αλγορίθμου ασαφούς συσταδοποίησης Fuzzy C-Means (FCM) που ενσωματώνει τον CenTra στη διαδικασία ενημέρωσης των κέντρων των συστάδων. Η πειραματική αξιολόγηση σε πραγματικά δεδομένα τροχιών δείχνει την αποτελεσματικότητα και αποδοτικότητα της προτεινόμενης προσέγγισης.

PDF




Σχετικά με την Προέλευση σε Επερωτήσεις πάνω σε Διασυνδεδεμένα Δεδομένα του Παγκόσμιου Ιστού

Γιάννης Θεοχάρης (ΙΤΕ-ΙΠ και Πανεπιστήμιο Κρήτης), Ειρήνη Φουντουλάκη (ΙΤΕ-ΙΠ), Γρηγόρης Καρβουναράκης (LogicBlox και ΙΤΕ-ΙΠ), Βασίλης Χριστοφίδης (ΙΤΕ-ΙΠ και Πανεπιστήμιο Κρήτης).

Η αποτίμηση της ποιότητας της πληροφορίας που βρίσκεται δημοσιευμένη στον παγκόσμιο ιστό ακολουθώντας το παράδειγμα των Διασυνδεδεμένων Δεδομένων (ΔΔ) αναδύεται σαν μια κρίσιμη ανάγκη πολλών εφαρμογών. Η σύλληψη της αξιοπιστίας και της φήμης των ΔΔ που μεταχειρίζονται μέσω της SPARQL, απαιτεί την αναπαράσταση ικανής πληροφορίας προέλευσης για τη σύλληψη της σχέσης ανάμεσα στα αποτέλεσμα των επερωτήσεων και τα δεδομένα εισόδου. Αυτή η σχέση μπορεί είτε να υλοποιηθεί μαζί με τα αποτελέσματα ή να χαθεί μετά την αποτίμηση των επερωτήσεων. Στην πρώτη περίπτωση, η πληροφορία προέλευσης των αποτελεσμάτων αποτελείται από αφαιρετικές εκφράσεις πάνω σε σύμβολα προέλευσης που ταυτοποιούν τα δεδομένα εισόδου, ενώ στη δεύτερη, αποτελείται από επισημειώσεις που υπολογίζονται βασιζόμενες στις επισημειώσεις των δεδομένων εισόδου μαζί με την αποτίμηση της επερώτησης. Επιχειρηματολογούμε πάνω στα οφέλη της πρώτης προσέγγισης, για περιβάλλοντα στα οποία τα αποτελέσματα των επερωτήσεων υλοποιούνται σε διαφορετικές αποθήκες δεδομένων και αναλύονται από πολλαπλούς χρήστες. Διερευνούμε το βαθμό στον οποίο σχεσιακά μοντέλα προέλευσης μπορούν να εφαρμοστούν για SPARQL επερωτήσεις και εξακριβώνουμε τα όρια των δυνατοτήτων τους. Τελικά, υποστηρίζουμε την ανάγκη για νέα μοντέλα προέλευσης ικανά να συλλάβουν ολόκληρη την εκφραστική δύναμη της SPARQL.

PDF



Επιδείξεις Λογισμικού


madIS: Ταχεία Προτυποποίηση Ροών Εργασίας στην SQL, με Συναρτήσεις Ορισμένες από τον Χρήστη (UDF)

Λευτέρης Σταματογιαννάκης (Πανεπιστήμιο Αθηνών), Μέι Λι Τριανταφυλλιδη (Πανεπιστήμιο Αθηνών), Μαριαλένα Κυριακίδη (Πανεπιστήμιο Αθηνών), Μαρία Βαγιανού (Πανεπιστήμιο Αθηνών), Γιάννης Ιωαννίδης (Πανεπιστήμιο Αθηνών)

Στην επίδειξη αυτήν, θα παρουσιάσουμε το madIS, ένα σύστημα ανοικτού κώδικα για το μετασχηματισμό και την ανάλυση δεδομένων, το οποίο βασίζεται στην SQLite. Το σύστημα φιλοδοξεί να αποτελέσει ένα επεκτάσιμο πλαίσιο στο οποίο προσαρμοσμένες και εξειδικευμένες εργασίες επεξεργασίας δεδομένων, μπορούν να υλοποιηθούν εύκολα και γρήγορα. Το σύστημα υποστηρίζει ερωτήματα εκφρασμένα στην madSQL, η οποία είναι μία δηλωτική γλώσσα, βασισμένη στην SQL. Η madSQL ενσωματώνει με φυσικό τρόπο συναρτήσεις ορισμένες από τον χρήστη με στόχο τη δημιουργία σύνθετων ροών δεδομένων.

PDF




YMAL: Ένα Σύστημα Συστάσεων Σχεσιακών Βάσεων Δεδομένων

Ευτυχία Κωλέτσου (Πανεπιστήμιο Ιωαννίνων), Κώστας Στεφανίδης (Πανεπιστήμιο Ιωαννίνων), Μαρίνα Δρόσου (Πανεπιστήμιο Ιωαννίνων), Ευαγγελία Πιτουρά (Πανεπιστήμιο Ιωαννίνων)

Σε αυτήν την επίδειξη λογισμικού παρουσιάζουμε τις YMAL συστάσεις, ένα πλαίσιο εργασίας που επεκτείνει τα σχεσιακά συστήματα βάσεων δεδομένων με λειτουργικότητα συστάσεων. Συγκεκριμένα, προτείνουμε, μαζί με τα αποτελέσματα μίας ερώτησης, να συστήνουμε στο χρήστη επιπλέον αποτελέσματα που ονομάζουμε “You May Also Like” ή YMAL αποτελέσματα. Για να υπολογίσουμε τα YMAL αποτελέσματα για μία συγκεκριμένη ερώτηση, χρησιμοποιούμε είτε μόνο το περιεχόμενο του αποτελέσματος της ερώτησης (τοπική προσέγγιση) είτε και το περιεχόμενο της βάσης δεδομένων (καθολική προσέγγιση).

PDF




Ένα Κατανεμημένο Πλαίσιο Αναζήτησης Χώρο-Χρονικών Δεδομένων για Δίκτυα Έξυπνων Συσκευών

Κωνσταντίνος Κώστα (Πανεπιστήμιο Κύπρου), Κωνσταντίνος Χριστοφόρου (Πανεπιστήμιο Κύπρου), Γιώργος Νικολαΐδης (Πανεπιστήμιο Κύπρου), Διομήδης Παπαδιομήδους (Πανεπιστήμιο Κύπρου), Χρίστος Λαουδιάς (Πανεπιστήμιο Κύπρου), Δημήτρης Ζεϊναλιπούρ (Πανεπιστήμιο Κύπρου)

Σε αυτή την δουλειά, θα παρουσιάσουμε ένα καινοτόμο πλαίσιο αναζήτησης ομοιότητας σε χώρο-χρονικά δεδομένα, το οποίο ονομάζεται HUB-K. Το πλαίσιο μας μπορεί να αξιοποιηθεί για να απαντήσει κανείς άμεσα επερωτήσεις της μορφής: ""Βρες τα αντικείμενα τα οποία ακολουθούν μια κίνηση όμοια με ένα αντικείμενο Q, όπου Q είναι κάποια τροχιά εισόδου."" Ο αλγόριθμος HUB-K, στηρίζεται σε ένα επί-τοπου μοντέλο αποθήκευσης, όπου τα χώρο-χρονικά δεδομένα παραμένουν τοπικά στην έξυπνη συσκευή και ανακτώνται μόνο επιλεκτικά κατά την εκτέλεση μιας επερώτησης. Ο HUB-K στηρίζεται επίσης σε κατανεμημένους αλγόριθμους σύγκρισης τροχιών έτσι ώστε να βρίσκει τις αιτούμενες απαντήσεις γρήγορα και αποδοτικά. Η παρουσίαση μας επιδεικνύει πως το αλγοριθμικό υπόβαθρο του HUB-K, μπορεί να υλοποιηθεί εύκολα πάνω σε έξυπνες κινητές συσκευές τύπου Android με θεαματικά αποτελέσματα χρόνου απόκρισης.

Για να παρουσιάσουμε τις ικανότητες του HUB-K κατά τη διάρκεια του συμποσίου, θα επιτρέψουμε στους παρευρισκόμενους να εκτελέσουν επερωτήσεις σε δίκτυα έξυπνων κινητών συσκευών με τους ακόλουθους δυο τρόπους: i) Διαδραστικά, όπου κάποιες συσκευές θα δοθούν στους παρευρισκόμενους; και ii) Μέσω Κατάστιχου, όπου ένα μεγαλύτερο στιγμιότυπο από πραγματικές και εξομοιωμένες συσκευές θα εκτελεστεί, έτσι ώστε να δείξουμε πως ανταποκρίνεται το πλαίσιο μας σε μεγαλύτερου μεγέθους εκτελέσεις.

PDF


Ένα Πρωτότυπο Σύστημα Εξατομίκευσης για τη Δικτυακή Πύλη της Ευρωπαϊκής Βιβλιοθήκης

Μαριαλένα Κυριακίδη (Πανεπιστήμιο Αθηνών), Λευτέρης Σταματογιαννάκης (Πανεπιστήμιο Αθηνών), Μέι Λι Τριανταφυλλιδη (Πανεπιστήμιο Αθηνών), Μαρία Βαγιανού (Πανεπιστήμιο Αθηνών), Γιάννης Ιωαννίδης (Πανεπιστήμιο Αθηνών)

Στην επίδειξη αυτή παρουσιάζουμε ένα ευέλικτο σύστημα για την παροχή εξατομικευμένων λειτουργιών σε συστήματα ψηφιακών βιβλιοθηκών. Το σύστημα έχει αναπτυχθεί με βάση τις ανάγκες της δικτυακής πύλης της «Ευρωπαϊκής Βιβλιοθήκης» και θα παρουσιαστεί κάτω από το συγκεκριμένο πλαίσιο, αλλά μπορεί να βρει ευρύτερη εφαρμογή. Υλοποιεί ένα μεγάλο σύνολο επεξεργασίας, ανάλυσης κι εξόρυξης δεδομένων στα ημερολόγια της δικτυακής πύλης, χρησιμοποιώντας το περιβάλλον madIS. Επιτρέπει την εξατομικευμένη προσαρμογή των αποτελεσμάτων σε πραγματικό χρόνο μέσω της ανάπτυξης REST υπηρεσιών ιστού, που είναι υπεύθυνες για την ανάκτηση και τον κατάλληλο συνδυασμό της εξαχθείσας πληροφορίας. Η επίδειξη περιέχει επίσης ένα διαδικτυακό εργαλείο οπτικοποίησης για την παρουσίαση των αποτελεσμάτων που προέκυψαν από την ανάλυση των ημερολογίων.

PDF




Σύστημα Ενοποίησης Δεδομένων με Βάση τα Αντικείμενα

Αικατερίνη Ιωάννου (L3S Research Center, Γερμανία), Claudia Niederée (L3S Research Center, Γερμανία), Γιάννης Βελεγράκης (University of Trento, Ιταλία)

Η πρωτοβουλία διασυνδεδεμένων δεδομένων (Linked Data initiative), έχει σαν στόχο την δημιουργία και εκμετάλευση συνδέσμων απο ταυτίσεις μεταξύ πληροφοριών. Το σύστημά μας έχει ως βάση αυτή την πρωτοβουλία, αλλά την επεκτείνει έτσι ώστε οι ταυτίσεις να συμπεριλαμβάνουν τα αντικείμενα τα οποία περιγράφονται από τα δεδομένα, λ.χ., σύνδεση των δεδομένων που περιγράφουν το ίδιο άτομο, ή την ίδια τοποθεσία. Στο εν λόγω άρθρο περιγράφουμε την θεωρία, την λειτουργία και τα αποτελέσματα της αξιολόγησης ενός τέτοιου συστήματος.

PDF




Χρηστο-κεντρικά Υπερμεσικά Περιβάλλοντα Εξατομίκευσης – Το Σύστημα AdaptiveWeb

Παναγιώτης Γερμανάκος (Πανεπιστήμιο Κύπρου και Πανεπιστήμιο Λευκωσίας), Μάριο Μπελκ (Πανεπιστήμιο Κύπρου), Νίκος Τσιάνος (Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών), Ζαχαρίας Λέκκας (Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών), Κωνσταντίνος Μουρλάς (Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών), Γιώργος Σαμάρας (Πανεπιστήμιο Κύπρου)

Βασικός στόχος της εργασίας αυτής είναι η ανάπτυξη ενός «ανοικτού» συστήματος εξατομίκευσης και προσαρμογής διαδικτυακών περιβαλλόντων, AdaptiveWeb, το οποίο στηρίζεται σε μια καινοτόμο έρευνα που συνδυάζει βασικές θεωρίες μαθησιακών στυλ και οπτικών, γνωστικών, και συναισθηματικών διεργασιών των χρηστών καθώς και σε τεχνολογίες σημασιολογίας και μεταδεδομένων περιεχομένου. Ο πυρήνας του συστήματος αποτελείται από έναν αριθμό συστατικών που συμβάλλουν στην μοντελοποίηση των χρηστών βάσει των παραπάνω μοναδικών αντιληπτικών τους προτιμήσεων και την αναδόμηση και προσαρμογή του υπερμεσικού περιεχομένου με την χρήση συγκεκριμένων μεθοδολογιών και τεχνικών σημασιολογίας. Για το σκοπό αυτό έχει σχεδιαστεί ένα RDFa σχήμα το οποίο επιτρέπει την ενσωμάτωση των εννοιών της έρευνας σε οποιαδήποτε XHTML σελίδα, που συνεπώς καταστεί τη δομημένη πληροφορία έτοιμη για προσαρμογή (adaptation), αλλά και οποιαδήποτε εξωτερική υπηρεσία επιθυμεί να υποστηρίξει το ίδιο πρότυπο. Η αξιολόγηση του συστήματος με περίπου 500 χρήστες, τόσο σε ένα μαθησιακό (eLearning) όσο και σε ένα γενικού περιεχομένου περιβάλλοντος αλληλεπίδρασης (eCommerce), κατέδειξε ότι η ενσωμάτωση γνωστικών και συναισθηματικών παραμέτρων στην εξατομίκευση ηλεκτρονικού περιεχομένου, αυξάνει την απόδοση και ικανοποίηση των χρηστών και βελτιώνει την μαθησιακή τους ικανότητα καθώς πλοηγούνται σε ένα διαδικτυακό περιβάλλον διάδρασης.

PDF



Αναρτημένες Ανακοινώσεις


Εξαγωγή Θεμάτων Συζήτησης μεταξύ Χρηστών Διαδικτυακών Χώρων Συζήτησης

Θοδωρής Γεωργίου (Πανεπιστήμιο Αθηνών)

Το αντικείμενο της παρούσας εργασίας αφορά την εξαγωγή των θεμάτων συζήτησης μεταξύ των χρηστών ενός διαδικτυακού τόπου συζητήσεων (web discussion board ή web forum). Για την επίτευξη του στόχου αυτού έχει γίνει χρήση συγκεκριμένων δομικών στοιχείων που προσφέρουν τα web forum. Τα στοιχεία αυτά είναι τα εξής: Η γνώση του «ποιος» και «πότε» δημοσίευσε μια ανάρτηση (post) σε μια συζήτηση (thread), ο μηχανισμός παράθεσης μιας άλλης ανάρτησης (quote), καθώς και η θέση της ανάρτησης μέσα στην συζήτηση.

Η χρήση των στοιχείων αυτών, με τον τρόπο που θα εξηγηθεί παρακάτω, είναι ιδιαίτερα σημαντική καθώς ο αλγόριθμος αγνοεί πλήρως τις λεκτικές ιδιομορφίες των αναρτήσεων. Κάτι αρκετά χρήσιμο δεδομένου ότι σε ένα forum μπορεί οι χρήστες να γράφουν σε μια ή παραπάνω άγνωστες γλώσσες (π.χ. κορεάτικα) ή οι αναρτήσεις να μην έχουν επαρκές περιεχόμενο για την εξαγωγή του θέματος. Ειδικά το τελευταίο είναι πολύ συχνό καθώς οι αναρτήσεις περιέχουν σχετικά μικρό αριθμό προτάσεων και συνήθως όχι σωστά δομημένες (και από γραμματική και από συντακτική άποψη).


Πειραματική Αποτίμηση του Αλγορίθμου ΜΙΝΤ στο TinyOS

Παναγιώτα Γιαννή (Πανεπιστήμιο Κύπρου)

Η αναρτημένη ανακοίνωση έχει ως σκοπό την παρουσίαση των αποτελεσμάτων της διπλωματικής μου εργασίας, που έχει ως θέμα την πειραματική αξιολόγηση του αλγόριθμου MINT(Materialized In-Network Top-k Views) στα ασύρματα δίκτυα αισθητήρων. Ο αλγόριθμος που μελετάμε ασχολείται με τη βελτιστοποίηση της εκτέλεσης ερωτημάτων συνεχούς παρακολούθησης σε δίκτυα αισθητήρων και αποσκοπεί στην μείωση της επικοινωνίας μέσα στο δίκτυο. Συγκεκριμένα, επικεντρώνεται στην αποτελεσματική ανάκτηση των k υψηλότερων σε κατάταξη (ή Top-k) απαντήσεων. Η γενική φιλοσοφία στην οποία βασίζεται ο MINT είναι η επεξεργασία των αποτελεσμάτων μέσα στο δίκτυο, πριν την προώθησή τους προς το υπόλοιπο δίκτυο. Ο απώτερος σκοπός αυτής της ενδοδίκτυας επεξεργασίας που υλοποιεί ο αλγόριθμος, είναι η ελαχιστοποίηση του κόστους της αξιολόγησης του ερωτήματος στο δίκτυο, με αποτέλεσμα τη μείωση της καταναλισκόμενης ενέργειας και κατά συνέπεια τη μεγιστοποίηση του χρόνου ζωής του δικτύου.

Για την αξιολόγηση του αλγόριθμου MINT, πραγματοποιήθηκαν πολλαπλές προσομοιώσεις με τη χρήση διαφόρων εργαλείων του λειτουργικού TinyOS, όπως το TinyDB, ο προσομοιωτής Tossim, το TinyViz και τo PowerTossim.


Αλγόριθμοι Κοινωνοικής Δικτύωσης

Χαρίτων Ευσταθιάδης (Πανεπιστήμιο Κύπρου)

Στόχος αυτής της εργασίας ήταν να αναπτυχθεί μία εφαρμογή κοινωνικής δικτύωσης η οποία συλλέγει πληροφορίες σχετικά με τη θέση των μελών της κοινότητας στην οποία ανήκουν. Κάθε χρήστης γνωρίζει πού βρίσκονται τα μέλη της κοινότητάς του, με την ακρίβεια που του προσφέρει το σύστημα GPS. Με αυτό τον τρόπο μπορεί να επικοινωνεί μαζί τους και να μαθαίνει πληροφορίες για το συγκεκριμένο σημείο. Τα δεδομένα αποθηκεύονται και διαχειρίζονται από έναν κεντρικό εξυπηρετητή. Στο πλαίσιο αυτό, έχουν αναπτυχθεί αλγόριθμοι για τη δημιουργία κοινότητας χρηστών, για την ανάκτηση και την αποστολή της θέσης του χρήστη, για την απεικόνιση της θέσης του χρήστη καθώς και της τροχιάς του σε ένα χάρτη.


Aνίχνευση Σχέσεων Συμφωνίας/Διαφωνίας μεταξύ Χρηστών Διαδικτυακών Χώρων Συζήτησης

Μάνος Καρβούνης (Πανεπιστήμιο Αθηνών)

Η παρούσα εργασία ασχολείται με την ανίχνευση των σχέσεων συμφωνίας/διαφωνίας μεταξύ χρηστών διαδικτυακών χώρων συζήτησης (web forums). Η προτεινόμενη μέθοδος αξιοποιεί το σύστημα παράθεσης (quoting) αυτών των χώρων, ώστε να δημιουργήσει έναν γράφο αντιπροσωπευτικό της συζήτησης. Με τον χρωματισμό του δημιουργούμενου γράφου οι συμμετέχοντες χρήστες χωρίζονται σε δύο σύνολα, ανάλογα με την ομοιογένεια των απόψεών τους. Η μέθοδος αυτή επιτυγχάνει ιδιαίτερα υψηλή ακρίβεια, μπορεί να εφαρμοστεί σε οποιαδήποτε συζήτηση χωρίς την ανάγκη για εκπαίδευση, και δεν απαιτεί τεχνικές επεξεργασίας φυσικής γλώσσας. Επίσης, δημιουργήθηκε ένας επιπλέον αλγόριθμος, ο οποίος αξιοποιεί τον προαναφερθέντα διαχωρισμό των χρηστών σε σύνολα, καθώς και έναν αλγόριθμο που εξάγει τα θέματα συζήτησης, για να ανιχνεύσει συγκεκριμένες σχέσεις συμφωνίας/διαφωνίας μεταξύ ζευγών χρηστών.


Εξωτερική Ταξινόμηση σε Μνήμες Flash

Παύλος Τούλουπος (Πανεπιστήμιο Κύπρου)

Στόχος αυτής της αναρτημένης ανακοίνωσης, είναι η παρουσίαση των αποτελεσμάτων της διπλωματικής μου εργασίας. Το θέμα της εν λόγω εργασίας αφορά την μελέτη και αξιολόγηση αλγόριθμων εξωτερικής ταξινόμησης σε μνήμες flash και τη πρόταση ενός νέου αποδοτικότερου αλγόριθμου που θα λαμβάνει υπόψη του την αρχιτεκτονική και τις ιδιαιτερότητες που παρουσιάζει η μνήμη αυτή ως αποθηκευτικό μέσο. Γενικά το πρόβλημα της εξωτερικής ταξινόμησης (external sorting) αναφέρεται σε περιπτώσεις όπου τα προς ταξινόμηση δεδομένα δεν χωρούν όλα μαζί στην εσωτερική μνήμη και θα πρέπει να γίνει χρήση και της εξωτερικής μνήμης για να είναι εφικτή η ταξινόμηση όλων των δεδομένων. Το πρόβλημα αυτό συναντάται με μεγάλη συχνότητα σε συστήματα βάσεων δεδομένων όπου υπάρχει διαχείριση μεγάλου όγκου δεδομένων και η ταξινόμηση αποτελεί μια από τις βασικές πράξεις του συστήματος. Στην συγκεκριμένη εργασία η εξωτερική μνήμη αποθήκευσης είναι η μνήμη flash. Η απουσία κινητών μερών και η ασυμμετρία στις διαδικασίες ανάγνωσης και εγγραφής δεδομένων που παρατηρείται στις μνήμες flash διαφοροποιούν τον τρόπο υπολογισμού του κόστους των αλγορίθμων σε σχέση με τον παραδοσιακό μαγνητικό δίσκο.

Ο προτεινόμενος αλγόριθμος επιλύει το πρόβλημα της ταξινόμησης εκτελώντας σταθερό αριθμό χρονοβόρων εγγραφών στην μνήμη flash που επιτυγχάνεται με την αύξηση των λιγότερο χρονοβόρων αναγνώσεων της μνήμης και συμπεριλαμβάνει τη χρήση ιστογραμμάτων και μιας τεχνικής που χωρίζει το προς ταξινόμηση αρχείο σε ενεργά και νεκρά σημεία. Συνολικά αξιολογήθηκαν τρεις υφιστάμενοι αλγόριθμοι εξωτερικής ταξινόμησης και δύο εκδόσεις του προτεινόμενου αλγόριθμου τον οποίο ονομάσαμε X-SORT. Η αξιολόγηση έγινε στη βάση του συνολικού χρόνου εκτέλεσης του κάθε αλγόριθμου πάνω σε τρεις διαφορετικής συσκευές (ενός SSD, μιας κινητή συσκευή HTC Hero που κάνει χρήση μιας SDcard για αποθήκευση των δεδομένων και ενός USB key). Η γλώσσα υλοποίησης όλων των αλγόριθμων ήταν η C. Το θεωρητικό υπόβαθρο καλύφθηκε μέσα από μελέτη επιστημονικών άρθρων και βιβλίων που έγινε στα πλαίσια του θεωρητικού μέρους της εργασίας αυτής και με την καθοδήγηση του ακαδημαϊκού μου συμβούλου κ. Δημήτρη Ζεϊναλιπούρ. Σύμφωνα με τα πειράματα που έγιναν οι δύο XSORT αλγόριθμοι εμφανίζονται να έχουν καλύτερη απόδοση από όλους τους υφιστάμενους αλγόριθμους από 30-50%.


Συμμετοχή στο ACM SIGMOD Programming Contest 2010

Φώτος Φραγκούδης, Παύλος Τούλουπος, Ανδριανή Στυλιανού, Ονησιφόρος Ονισηφόρου, Θεόδωρος Ιωάννου, Σάββας Ζαννέτος (Πανεπιστήμιο Κύπρου)

Για την λύση μας δημιουργήθηκαν δυο διαφορετικές εκδόσεις κώδικα, μια για κάθε ομάδα, οι οποίες είχαν τα ακόλουθα κοινά συστατικά: Για την ανάλυση των επερωτήματα δημιουργήσαμε μία δομή με στατιστικά σχετικά με τα μεγέθη των πινάκων, ευρετηρίων και άλλες πληροφορίες. Στη συνέχεια υλοποιήσαμε ένα query planner-optimizer, ο οποίος εύρισκε ένα αποδοτικό πλάνο βάσει αυτών των πληροφοριών. Για την εκτέλεση των κεντρικοποιημένων συζεύξεων μεταξύ πινάκων χρησιμοποιήσαμε αριστεροβαθή δένδρα, όπου τα ενδιάμεσα αποτελέσματα προωθούνταν προς τα πάνω (pipelined). Για την υλοποίηση του κατανεμημένου μέρους θέταμε ένα κόμβο ως master που έστελνε επερωτήματα στους κόμβους-slaves χρησιμοποιώντας το πλάνο που αποφασίστηκε από τον query planner. Η γλώσσα υλοποίησης ήταν C++ ενώ χρησιμοποιήθηκαν και οι ακόλουθες τεχνολογίες: STL, PThreads, Unix Sockets και Processes, Low-level I/O in C++. Η πειραματική υποδομή ήταν 64-bit μηχανές στο Amazon Elastic Computing Cloud Το θεωρητικό υπόβαθρο καλύφθηκε στα πλαίσια του μαθήματος προχωρημένων βάσεων δεδομένων του μαθήματος, το οποίο παρακολουθήσαμε παράλληλα με τον διαγωνισμό.

Για την αξιολόγηση, το πρόγραμμα περνούσε αυτόματα από 8 δοκιμασίες επιδόσεων (benchmarks). Οι δοκιμασίες αυτές ήταν χωρισμένες σε δυο ενότητες: Ενότητα Α: Benchmarks 1-5 και Ενότητα Β: Benchmarks 6-8. Η κατάταξη μιας ομάδας γινόταν συνάρτηση του συνολικού χρόνου εκτέλεσης των δοκιμασιών. Οι ομάδες μας κατάφεραν να περάσουν με μόνο τα 4 από τα 5 πρώτα benchmarks της ενότητας Α, και συνεπώς δεν προκρίθηκαν στη δεύτερη φάση όπου θα γινόταν η αξιολόγηση της ενότητας Β. Για την μεγαλύτερη διάρκεια του διαγωνισμού, οι ομάδες μας ήταν στη 3η και 5η θέση του leaderboard.

Σημαντικές Ημερομηνίες

Προθεσμία υποβολής άρθρων και προτάσεων:

15 Απριλίου 2010

Γνωστοποίηση αποδοχής:

20 Μαϊου 2010

Προθεσμία υποβολής Ανακοινώσεων:

2 Ιουνίου 2010

Προθεσμία υποβολής τελικής έκδοσης:

3 Ιουνίου 2010

Διεξαγωγή σuμπόσιου:
30 Ιουνίου -  3 Ιουλίου 2010

Τάφοι των Βασιλέων - Πάφος