Title :
Optimal Storage Placement for Tree-Structured Networks with Heterogeneous Channel Costs
Author :
Chiu, Ge-Ming ; Yen, Li-Hsing ; Chin, Tai-Lin
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan
Abstract :
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.
Keywords :
query processing; storage management; trees (mathematics); data query applications; heterogeneous channel costs; optimal storage placement; tree-structured networks; Algorithm design and analysis; Data communication; Data models; Database systems; Memory; Peer to peer computing; Wireless sensor networks; Algorithm/protocol design and analysis; information storage and retrieval; network problems.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2010.231