Organizing and searching data in unstructured P2P networks

Abstract

As data generation becomes increasingly inherently distributed, either due to user-generated (multimedia) content or because of application-specific needs (sensor networks, data streams, etc.), traditional centralized architectures fail to address the new challenges of contemporary data management. A promising solution for the design and deployment of global-scale applications is the exploitation of the peer-to-peer (P2P) paradigm. P2P has emerged as a powerful model for organizing and searching large data repositories distributed over autonomous independent sources. The main topic and contribution of this thesis is the unsupervised organization of content into Semantic Overlay Networks (SONs), in a decentralized and distributed manner, and subsequently a variety of techniques for efficient searching and query processing in unstructured P2P systems. SONs have been proposed in the relevant research literature, as a way to organize peers into thematic groups, thereby enabling query routing to specific peer groups in a deliberate way, instead of blind forwarding. In particular, this work focuses on unstructured P2P networks that preserve peer autonomy. A novel protocol for unsupervised, distributed and decentralized SON construction is proposed, named DESENT, which employs distributed clustering of peer contents, respecting the requirements imposed by the distributed nature of the environment. Exploiting the generated SONs, we propose efficient routing strategies for answering similarity search queries. The approach is applied and tested in a distributed IR setting, aiming to address some of the limitations of P2P IR/web search. Towards this goal, a distributed dimensionality reduction algorithm is proposed, in order to reduce the high-dimensional feature space and improve clustering quality. Assuming a super-peer architecture we propose an approach called SIMPEER that efficiently supports similarity search over data distributed over a large set of peers. We show how range queries and nearest neighbor queries can be processed. We also explore how to support non-traditional queries (such as top-k and skylines) that involve ranking. Furthermore, by relaxing the restriction of completely unsupervised environment and assuming a semi-supervised context, a novel technique for P2P summary caching of hierarchical information is presented, exploiting either predefined taxonomies or XML schema information, which is applied in mobile P2P context-aware environments to improve query routing.

Καθώς η διαχείριση δεδομένων γίνεται ολοένα και περισσότερο κατανεμημένη, είτε λόγω (πολυμεσικού) περιεχόμενου παραγόμενου από τους χρήστες ή λόγω αναγκών συγκεκριμένων εφαρμογών (δίκτυα αισθητήρων, ροές δεδομένων, κτλ.), οι παραδοσιακές κεντρικοποιημένες αρχιτεκτονικές αποτυγχάνουν να αντιμετωπίσουν τις νέες προκλήσεις της σύγχρονης διαχείρισης δεδομένων. Μια υποσχόμενη λύση για τη σχεδίαση και υλοποίηση ευρείας κλίμακας εφαρμογών είναι χρήση των δικτύων ομότιμων κόμβων. Τα δίκτυα ομότιμων προβάλουν ως ένα ισχυρό μοντέλο για την οργάνωση και αναζήτηση μεγάλων βάσεων δεδομένων, οι οποίες είναι κατανεμημένες σε αυτόνομες και ανεξάρτητες οντότητες. Το κύριο θέμα και η κύρια συνεισφορά της παρούσας διδακτορικής διατριβής είναι η μη-εποπτευόμενη οργάνωση περιεχομένου σε Σημασιολογικά Υπερκείμενα Δίκτυα (ΣΥΔ), με τρόπο κατανεμημένο και αποκεντρωμένο, και ακολούθως μια ποικιλία τεχνικών για αποδοτική αναζήτηση και επεξεργασία επερωτήσεων σε αδόμητα δίκτυα ομότιμων. Τα ΣΥΔ έχουν προταθεί στη σχετική βιβλιογραφία σαν ένας τρόπος οργάνωσης κόμβων σε θεματολογικές ομάδες, ώστε να είναι εφικτή η δρομολόγηση επερωτήσεων σε συγκεκριμένες ομάδες κόμβων στοχευμένα, αντί για τυφλή προώθηση. Πιο συγκεκριμένα, η εργασία αυτή επικεντρώνεται σε αδόμητα δίκτυα ομότιμων που διατηρούν την αυτονομία των κόμβων. Προτείνεται ένα νέο πρωτόκολλο για μη-εποπτευόμενη, κατανεμημένη και αποκεντρωμένη κατασκευή ΣΥΔ, με το όνομα DESENT, το οποίο στηρίζεται σε κατανεμημένη συσταδοποίηση των περιεχομένων των κόμβων, με σεβασμό προς τις απαιτήσεις που επιβάλλει η κατανεμημένη φύση του περιβάλλοντος. Εκμεταλλευόμενοι τα ΣΥΔ που δημιουργούνται, προτείνουμε αποδοτικές στρατηγικές δρομολόγησης για την απάντηση επερωτήσεων με βάση την ομοιότητα. Η προσέγγιση εφαρμόζεται και ελέγχεται σε ένα περιβάλλον κατανεμημένης ανάκτησης πληροφορίας, στοχεύοντας να αντιμετωπίσει κάποιους από τους περιορισμούς της αναζήτησης και ανάκτησης πληροφορίας από το Διαδίκτυο. Για αυτό το σκοπό, προτείνεται ένας κατανεμημένος αλγόριθμος μείωσης διάστασης, ώστε να μειώσει την υψηλή διάσταση του χώρου αναπαράστασης των αντικειμένων και να βελτιώσει την ποιότητα της συσταδοποίησης. Υποθέτοντας μια αρχιτεκτονική με υπερ-κόμβους, προτείνουμε μια προσέγγιση με το όνομα SIMPEER που υποστηρίζει αποδοτική αναζήτηση με βάση την ομοιότητα πάνω από δεδομένα κατανεμημένα σε ένα μεγάλο σύνολο κόμβων. Δείχνουμε με ποιο τρόπο ερωτήματα με βάση την ακτίνα και ερωτήματα κοντινότερου γείτονα μπορούν να επεξεργαστούν. Επίσης, εξετάζουμε πώς μπορούν να υποστηριχθούν μη-παραδοσιακοί τύποι επερωτήσεων (όπως επερωτήσεις για τα $k$ καλύτερα αντικείμενα και επερωτήσεις κορυφογραμμών) που εμπεριέχουν κατάταξη. Επιπρόσθετα, χαλαρώνοντας τον περιορισμό του μη-εποπτευόμενου περιβάλλοντος και υποθέτοντας ένα ημι-εποπτευόμενο παριβάλλον, παρουσιάζεται μια νέα τεχνική για προσωρινή αποθήκευση περιλήψεων πληροφορίας ιεραρχικά δομημένης σε δίκτυα ομότιμων, χρησιμοποιώντας είτε προκαθορισμένες ταξινομίες είτε πληροφορία se XML σχήμα, η οποία εφαρμόζεται σε περιβάλλον κινητών συσκευών όπου η περιρρέουσα κατάσταση παίζει σημαντικό ρόλο, για τη βελτίωση της δρομολόγησης επερωτήσεων.