Characterization and Performance Evaluation of Request Sequence for Move-To-Front Algorithm

摘要

List accessing problem is the problem of efficiently reorganizing and accessing the element of the list for obtaining optimal cost. So in list accessing problem a sorted list and an unsorted request sequence is given as input and the main objective is to reduce access cost of the elements. In this paper, characterizing the request sequences based on locality of references and look ahead property. Also characterization is done based on size of list, size of request sequences, ordering of elements, frequencies occurrence of elements and sequence of elements of the list. Based on our characterization a new cost model is developed for different inputs by using Move-To-Front list accessing algorithm. Till now Move-To-Front algorithm has been proved as best performing algorithm where the elements are moving towards front of list after accessing.