Ερωτήματα συνένωσης και βαθμολογημένης συνένωσης σε κατανεμημένα συστήματα
| dc.contributor.advisor | Τριανταφύλλου, Παναγιώτης | |
| dc.contributor.author | Πατλάκας, Ιωάννης | |
| dc.contributor.committee | Τριανταφύλλου, Παναγιώτης | |
| dc.contributor.committee | Βαρβαρίγος, Εμμανουήλ | |
| dc.contributor.committee | Γαροφαλάκης, Ιωάννης | |
| dc.contributor.other | Patlakas, Ioannis | |
| dc.date.accessioned | 2013-02-28T16:04:33Z | |
| dc.date.available | 2013-02-28T16:04:33Z | |
| dc.date.copyright | 2012-01-31 | |
| dc.date.issued | 2013-02-28 | |
| dc.degree | Μεταπτυχιακή Εργασία | el |
| dc.description.abstract | Η ανάπτυξη των peer-to-peer βάσεων δεδομένων και η δυναμική εισαγωγή των συστημάτων αποθήκευσης σε νέφη υπολογιστών (cloudstores) ως τα κυρίαρχα μεγάλης κλίμακας συστήματα διαχείρισης δεδομένων, έχουν οδηγήσει τους ερευνητές να εξετάσουν το πρόβλημα της υποστήριξης πολύπλοκων ερωτημάτων με ένα πλήρως αποκεντρωμένο τρόπο. Περίπλοκα ερωτήματα επιλογής (select), συνένωσης join, καθώς και βαθμολογημένα ερωτήματα έχουν κεντρίσει το ενδιαφέρον της κοινότητας διαχείρισης δεδομένων. Ανάμεσα στις τάξεις των ερωτημάτων αυτών είναι το κεντρικής σημασίας top-k join. To κατανεμημένο top-k join, δεν έχει μελετηθεί επαρκώς, αν και συναντάται πολύ συχνά σε πραγματικό φόρτο εργασίας σε πολλά εμπορικά και άλλα συστήματα βάσεων δεδομένων. Με την εργασία αυτή αντιμετωπίζουμε τέτοιου είδους ερωτήματα πάνω σε δεδομένα που είναι κατανεμημένα σε ένα μεγάλου κλίμακας δίκτυο. Οι συνεισφορές μας με αυτήν την εργασία περιλαμβάνουν: (α) ένα νέο κατανεμημένο ευρετήριο, που επιτρέπει την πρόσβαση σε πλειάδες με τυχαίο και διατεταγμένο τρόπο, (β) ένα σύνολο αλγόριθμων για βαθμολογημένα ερωτημάτατα συνένωσης join. Οι αλγόριθμοί μας στηρίζονται στην προσαρμογή γνωστών αλγοριθμών κατωφλίου για βαθμολογημένο join σε κατανεμημένο περιβάλλον, (γ) μία νέα χρήση των Bloom φίλτρων και ιστογραμμάτων για την περαιτέρω μείωση του εύρους ζώνης που καταναλώνουν οι παραπάνω αλγόριθμοι, καθώς και απόδειξη για το ότι οι αλγόριθμοί μας που βασίζονται σε φίλτρα Bloom και ιστογράμματα παράγουν το σωστό top-k αποτέλεσμα, (δ) μια σε βάθος συζήτηση του σχεδιασμού των αλγορίθμων μας και θεμάτων που συνδέονται με τις επιδόσεις και τα trade-offs. Επιπλέον διερευνούμε την αποτελεσματικότητα και την ποιότητα των προτεινόμενων λύσεων μέσα από μία αναλυτική πειραματική αξιολόγηση, δείχνοντας τις περιπτώσεις που ο κάθε αλγόριθμός μας είναι κατάλληλος σε μαζικώς κατανεμημένα και αποκεντρωμένα περιβάλλοντα, ενώ τονίζουμε τα trade-offs που προκύπτουν. | el |
| dc.description.translatedabstract | The advent of peer-to-peer databases and the recent rise of cloudstores as key large-scale data management paradigms, have led researchers to look into the problem of supporting complex queries in a fully decentralized manner. Among the classes of queries considered in related centralized work, there is one that stands out as largely overlooked in widely distributed settings, albeit very common in real-world workloads: top-k joins. With this work we tackle such queries over data distributed across an internet-scale network. Our contributions include: (a) a novel distributed indexing scheme, allowing access to tuples in both a random and an ordered manner; (b) a set of query processing algorithms based on a novel adaptation of rank-join and threshold algorithms, appropriate for use in a distributed environment; (c) a novel use of Bloom Filters and histograms to further reduce the bandwidth consumption of the above algorithms; a proof that ensures that our algorithms based on Bloom filters and histograms produce the correct top-k results; and (d) an in-depth discussion of the design space and related performance trade-offs. We further investigate the efficiency and quality of the proposed solutions through an elaborate experimental evaluation, showcasing their appropriateness for widely-distributed and massively decentralized environments and highlighting related trade-offs. | el |
| dc.identifier.uri | http://hdl.handle.net/10889/5871 | |
| dc.language.iso | gr | el |
| dc.relation.isformatof | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. | el |
| dc.rights | 0 | el |
| dc.subject | Κατανεμημένες βάσεις δεδομένων | el |
| dc.subject | Top-k ερωτήματα | el |
| dc.subject | Rank ερωτήματα | el |
| dc.subject.alternative | Distributed databases | el |
| dc.subject.alternative | Top-k queries | el |
| dc.subject.alternative | Rank queries | el |
| dc.subject.alternative | Query processing | el |
| dc.subject.alternative | DHT | el |
| dc.subject.ddc | 005.74 | el |
| dc.title | Ερωτήματα συνένωσης και βαθμολογημένης συνένωσης σε κατανεμημένα συστήματα | el |
| dc.type | Thesis | el |