How to pack trees

In a virtual memory system, the address space is partitioned into pages, an d the main memory serves as a cache to the disk. In this setting, we addres s the following problem: Given a tree, find an allocation of its nodes to p ages, so-called a packing, which optimizes the cache performance for some a ccess pattern to the tree nodes. We investigate a model for tree access in which a node is accessed only via the path leading to it from the root. Two cost functions are considered: the total number of different pages visited in the search, and the number of page faults incurred. It is shown that bo th functions can be optimized simultaneously. An efficient dynamic programm ing algorithm to find an optimal packing is presented. The problem of findi ng an optimal packing which also uses the minimum number of pages is shown to be NP-complete. However, an efficient approximation algorithm is present ed. This algorithm finds a packing that uses the minimum number of pages an d requires at most one extra page fault per search. Finally, we study this problem in the context of dynamic trees which allow insertions and deletion s. (C) 1999 Academic Press.