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.

c-Perfect Hashing Schemes for Binary Trees, with Applications to Parallel Memories

CORDASCO, Gennaro;
2004

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.
2004
3-540-40788-X
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11591/181210
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact