| Περίληψη |
Επειδή ισορροπημένα δυαδικά δένδρα (Μαύρα-Κόκκινα, 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 μείωση στην πλοκή, μετρούμενη ως προσπελαστούς κόμβους, αναδεικνύοντας ως αντιπαράδειγμα μία κλάση δένδρων με πολλές συμμετρίες και άλλες αξιοπαρατήρητες ιδιότητες. Αυτό δημιουργεί αμφιβολίες για την ύπαρξη τέτοιου σχήματος.
|
Multi-Way Self-Adjusting Data Structures: A General Theory and Some Limitations
