1. A method for evaluating interaction between a cache in a computer system and at least one entity, where each entity submits a stream of references, each reference corresponding to a location identifier corresponding to data storage locations in a storage system, the method comprising, for each of at least one of the entities, at a sampling rate, spatially sampling the stream of references by: selecting a threshold value; computing a hash value for each reference; comparing the hash value for each reference in the stream with the threshold value and selecting only those references whose hash value meets a selection criterion; maintaining a sample set data structure having entries corresponding to the sampled references whose hash values satisfy the selection criterion; compiling cache utility values for the sampled references whose hash values satisfy the selection criterion; computing a first statistic of the location identifiers that meet the selection criterion over the entire stream of references; computing a second statistic for the sampled references whose hash values satisfied the selection criterion; and computing and applying to the compiled cache utility values a correction as a function of the difference between the first and second statistics.