In a space incremental garbage collector, remembered set information for a region is stored in a set of fixed-size data structures, each of which has a representation of the information and a level of precision that differs from other data structures in the set. Remembered set information for each other region is placed in a data structure based on the density of inter-region references between the region and the other region. The remembered set information for the other region is moved from one data structure to another data structure when the density of inter-region references between the region and the other changes. Some of the data structures use bit arrays to store the information and these arrays can be combined with bit arrays produced by the collector to facilitate the identification and removal of stale remembered set entries.