c-perfect hashing schemes for binary trees, with applications to parallel memories (extended abstract)

We study the problem of mapping tree-structured data to an ensemble of parallel memory modules. We are given a "conflict tolerance" c, and we seek the smallest ensemble that will allow us to store any nvertex rooted binary tree with no more than c tree-vertices stored on the same module. Our attack on this problem abstracts it to a search for the smallest c-perfect universal graph for complete binary trees. We construct such a graph which witnesses that only O (c(1-1/c) · 2(n+1)/(c+1)) memory modules are needed to obtain the required bound on conflicts, and we prove that Ω( 2(n+1)/(c+1)) memory modules are necessary. These bounds are tight to within constant factors when c is fixed - as it is with the motivating application. © Springer-Verlag 2003.