Τα νέφη υπολογιστών γίνονται ολοένα και πιο σημαντικά για εφαρμογές διαχείρισης δεδομένων, λόγω της δυνατότητας που προσφέρουν για διαχείριση πολύ μεγάλου όγκου δεδομένων. Καθημερινά προκύπτουν νέα προβλήματα, που η λύση τους απαιτεί αποδοτικές και κλιμακώσιμες εφαρμογές για την επεξεργασία αυτού του τεράστιου όγκου πληροφορίας. Κεντρικό ρόλο σε αυτόν τον τομέα κατέχουν τα συστήματα αποθήκευσης κλειδιού-τιμής σε νέφη υπολογιστών (cloud key-value stores), καθώς και συστήματα παράλληλης επεξεργασίας μεγάλης ποσότητας δεδομένων όπως το MapReduce. Τα ερωτήματα διαστημάτων εμφανίζονται συχνά σε πραγματικές εφαρμογές. Η εργασία αυτή ασχολείται με ερωτήματα διαστημάτων σε περιβάλλοντα νεφών υπολογιστών με κορυφαία εφαρμογή τα χρονικά ερωτήματα (temporal queries). Τέτοια ερωτήματα επικεντρώνονται συνήθως στο να απαντήσουν ποια γεγονότα συνέβησαν ή συνέβαιναν κατά την διάρκεια ενός χρονικού διαστήματος. ́Ομως τα παραδοσιακά συστήματα για τη διαχείριση τέτοιου είδους ερωτημάτων δεν μπορούν να αντεπεξέλθουν στον όγκο δεδομένων που παράγονται τη σημερινή εποχή από ορισμένες εφαρμογές, με αποτέλεσμα να μην υπάρχει μία αποδοτική λύση. Για να αντιμετωπιστεί το πρόβλημα αυτό προτείνεται η χρήση συστημάτων νεφών υπολογιστών, τέτοιων που θα καταστήσουν διαχειρίσιμο αυτόν τον τεράστιο όγκο δεδομένων. Τα υπάρχοντα, όμως, έως σήμερα συστήματα νεφών υπολογιστών δεν διαθέτουν τη δυνατότητα υποστήριξης τέτοιου είδους ερωτημάτων. Στην εργασία αυτή, αρχικά, μελετήθηκε το πρόβλημα και οι σχετικές λύσεις που είχαν προταθεί παλαιότερα, όπως πχ. τα δέντρα ευθυγράμμων τμημάτων (Segment trees). Αυτές οι δομές επιτρέπουν την απάντηση των ερωτημάτων που περιγράφονται παραπάνω με αποδοτικό τρόπο. Στη συνέχεια μελετήθηκε η δυνατότητα εφαρμογής τους σε περιβάλλοντα νεφών υπολογιστών, ενώ διερευνήθηκαν πιθανές εναλλακτικές λύσεις που θα εκμεταλλεύονται καλύτερα τις δυνατότητες που προσφέρουν τα συστήματα αυτά. Η μελέτη αυτή οδήγησε στην δημιουργία νέων δομών δεδομένων και αλγορίθμων, ή τροποποιήσεις των υπαρχόντων, που βοηθούν στην αποδοτική επίλυση του προβλήματος. Τέλος πραγματοποιήθηκε σύγκριση της απόδοσης των λύσεων και τον αλγορίθμων που προτείνονται με τις ήδη υπάρχουσες. Τα αποτελέσματα της σύγκρισης έδειξαν βελτίωση του χρόνου εκτέλεσης έως και μία τάξης μεγέθους σε μερικές περιπτώσεις. / The cloud is becoming increasingly more important for data management applications, as it can seamlessly handle huge amounts of data. New problems arise on a daily basis and can only be solved by the use of efficient and scalable applications that can process these data. Cloud key-value storage systems play a crucial role in this new field, along with systems like MapReduce that can distributedly process huge amounts of data. One of these problems appearing often is supporting interval queries, an efficient solution for which is lacking in the field of cloud key-value stores. This thesis deals with this problem, and more specifically with the problem of temporal queries. This kind of queries try to answer what happened during a specific time range. But in recent years there has been an explosion in how much data are produced from some applications, rendering traditional systems incapable of handling them. For handling this amount of data the use of cloud key-value stores is suggested. But these systems don't have any special functionality for enabling them to answer those queries. First, in this thesis, older solutions where studied, such as Segment Trees. These kinds of data structures can answer the queries described above in an efficient way. After that, it was studied whether these data structures can be deployed on top of cloud key-value stores, additionally other solutions were investigated that could take better advantage of these systems. Finally, the efficiency of these new methods is compared with those already existing. The comparisons results showed even an order of magnitude improvement on some occasions.

Ανέκαθεν, η ανάγκη του ανθρώπου για πληροφορία ήτανε μια από αυτές που φρόντιζε να ικανοποιήσει όσο το δυνατόν πληρέστερα. Η πληροφορία είναι σε όλες τις περιπτώσεις ένα πολύτιμο εργαλείο στην λήψη αποφάσεων και οι άνθρωποι γρήγορα αντιλήφθηκαν την σημασία της, ειδικότερα μάλιστα στην σύγχρονη εποχή στην οποία μέσω της επιστήμης της Πληροφορικής δόθηκε η δυνατότητα σε μεγάλο μέρος του κοινού να έχει πρόσβαση σε τεράστιο όγκο δεδομένων, τα οποία μέσω της σωστής επεξεργασίας μετατρέπονται σε πληροφορία. Αυτό που πλέον αποτελεί πρόκληση, η οποία μας καλεί σαν επιστήμονες της Πληροφορικής να αντιμετωπίσουμε, είναι η εύρεση και στην συνέχεια η εφαρμογή καινούργιων μεθόδων γρήγορης και ανέξοδης συλλογής, αποδοτικής αποθήκευσης και εποικοδομητικής ανάλυσης δεδομένων, έτσι ώστε να γίνουν πληροφορία ποιοτική, πλούσια και με σημαντική χρηστική αξία. Στις μέρες μας, η ανάπτυξη του κλάδου τόσο των κατανεμημένων συστημάτων όσο και του διαδικτύου, μας έχουνε δώσει την δυνατότητα να χρησιμοποιούνται χαμηλοί σε απαιτήσεις υπολογιστικοί πόροι για να επεξεργάζονται παράλληλα μεγάλο όγκο δεδομένων. Ο κλάδος της Πληροφορικής που ασχολείται εκτενώς με αυτά τα συστήματα είναι τα ομότιμα συστήματα ή αλλιώς p2p συστήματα και ο κατανεμημένος υπολογισμός. Η παρούσα διπλωματική εργασία έχει ως στόχο να βρίσκει σε κατανεμημένο περιβάλλον σημεία στις δύο διαστάσεις. Ορίζεται, δηλαδή, ένας χώρος από κ – διαστάσεις που είναι το πλέγμα (grid), στον οποίο ο χρήστης προσπαθεί να εντοπίσει σημεία που τον ενδιαφέρουν δημιουργώντας έτσι ερωτήματα εύρους. Το σύστημα θα ψάχνει να βρει το αποτέλεσμα στο ερώτημα αυτό για να καταλήξει σε ποιο από τα άλλα ορθογώνια τμήματα του πλέγματος εμπλέκεται και στην συνέχεια αυτά (τα τμήματα) θα επιστρέφονται. Πιο συγκεκριμένα, το πλέγμα μας χωρίζεται σε τετράγωνες περιοχές και κάθε κόμβος του κατανεμημένου δικτύου αναλαμβάνει να φιλοξενήσει τα σημεία της κάθε τετράγωνης περιοχής. Όλοι αυτοί οι κόμβοι οργανώνονται σε ένα hadoop cluster και τα δεδομένα εισάγονται στην κατανεμημένη βάση δεδομένων HBase που βασίζεται στην αρχιτεκτονική του BigTable της Google File System. Ο τρόπος που οργανώνονται τα δεδομένα στην HBase είναι κατανεμημένος και γίνεται χρήση των B+ -δέντρων. Η χρησιμότητα των B+ -δέντρων σε συνδυασμό με το κατανεμημένο πλαίσιο εργασίας του Hadoop, έγκειται στο γεγονός ότι με την χρήση των απαραίτητων εργαλείων τόσο της HBase όσο και του Hadoop FS, μπορούμε να γνωρίζουμε σε ποιόν κόμβο του hadoop cluster είναι αποθηκευμένοι οι ζητούμενοι κόμβοι του B+ -δέντρου και έτσι να επιτυγχάνεται η γρήγορη ανάκτηση των αποτελεσμάτων σε ένα ερώτημα εύρους. Η διάρθρωση της εργασίας έχει ως εξής: Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες του κατανεμημένου υπολογισμού πάνω σε κατανεμημένα περιβάλλοντα. Στο δεύτερο γίνεται μια αναφορά στα ομότιμα δίκτυα (p2p) και πιο συγκεκριμένα αναλύεται το δίκτυο επικάλυψης του BATON που έχει δενδρική δομή όμοια με αυτή του Β+ -δέντρου. Στο τρίτο κεφάλαιο αναφέρεται μια υλοποίηση δεικτοδότησης και απάντησης σε ερωτήματα εύρους στο Νέφος Υπολογιστών με χρήση βασικών δομών δεδομένων B+ -δέντρου. Επίσης, η ART Autonomous Range Tree δομή παρουσιάζεται η οποία μπορεί να υποστηρίξει ερωτήματα εύρους σε τόσο ευρείας κλίμακας σε μη κεντρικοποιημένα περιβάλλοντα και μπορεί να κλιμακώνεται σε σχέση με τον αριθμό των κόμβων, καθώς και με βάση τα στοιχεία που είναι αποθηκευμένα. Η ART δομή ξεπερνά τις πιο δημοφιλείς μη κεντρικοποιημένες δομές, συμπεριλαμβανομένου του Chord (και μερικοί από τους διαδόχους του), του ΒΑΤΟΝ (και τον διάδοχό του) και των Skip-Graphs. Στο τέταρτο και πέμπτο κεφάλαιο, αντίστοιχα, γίνεται μια αναφορά στα βασικότερα σημεία της αρχιτεκτονικής και της λειτουργίας του Hadoop Framework και της HBase. Στο έκτο κεφάλαιο, βρίσκεται η περιγραφή της υλοποίησης της παρούσης διπλωματικής εργασίας μαζί με τους αλγορίθμους και τον τρόπο λειτουργίας τους. Στο επόμενο γίνεται η αξιολόγηση των πειραματικών αποτελεσμάτων της παρούσης διπλωματικής εργασίας καθώς, και το τι συμπεράσματα προκύπτουν μέσα από την αξιολόγηση. Τέλος, στο τελευταίο και όγδοο κεφάλαιο γίνεται η αποτίμηση της διπλωματικής εργασίας, καθώς αναφέρονται τα βασικά της μέρη, όπως επίσης και πιθανές προεκτάσεις που θα βελτίωναν την απόδοση του συστήματος. / Traditionally, the human need for information was one of those seeking to satisfy as much as possible. Information is in every way a valuable tool in decision making and people quickly realized its importance, especially in modern times, when the Information Technology gave the public access to the vast volume of data, which can be further processed into information. What seems to be now a challenge that IT specialists have to face is finding and implementing new methods of fast and inexpensive data collection, efficient storing of data and constructive data analysis, in order to turn them into quality, rich and useful information. Nowadays, the devel-opment of both the field of distributed systems and the Internet gave us the possibility of using computational resources with low requirements for simultaneous processing of large amounts of data. The IT field that deals extensively with these systems are peer-to-peer systems (p2p) and distributed computing. The present dissertation aims at finding points in a distributed environment in the two-dimensional space. A space of k – dimensions is defined, i.e. the grid, in which the user tries to identify points of interest creating range queries. The system will search to find the result in this question to come up with the rectangular section of the grid that is involved and then these sections will be returned. More specifically, the grid is divided into square areas, and each node of the distributed network will accommodate points of each square area. All these nodes are organized into a hadoop cluster and the data is imported into the HBase distributed database based on BigTable architecture of the Google File System. In HBase data is organized in a distributed way and B+ -trees are used. The utility of B+ -trees in conjunction with the distributed framework of Hadoop lies on the fact that using the necessary tools of both HBase and Hadoop FS we can know in which hadoop cluster node the requested B+ -tree nodes are stored and thus achieve fast results retrieval in a range query. The structure of the project is as follows: The first chapter is an introduction to the concepts of distributed computing over distributed environments. The second is a reference to peer-to-peer networks (p2p) and more specifically the BATON overlay network, which has a tree structure similar to that of the B+ -tree, is analyzed. The third chapter deals with an indexation and answering implementation on range queries in the Computer Cloud using B+ -tree basic data structures. Also, ART Autonomous Range Tree structure is presented which can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. ART outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. In the fourth and fifth chapter respectively a reference is made to the main points of Hadoop Framework and HBase architecture and operation. The sixth chapter is the description of the implementation of this dissertation together with the algorithms and how they operate. The next chapter is the evaluation of the experimental results of this dissertation and of the conclusions that derive from the evaluation. Finally, the eighth and last chapter is an overview of the dissertation, mentioning its basic parts, as well as possible extensions that would improve the system performance.