Efficient query processing over highly distributed data

Abstract

The objective of this thesis is to investigate the performance of query processing over highly distributed data. Peer-to-peer (P2P) systems emerge as a powerful model for searching vast amounts of data distributed over independent sources. While different peer-to-peer architectures have been proposed in the related research literature, in this thesis we focus on unstructured peer-to-peer networks. Some peers, called super-peers, have special roles due to their enhanced features, such as availability, stability, storage and bandwidth capacity, and form a super-peer network. We study how various advanced query operators, such as similarity search (range and k nearest neighbor queries), top-k and skyline queries can be performed efficiently over a super-peer network, where the data objects are horizontally distributed over the peers. In order to support query processing, queries are first routed on the super-peer backbone and afterwards, if necessary, they are forwarded to the peers with relevant data. In this thesis, we study efficient query processing over such a highly distributed architecture, by using routing information at super-peer level in a deliberate way, aiming at minimizing contacted peers and transferred data.

Η παρούσα διδακτορική διατριβή επικεντρώνεται στον χώρο της επεξεργασίας μη παραδοσιακών τύπων επερωτήσεων σε ευρέως κατανεμημένα δεδομένα όπως αυτά που συναντώνται σε δίκτυα ομότιμων (peer-to-peer). Τα δίκτυα ομότιμων προβάλλουν ως ένα δυναμικό μοντέλο για την αναζήτηση και διαχείριση τεράστιων ποσοτήτων δεδομένων κατανεμημένων σε ανεξάρτητες πηγές δεδομένων. Ενώ διάφορες αρχιτεκτονικές ομότιμων συστημάτων έχουν προταθεί στη σχετική βιβλιογραφία, σε αυτή τη διατριβή βρίσκονται στο επίκεντρο τα αδόμητα δίκτυα ομότιμων κόμβων. Ορισμένοι ομότιμοι, που ονομάζονται super-peers, έχουν ειδικό ρόλο λόγω των ιδιαίτερων χαρακτηριστικών τους, όπως διαθεσιμότητα, σταθερότητα, αυξημένη αποθηκευτική δυνατότητα και μεγάλο εύρος ζώνης, και διαμορφώνουν ένα super-peer δίκτυο. Μελετώνται διάφοροι προηγμένοι τελεστές επερώτησης, όπως η αναζήτηση με βάση την ομοιότητα, οι top-k και skyline επερωτήσεις, καθώς και ο αποδοτικός υπολογισμός αυτών σε ένα super-peer δίκτυο, όπου τα δεδομένα είναι οριζόντια κατατμημένα στους ομότιμους. Για την επεξεργασία επερωτήσεων, οι επερωτήσεις πρώτα δρομολογούνται στο δίκτυο των super-peers, και στη συνέχεια προωθούνται σε εκείνους τους ομότιμους που έχουν σχετικά δεδομένα. Σε αυτή τη διατριβή εξετάζεται η αποδοτική επεξεργασία επερωτήσεων σε μια τέτοια ευρέως κατανεμημένη αρχιτεκτονική, χρησιμοποιώντας πληροφορία δρομολόγησης σε επίπεδο super-peers, με στόχο την ελαχιστοποίηση των ομότιμων που θα επεξεργαστούν την επερώτηση και του όγκου των δεδομένων που θα μεταφερθούν.