Η ανάπτυξη των peer-to-peer βάσεων δεδομένων και η δυναμική εισαγωγή των συστημάτων αποθήκευσης σε νέφη υπολογιστών (cloudstores) ως τα κυρίαρχα μεγάλης κλίμακας συστήματα διαχείρισης δεδομένων, έχουν οδηγήσει τους ερευνητές να εξετάσουν το πρόβλημα της
υποστήριξης πολύπλοκων ερωτημάτων με ένα πλήρως αποκεντρωμένο τρόπο. Περίπλοκα ερωτήματα επιλογής (select), συνένωσης join, καθώς και βαθμολογημένα ερωτήματα έχουν κεντρίσει το ενδιαφέρον της κοινότητας διαχείρισης δεδομένων.
Ανάμεσα στις τάξεις των ερωτημάτων αυτών είναι το κεντρικής σημασίας top-k join. To κατανεμημένο top-k join, δεν έχει μελετηθεί επαρκώς, αν και συναντάται πολύ συχνά σε πραγματικό φόρτο εργασίας σε πολλά εμπορικά και άλλα συστήματα βάσεων δεδομένων.
Με την εργασία αυτή αντιμετωπίζουμε τέτοιου είδους ερωτήματα πάνω σε δεδομένα
που είναι κατανεμημένα σε ένα μεγάλου κλίμακας δίκτυο.
Οι συνεισφορές μας με αυτήν την εργασία περιλαμβάνουν: (α) ένα νέο κατανεμημένο ευρετήριο,
που επιτρέπει την πρόσβαση σε πλειάδες με τυχαίο και
διατεταγμένο τρόπο, (β) ένα σύνολο αλγόριθμων για βαθμολογημένα ερωτημάτατα συνένωσης join. Οι αλγόριθμοί μας
στηρίζονται στην προσαρμογή γνωστών αλγοριθμών κατωφλίου για βαθμολογημένο join
σε κατανεμημένο περιβάλλον, (γ) μία νέα χρήση των Bloom φίλτρων και ιστογραμμάτων για την περαιτέρω μείωση του εύρους ζώνης
που καταναλώνουν οι παραπάνω αλγόριθμοι, καθώς και απόδειξη για το ότι οι
αλγόριθμοί μας που βασίζονται σε φίλτρα Bloom και ιστογράμματα παράγουν το σωστό top-k αποτέλεσμα, (δ) μια σε βάθος συζήτηση του
σχεδιασμού των αλγορίθμων μας και θεμάτων που συνδέονται με τις επιδόσεις και τα trade-offs.
Επιπλέον διερευνούμε την αποτελεσματικότητα και την ποιότητα των προτεινόμενων λύσεων
μέσα από μία αναλυτική πειραματική αξιολόγηση, δείχνοντας τις περιπτώσεις που ο κάθε αλγόριθμός μας είναι κατάλληλος σε
μαζικώς κατανεμημένα και αποκεντρωμένα περιβάλλοντα, ενώ τονίζουμε τα trade-offs που προκύπτουν. / 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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/5871 |
| Date | 28 February 2013 |
| Creators | Πατλάκας, Ιωάννης |
| Contributors | Τριανταφύλλου, Παναγιώτης, Patlakas, Ioannis, Τριανταφύλλου, Παναγιώτης, Βαρβαρίγος, Εμμανουήλ, Γαροφαλάκης, Ιωάννης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0027 seconds