The authors develop and evaluate a number of storage reclamation algorithms for client-server persistent object stores. Experience with a detailed simulation and a prototype implementation in the Exodus storage manager shows that one of the proposed algorithms, the Incremental Partitioned Collector, is complete, maintains transaction semantics, and can be run incrementally and concurrently with client applications. Furthermore, it can significantly improve subsequent system performance by reclustering data, rendering it attractive even for systems that choose not to support automatic storage reclamation.>