Data replication in static tree structures

Complete mappings from the nodes of T to blocks are described when nodes can be replicated, the amount of replication is controlled, and the block-number is optimized. A node of T can be mapped to more than one block and is thus available in different blocks. It is shown that any tree T of height h...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2003-05, Vol.86 (4), p.197-202
Main Authors: Hambrusch, Susanne E, Liu, Chuan-Ming
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Blocknumber
Computer science
control theory
systems
Data processing. List processing. Character string processing
Data replication
Exact sciences and technology
Information retrieval. Graph
Information systems. Data bases
Memory organisation. Data processing
Secondary storage
Software
Static tree structures
Studies
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Complete mappings from the nodes of T to blocks are described when nodes can be replicated, the amount of replication is controlled, and the block-number is optimized. A node of T can be mapped to more than one block and is thus available in different blocks. It is shown that any tree T of height h has a complete mapping with a total replication factor of t = 3/2 and achieving a blocknumber of at most [{h - log d B)/B] + 2.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(02)00503-3