IUP Publications Online
Home About IUP Magazines Journals Books Archives
     
Recommend    |    Subscriber Services    |    Feedback    |     Subscribe Online
 
The IUP Journal of Information Technology
A Move-To-Head-or-Tail (MTHT) Algorithm for the List Accessing Problem†
:
:
:
:
:
:
:
:
:
 
 
 
 
 
 
 

Move-To-Front (MTF) algorithm has been proved to be the best performing online list accessing algorithm for the List Accessing Problem (LAP) till date. It was shown experimentally in 2010 that an Improved-Move-To-Front (IMTF) algorithm performs better than MTF algorithm. A modified linked list data structure is used to define a new cost model for list accessing algorithm. Using the new cost model, a Move-To-Head-or-Tail (MTHT) algorithm is proposed for the LAP. An experiment is being conducted by generating two different types of dataset and MTF, IMTF and MTHT algorithms were implemented with the datasets. The experimental analysis shows that the performance of the proposed MTHT algorithm is better than MTF and IMTF algorithms.

 
 

List Accessing Problem(LAP) is a self-organizing linear search, where a list accessing algorithm accesses a sequence of requested elements on a fixed size of unsorted linear list. After accessing the element, the list is reorganized in such a way that the frequently accessed elements are moved towards front of it. For each operation, the algorithm incurs some cost according to a cost model. The full cost model defined by Sleator and Tarjan (1985) is considered as the standard cost model for LAP. In this cost model, for accessing the ith element in the list, the access cost is i. Immediately after an access, the accessed element can be moved any distance forward in the list without paying any cost. These exchanges cost nothing and are called free exchanges. For any exchange between two adjacent elements in the list, the cost is 1. These exchanges are called paid exchanges. Hence, the total access cost is the sum of the exchange cost and the access cost. The goal is to efficiently reorganize the list by performing exchanges after accessing each element of the request sequence so that the access cost for subsequent requested elements is reduced, thereby reducing the total access cost. The list accessing algorithms can be classified as online and offline on the basis of arrival of request element in the request sequence. In online algorithms, the request sequence is partially known, i.e., the current requests are known and future requests come on one by one in a serial fashion. In offline algorithms, the whole request sequence is known in advance. In reality, the requests come in blocks in possibly variable size instead of one after another. When a request is generated faster than it is processed by the LAP, then it is to be expected that some requests may be waiting in the line to be processed by an online algorithm and that concept is known as lookahead.

 
 

Information Technology Journal, Lookahead, Data structure, List accessing, Linear search, Linked list, Experimental analysis.