2014 | OriginalPaper | Chapter
An Experimental Study of a Novel Move-to-Front-or-Middle (MFM) List Update Algorithm
Authors : Rakesh Mohanty, Tirtharaj Dash, Biswadeep Khan, Shiba Prasad Dash
Published in: Applied Algorithms
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
List Update Problem (LUP) or List Accessing Problem (LAP) is a well studied research problem in the area of online algorithms [5] and self organizing data structures [2] since the pioneering work of McCabe [7]. In this problem, the inputs are an unsorted list of distinct items and a sequence of requests where each request is an access operation on an item of the list. The objective of a list update algorithm is to reorganize the list after each access and minimize the total access and reorganization cost, while processing a request sequence of finite size on a fixed size list. LUP is one of the general memory accessing problem which was studied by Sleator and Tarjan [14] for the competitive analysis of online algorithms in their seminal paper. As offline list update has been proved to be NP-hard [3], there is no known trivial solution to the problem. Move-To-Front(MTF) has been proved to be the best online algorithm [2] in the literature. In this paper, we have proposed a novel variant of MTF algorithm, which we popularly call as Move-to-Front-or-Middle(MFM). We have performed an empirical study of MFM algorithm and comparative performance analysis with MTF algorithm using two dataset such as Calgary Corpus and Canterbury Corpus. Our experimental results show that MFM outperforms MTF for all request sequences in both the data set.