# GreedyDual-Size / GreedyDual-Size-Frequency (GDS/GDSF)
## Goal
Make eviction consider **object size** and/or **miss cost** (common in web/CDN caches), not just request count.
## Core Idea
Assign each entry a key `H` (priority). Evict the smallest `H`.
Common scoring shape (varies by variant):
- `H = (cost * freq) / size + L`
Where:
- `cost`: retrieval cost (latency, backend load, $ cost)
- `freq`: access frequency (for GDSF-like variants)
- `size`: bytes
- `L`: an “inflation” value updated to the `H` of the last evicted item (prevents tiny objects from dominating forever)
## Core Data Structures
Typical implementation:
- `HashMap<K, Entry>` for lookup
- min-heap or ordered map keyed by `H` for victim selection
Implementation choices:
- Exact heap: O(log n) per access/update
- Approximate: bucket priorities or periodic recomputation
## When It Matters
Use when:
- object sizes vary a lot and you care about byte hit rate
- misses have heterogeneous cost
## References
- Cao, Irani (1997): “GreedyDual-Size: An algorithm for web caching”.
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies