Reducing splaying by taking advantage of working sets

T. Aho, T. Elomaa, J. Kujala

    Research output: Contribution to journalArticleScientificpeer-review

    1 Citation (Scopus)
    45 Downloads (Pure)

    Abstract

    Access requests to keys stored into a data structure often exhibit locality of reference in practice. Such a regularity can be modeled, e.g., by working sets. In this paper we study to what extent can the existence of working sets be taken advantage of in splay trees. In order to reduce the number of costly splay operations we monitor for information on the current working set and its change. We introduce a simple algorithm which attempts to splay only when necessary. Under worst-case analysis the algorithm guarantees an amortized logarithmic bound. In empirical experiments it is 5% more efficient than randomized splay trees and at most 10% more efficient than the original splay tree. We also briefly analyze the usefulness of the commonly-used Zipf’s distribution as a general model of locality of reference.
    Translated title of the contributionReducing splaying by taking advantage of working sets
    Original languageEnglish
    Pages (from-to)1-13
    Number of pages13
    JournalLecture Notes in Computer Science
    Volume5038
    DOIs
    Publication statusPublished - 2008
    Publication typeA1 Journal article-refereed

    Publication forum classification

    • Publication forum level 1

    Fingerprint

    Dive into the research topics of 'Reducing splaying by taking advantage of working sets'. Together they form a unique fingerprint.

    Cite this