Name
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 n-vertex 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 Omega(2((n+1)/(c+1))) memory modules are necessary. These bounds axe tight to within constant factors when c is fixed-as it is with the motivating application. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-45209-6_125 | LECTURE NOTES IN COMPUTER SCIENCE |
Keywords | Field | DocType |
tree structure,data structure,binary tree,structured data | Data structure,Complete graph,Discrete mathematics,Graph,Combinatorics,Distributed memory,Binary tree,Perfect hash function,Hash function,Universal graph,Mathematics,Distributed computing | Conference |
Volume | ISSN | Citations |
2790 | 0302-9743 | 2 |
PageRank | References | Authors |
0.39 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gennaro Cordasco | 1 | 344 | 47.06 |
| Alberto Negro | 2 | 74 | 11.67 |
| Vittorio Scarano | 3 | 609 | 71.49 |
| Arnold L. Rosenberg | 4 | 105 | 9.51 |