TinyLFU

[ben-manes]

You would probably find TinyLFU an interesting approach, as it focuses on admission rather than eviction. This is done by using a popularity sketch to probabilistically estimate the frequency of the new arrival compared to the victim, choosing whichever has the highest frequency. You may also find this project's simulator a useful resource, as LIRS is difficult to implement correctly due to subtleties in the paper.

[DmitryBespalov]

Thanks for sharing. TinyLFU looks interesting, indeed. I had Bloom filter in mind, too. Let's see if I'll come close to implementing those :)