| Περίληψη : | Object hierarchies are frequently used to model various concepts that exhibit containment properties. Examples include administration hierarchies for states, hierarchies that break down a complex system to its components, etc. Hierarchical graphs are directed multi-graphs, whose vertices are leaf nodes in a known hierarchy. The edges of such graphs have their source and destination vertices explicitly defined, and there may be more than one edges for any particular pair of vertices. An example of such a graph is the set of CDRs (Call Detail Records) for a particular area. CDRs can be depicted as edges in a graph structure, whose vertices are all the active telephone numbers in that area. In turn, telephone numbers usually form the leaf layer of a complex hierarchy, which is usually location-based. Graphs of this sort, which are constantly updated via streaming data, can grow to enormous size. Data ingestion speed then becomes a problem, as does query processing, where queries can include source and destination constraints that may appear as nodes anywhere in the hierarchy.The purpose of this work is to develop, test and compare a number of alternative implementations in HBase, of a system that facilitates batch data ingestion and query processing, by using Spark’s distributed computing engine to spread the processing load across a cluster of computers.The approach taken is based on the partition tree index described in [1], which is used as a first level index in all alternative implementations. Furthermore, we have incorporated a second level index, based on z-order curves, as this is explained in [2]. Our implementation of the z-order index is based on the already developed library in [3], to which a number of additions and other changes were made to fit into our framework.During the experimental evaluation phase we have tried to assess whether the inclusion of a second level index promotes query response performance sufficiently to be considered worthwhile, as well as how significantly it demotes ingestion process performance. Moreover, we have compared alternatives that include indices across two levels of the data to those that only include the partition index, to verify that there is indeed an improvement in performance. A number of more refined experiments have also been carried out to reach more specific conclusions.
Οι ιεραρχίες χρησιμοποιούνται συχνά για τη μοντελοποίηση εννοιών που παρουσιάζουν ιδιότητες συμπερίληψης. Ως παραδείγματα μπορούν να αναφερθούν διοικητικές ιεραρχίες κρατών, ιεραρχίες που αποσυνθέτουν ένα πολύπλοκο σύστημα στα συστατικά του, κ.α. Οι ιεραρχικοί γράφοι είναι πολυ-γράφοι, των οποίων οι κορυφές αποτελούν τα φύλλα κάποιας γνωστής ιεραρχίας. Για τις ακμές τέτοιων γράφων η αφετηρία και ο προορισμός καθορίζονται σαφώς, και σε κάθε ζεύγος κορυφών μπορούν να αντιστοιχούν παραπάνω από μία ακμές. Παράδειγμα ενός τέτοιου γράφου είναι το σύνολο των CDRs (CallDetailRecords – εγγραφές που περιλαμβάνουν λεπτομέρειες για μία συγκεκριμένη τηλεφωνική κλήση) για μία συγκεκριμένη περιοχή. Οι CDRs μπορούν να αναπαρασταθούν σαν ακμές ενός γράφου, του οποίου οι κορυφές σχηματίζουν το στρώμα φύλλων μίας πολύπλοκης ιεραρχίας, η οποία συνήθως είναι γεωγραφικής φύσεως. Γράφοι αυτού του είδους, οι οποίοι ενημερώνονται συνέχεια μέσω ρευμάτων δεδομένων, είναι δυνατόν να αποκτήσουν τεράστιο μέγεθος. Η κατανάλωση δεδομένων σε αυτή την περίπτωση εξελίσσεται σε πρόβλημα, όπως και η επεξεργασία επερωτήσεων, οι οποίες περιλαμβάνουν περιορισμούς που συναντώνται σαν κόμβοι οπουδήποτε στην ιεραρχία.Ο σκοπός αυτής της εργασίας είναι να αναπτυχθούν, ελεγχτούν και συγκριθούν μεταξύ τους εναλλακτικές υλοποιήσεις στην HBase, ενός συστήματος που διευκολύνει τη μαζική κατανάλωση δεδομένων και την επεξεργασία επερωτήσεων, χρησιμοποιώντας την κατανεμημένη υπολογιστική μηχανή του Spark ώστε να εξαπλώσει το φόρτο επεξεργασίας επί μίας συστάδας υπολογιστών.Η προσέγγιση που υιοθετείται βασίζεται στο ευρετήριο δέντρου κατάτμησης, όπως αυτό περιγράφεται στο [1], το οποίο χρησιμοποιείται ως ένα ευρετήριο πρώτου επιπέδου σε όλες τις εναλλακτικές υλοποιήσεις. Επιπλέον, έχει ενσωματωθεί και ένα ευρετήριο δευτέρου επιπέδου, το οποίο βασίζεται σε καμπύλες z-τάξης, όπως αυτό περιγράφεται στο [2]. Η παρούσα υλοποίηση του ευρετηρίου z-τάξης βασίζεται στην ήδη υπάρχουσα που αναπτύχθηκε στο [3], επί του οποίου έχουν πραγματοποιηθεί μία σειρά από προσθήκες και άλλες αλλαγές ώστε να συντεθεί με το τρέχον πλαίσιο.Κατά την πειραματική αξιολόγηση έγινε προσπάθεια να εκτιμηθεί αν η συμπερίληψη ενός ευρετηρίου δευτέρου επιπέδου προάγει την αποδοτικότητα επεξεργασίας επερωτήσεων αρκετά ώστε να μπορεί να θεωρηθεί αξιόλογη προσθήκη, αλλά και κατά πόσο υποβιβάζει την αποδοτικότητα της διαδικασίας κατανάλωσης δεδομένων. Επιπροσθέτως, πραγματοποιήθηκε σύγκριση μεταξύ υλοποιήσεων που υποστηρίζουν ευρετήρια επί δύο επιπέδων των δεδομένων, και αυτών που υποστηρίζουν μόνο το ευρετήριο δέντρου κατάτμησης, προκειμένου να επιβεβαιώσουμε ότι όντως υπάρχει διαφορά στην απόδοση. Τέλος, εκτελέστηκαν κάποια πιο εξειδικευμένα πειράματα για την εξαγωγή συμπερασμάτων που αφορούν σε ορισμένες ειδικές περιπτώσεις.
|
|---|
Copyright © 2013 Βιβλιοθήκη Ο.Π.Α. Με την επιφύλαξη παντός δικαιώματος.