Skip to content

Self organising linked list : Notes.



Self organising linked list is a very simple idea to improve the linear
non-improving access times of linked lists. The basic assumption is that
the data being accessed will be accessed again and hence it would be
beneficial to improve the access times by moving the data closer to the
head of the list.
There are various strategies to implement this:
1) Move To Front(MTF) : MTF takes a drastic view of the data and moves
every data to the front of the list. It treats every access with
significance and assumes that the data will be surely accessed in the near
future. This works well for databases where in 20% of the data is accessed
80% of the times. But if the access is of truely random nature then this
will only makes the access that much longer.
2) Count method : Maintain a count of the number of times a node/data is
accessed and then sort the list on that basis. This is a more deterministic
as the order is based on data and not based on too drastic view like MTF.
But this requires extra bookkeeping and also requires the list to be sorted
in proper order.
3) Tranpose method : I call it the “bubble-up” method. In this method the
on access the data / node is swapped with its previous node, moving it one
step near to the head of the list. This strategy is cautious about the
importance being placed in a node access. And the node has to be accessed
quite some time to make its way to the top. The node bubble-ups only after
frequent access. The problem here is that truly important data will take
quite some time before it reaches the head , thus robbing off of any
improvements gained through self-organising lists.

Applications:
Databases
Compiler symbol tables.
Improving cache access times.

Link : http://en.wikipedia.org/wiki/Self-organizing_list




Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*