SCADDAR: An Efficient Randomized Technique to Reorganize Continuous Media Blocks Ashish Goel, Cyrus Shahabi, Didi Shu-Yuen Yao, and Roger Zimmermann   View Paper (PDF)   Return to Session 12: Database Access Structures and Techniques Abstract Scalable storage architectures allow for the addition of disks to increase storage capacity and/or bandwidth. In its general form, disk scaling also refers to disk removals when either capacity needs to be conserved or old disk drives are retired. Assuming random placement of blocks on multiple nodes of a continuous media server, our optimization objective is to redistribute a minimum number of media blocks after disk scaling. This objective should be met under two restrictions. First, uniform distribution and hence a balanced load should be ensured after redistribution. Second, the redistributed blocks should be retrieved at the normal mode of operation in one disk access and through low complexity computation. We propose a technique that meets the objective, while we prove that it also satisfies both restrictions. The SCADDAR approach is based on using a series of REMAP functions which can derive the location of a new block using only its original location as a basis. DiSC'03 © 2003 Association for Computing Machinery