Optimal storage placement for tree-structured networks with heterogeneous channel costs

Ge Ming Chiu*, Li-Hsing Yen, Tai Lin Chin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


This work considers data query applications in tree-structured networks, where a given set of source nodes generate (or collect) data and forward the data to some halfway storage nodes for satisfying queries that call for data generated by all source nodes. The goal is to determine an optimal set of storage nodes that minimizes overall communication cost. Prior work toward this problem assumed homogeneous channel cost, which may not be the case in many network environments. We generalize the optimal storage problem for a tree-structured network by considering heterogeneous channel costs. The necessary and sufficient conditions for the optimal solution are identified, and an algorithm that incurs a linear time cost is proposed. We have also conducted extensive simulations to validate the algorithm and to evaluate its performance.

Original languageEnglish
Article number5661768
Pages (from-to)1431-1444
Number of pages14
JournalIEEE Transactions on Computers
Issue number10
StatePublished - 15 Sep 2011


  • Algorithm/protocol design and analysis
  • information storage and retrieval
  • network problems


Dive into the research topics of 'Optimal storage placement for tree-structured networks with heterogeneous channel costs'. Together they form a unique fingerprint.

Cite this