Υβριδικό ευρετήριο κύριας μνήμης με βάση τα προθέματα
(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)
University of Ioannina
