Dynamic Ordering

Move-To-Front Heuristic

In a list: Always insert at the front. Upon a successful search , move the accessed item to the front of the list.

Transpose Heuristic

Upon successful search, swap the accessed item with the item immediately preceding it.

Performance

• Transpose does not adapt quickly to changing access patterns.
• MTF works well in practice
• Can show: MTF is “2-competitive”: No more than twice as bad as the optimal static ordering