Multi-way self-adjusting data structures: a general theory and some limitations

Abstract

In Chapter 1, “Introduction: The Searching Problem,” we present a concise history of the searching problem, from the original divide-and-conquer, known intuitevely even to children, up to the formulation of contemporary concepts such as amortized analysis and competitiveness. Our own work focuses on the situations in which we can do better than classical binary search trees, namely in biased searching, when balanced trees “lose” because of their “over-balancedness”. The classical answer to this problem, biased search trees, is clearly of little practical use because of the strict assumptions made. We present the reforms of Sleator and Tarjan’s splay technique and extensions by Subramanian and by Sherk. In this context we summarize our main results: (1) a generalization of almost all aspects of the results of Subramanian together with a substantial weaking of the conditions required for a self-adjustment scheme to exhibit optimality in several biased situations (explained fully in Chapter 2) and (2) our refutation of Sherk’s conjecture (explained fully in Chapter 3). In Chapter 2, “Multi-way Splaying: A General Theory and Calculus,” we develop a general theory of selfadjusting tree-based data structures. First we decouple the details of self-adjustment from the underlying invariant conditions necessary for the data structure to operate as designed. This provides the ability to impose self-adjustment on almost any tree-based data structure, guaranteeing performance in schemes other than search trees. We then present in detail the strict set of conditions required by Subramanian’s proof, and how these can be greatly reduced. The impression left at the end is that the vast majority of template sets for self-adjustment satisfy our criteria, and thus the end-user has a great degree of freedom to choose a selfadjustment scheme that respects the invariant condition required. In Chapter 3, “The Limitations of Multi-Way Self-Adjusting Schemata,” we refute Sherk’s conjecture that the -splay technique for self-adjustment achieves nodes visited, amortized. With respect to classical data structures (non-self-adjusting) we may choose B-trees over binary trees, because the number of nodes visited is reduced by a factor of . Sherk’s conjecture is that -splay provides an analogous reduction in the context of self-adjustment. We demonstrate a family of degree- trees for which -splay behaves as if it were operating on a binary tree. Besides the lower bound for -splay implied by the existence of this family of trees, they have other interesting properties which we explore. In the final chapter, Chapter 4, “Summary and Conclusions,” we summarize our work, presenting several possible directions for further research.

Επειδή ισορροπημένα δυαδικά δένδρα (Μαύρα-Κόκκινα, AVL, B-δένδρα, κλπ.) εγγυούνται χειρίστης περιπτώσεως πλοκή τάξεως O(log N) εκάστης λειτουργίας, είναι επαρκή για πολλές εφαρμογές, ακόμη αυτές που χειρίζονται μεγάλου πλήθους δεδομένα. Όμως όταν υφίσταται μεροληψία (τα στοιχεία προσπελαύνονται με διαφορετικές συνότητες), αποδεικνύονται υποβέλτιστα, όπου ο συντελεστής υποβελτιστότητας αυξάνεται με την μεροληψία. Αυτό αντιμετωπίζεται με στατικά μεροληπτικά δένδρα, όμως οι συνθήκες υπό τις οποίες παρέχουν καλές επιδόσεις είναι ισχυρές έως μη ρεαλιστικές. Τα δε αρθρωτά δένδρα αντιμετωπίζουν μεροληψία με τέτοιον τρόπο, ώστε για κάθε ιστορία H, το κόστος τους να μην ξεπερνά O(1) φορές του βέλτιστου στατικού δένδρου επί της ίδιας ιστορίας, δηλαδή είναι στατικά βέλτιστα. Παρέχουν επιπλέον επιθυμητές ιδιότητες (working set ιδιότητα, στατικό finger θεώρημα) και εικάζονται να είναι δυναμικώς βέλτιστα. Θεωρητική δουλειά σ' αυτό το θέμα έχει δείξει ότι άλλων μορφών αυτορρύθμιση εγγυάται επίσης χειρίστης περιπτώσεως λογαριθμικό κόστος, εφ' όσον υπακούν σ' ένα σύνολο κριτηρίων. Η παρούσα διατριβή παρουσιάζει αποτελέσματα που αναπτύσσουν τις διαθέσιμες τεχνικές για την δημιουργία και ανάλυση αυτορρυθμιζόμενων δομών δεδομένων. Συγκεκριμένα, ενοποιούμε την θεωρία δυαδικών δένδρων με δένδρα μεγαλύτερου βαθμού και αποσυνδέουμε την αυτορρυθμιστική πολιτική από τις αναλλοίωτες συνθήκες της εγγενούς δομής. Παρουσιάζουμε νέα διατύπωση του δυναμικού, βασιζόμενο στις ακμές αντί των ακμών, η οποία επιτρέπει πιο ακριβή εκτίμηση των μεταβολών του δυναμικού σε αυτορρυθμιστικά βήματα. Χρησιμοποιούμε αυτό για να χαλαρώσουμε τις συνθήκες υπό τις οποίες η αυτορρύθμηση εγγυάται λογαριθμικό κόστος και στατική βελτιστότητα, δείχνοντας ότι η μεγαλύτερη πλειοψήφία των αυτορρυθμιστικών σχημάτων παρέχει την επιθυμητή πλοκή. Παρουσιάζουμε μερικά παραδείγματα αυτής της θεωρίας: τα «κατά τη μέση» διασπώμενα δένδρα, τα «ως log N» δένδρα και μία απλοποίηση της ανάλυσης του heuristic της «εξισορρόπησης του κλάδου». Παραλλαγές των B-δένδρων χρησιμοποιούνται σχεδόν κατ' αποκλειστικότητα σε βάσεις δεδομένων διότι μπορούν να μειώνουν τις προσπελάσεις στον δίσκο κατά ένα παράγοντα του log(2) k, όπου k ορίζει το βαθμό των δένδρων. Ο Sherk και άλλοι αναζήτησαν υποψήφια αυτορρυθμιζόμενα σχήματα, τα οποία να δίδουν στα B-δένδρα τις ιδιότητες που επιτυγχάνει η αυτορρύθμιση, και το k-splay είναι το πιο πιθανό υποψήφιο σχήμα. Αποδεικνύουμε ότι δεν δύναται να επιτύχει την κατά log(2) k μείωση στην πλοκή, μετρούμενη ως προσπελαστούς κόμβους, αναδεικνύοντας ως αντιπαράδειγμα μία κλάση δένδρων με πολλές συμμετρίες και άλλες αξιοπαρατήρητες ιδιότητες. Αυτό δημιουργεί αμφιβολίες για την ύπαρξη τέτοιου σχήματος.