Web proxy caching provides an effective way to reduce access latency and bandwidth consumption, and thus improve performance of the World Wide Web. Due to the simplicity of incorporating various types of data into the Web, non-negligible access for large multimedia data is observed. Large multimedia data transfer, requiring a long-lived connection with consecutive data transmissions, often fails over wide area networks. Repetitive attempts to fetch large objects through proxy caches would waste network resources with no success guaranteed. In this paper, we propose on-demand cumulative prefetching to enhance proxy caches for better data availability of large multimedia files. Our analysis shows that on-demand cumulative prefetching can be performed within a few trials with minimal additional bandwidth requirement. The experimental results demonstrate that the proposed scheme substantially reduces error rate and increases byte hit rate for large multimedia data. (C) 2000 Published by Elsevier Science B.V. All rights reserved.