Efficient tree layout in a multilevel memory hierarchy

Michael A. Bender, Erik D. Demaine, Martin Farach-Colton

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize the expected number of block transfers performed during a search operation, subject to a given probability distribution on the leaves. This problem was previously considered by Gil and Itai, who show optimal but high-complexity algorithms when the block-transfer size is known. We propose a simple greedy algorithm that is within an additive constant strictly less than 1 of optimal. We also present a relaxed greedy algorithm that permits more flexibility in the layout while decreasing performance (increasing the expected number of block transfers) by only a constant factor. Finally, we extend this latter algorithm to the cache-oblivious setting in which the block-transfer size is unknown to the algorithm; in particular this extension solves the problem for a multilevel memory hierarchy. The query performance of the cache-oblivious layout is within a constant factor of the query performance of the optimal layout with known block size.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
    EditorsRolf Möhring, Rajeev Raman
    PublisherSpringer Verlag
    Number of pages9
    ISBN (Electronic)3540441808, 9783540441809
    StatePublished - 2002
    Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
    Duration: Sep 17 2002Sep 21 2002

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other10th Annual European Symposium on Algorithms, ESA 2002

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Efficient tree layout in a multilevel memory hierarchy'. Together they form a unique fingerprint.

    Cite this