Υβριδικό ευρετήριο κύριας μνήμης με βάση τα προθέματα (EL)

A prefix-based hybrid solution for main memory indexin (EN)

Christodoulou, George (EN)

Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής (EL)

Μαμουλής, Νικόλαος (EL)

Christodoulou, George (EN)

Η αποδοτική ανάκτηση στην κύρια μνήμη καθίσταται όλο και πιο σημαντική στις σύγχρονες εφαρμογές που διαχειρίζονται τεράστιους όγκους δεδομένων (π.χ. δεδο- μένα IoT και κοινωνικών δικτύων). Αυτό είναι ιδιαίτερα σημαντικό για αποθήκες δεδομένων κλειδιών-τιμών που χειρίζονται πολλά ζεύγη κλειδιών-τιμών τα οποία θα πρέπει να προσφέρουν πρόσβαση σε νανοδευτερόλεπτα. Σε αυτή τη διατριβή, παρουσιάζουμε το POT (Performance Optimized Tree), ένα νέο υβριδικό δέντρο, που συνδυάζει το bucketing με τα προθέματα δεδομένων. Σχεδιάζουμε ένα δέντρο το οποίο υποστηρίζει λειτουργίες γρήγορης αναζήτησης. Το δέντρο αποτελείται από επίπεδα που εξαρτώνται από τα τμήματα της ανα- παράστασης δεδομένων τα οποία ονομάζονται προθέματα και οι κόμβοι φύλλων υποδεικνύουν εύρη τιμών των ευρεθέντων δεδομένων, που ονομάζονται “κάδοι“ δε- δομένων. Κατασκευάζουμε το δέντρο έτσι ώστε να μπορούμε να προσπελάσουμε τα επίπεδα του δέντρου χωρίς συγκρίσεις και στη συνέχεια να χρησιμοποιήσουμε δυαδική αναζήτηση για να καταλήξουμε με ακρίβεια στην τιμή που αναζητάμε. Το δέντρο μας μπορεί εύκολα να προσαρμοστεί σε οποιοδήποτε τύπο δεδομένων και κατανομή δεδομένων, καθώς χρησιμοποιεί τη δυαδική αναπαράσταση των κλει- διών αναζήτησης. Οι κόμβοι του δέντρου είναι προσεκτικά κατασκευασμένοι ώστε να είναι συμπαγείς και να υποστηρίζουν γρήγορη αναζήτηση. Το POT υποστηρίζει ερωτήματα σημείων και εύρους. Αξιολογούμε την απόδοση του δέντρου σε ένα συνθετικό και δύο πραγματικά σύνολα δεδομένων και τη συγκρίνουμε με τις αποδόσεις άλλων δημοφιλών δομών ευρετηρίου. Τα αποτελέσματά μας δείχνουν ότι η προσέγγισή μας μπορεί να απο- δώσει πολύ καλύτερα από τις υπάρχουσες τεχνικές. Επίσης, μελετάμε το πρόβλημα της προσαρμογής της δομής ευρετηρίου, ανάλογα με το μέγεθος και τη κατανομή των δεδομένων. (EL)

Efficient retrieval in main memory is becoming increasingly important in modern applications that manage huge amounts of data (e.g. IoT and social network data). This is especially relevant for key-value stores which handle numerous key-value pairs which should be accessed in nanoseconds. In this thesis, we introduce POT (Performance Optimized Tree), a novel hybrid tree, combining bucketing with data prefixes. We design a tree, which supports fast search operations. The tree consists of levels depending on segments of the data representation called prefixes and the leaf nodes point to ranges of the indexed data values, called buckets. We construct the tree so that we can hop through its levels without comparisons and then use binary search for the last mile accuracy. Our tree can easily adapt to any type of data and data distribution as we consider the binary representation of the indexed values. The layout of each node is carefully constructed for compactness and fast search. POT supports point and range queries. We evaluate the performance of the tree on two real and one synthetic dataset and compare the results with other popular index structures. Our results indicate that our approach can perform much better than existing techniques. We also study the problem of tuning the index, depending on the data size and distribution. (EN)

masterThesis

Βάσεις δεδομένων (EL)

Database (EN)

Πανεπιστήμιο Ιωαννίνων

Ιδρυματικό Αποθετήριο Ολυμπιάς

Πολυτεχνική Σχολή

ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"

Αγγλική γλώσσα

2020

https://olympias.lib.uoi.gr/jspui/handle/123456789/29875

Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής (EL)