Counter Stacks and the Elusive Working Set

Counter stacks are a compact and effective data structure for summarizing access patterns in memory and storage workloads. They are a stream abstraction that efficiently characterizes the uniqueness of an access stream over time, and are sufficiently low overhead as to allow both new approaches to online decision-making (such as replacement or prefetching policies) and new applications of lightweight trace transmission and archiving.