Pseudo-LRU

Pseudo-LRU or PLRU is a family of cache algorithms which improve on the performance of the Least Recently Used (LRU) algorithm by replacing values using approximate measures of age rather than maintaining the exact age of every value in the cache.

PLRU usually refers to two cache replacement algorithms: tree-PLRU and bit-PLRU.

The algorithm works as follows: consider a binary search tree for the items in question.

To find a pseudo-LRU element, traverse the tree according to the values of the flags.

To update the tree with an access to an item N, traverse the tree to find N and, during the traversal, set the node flags to denote the direction that is opposite to the direction taken.