An Approach to Improve the Performance of MTF Algorithm in List Accessing Problem

Pujarani Nanda¹ , Shiba Prasad Dash²

Section:Research Paper, Product Type: Journal-Paper
Vol.8 , Issue.4 , pp.32-36, Aug-2020

Online published on Aug 31, 2020

Copyright © Pujarani Nanda, Shiba Prasad Dash . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
A linear search problem having self organizing capacity is known as List Accessing Algorithm. In linear search the set of elements are accessed conclusively from the start of the list in a fixed size unsorted linear list. By performing exchanges we can reorganize the list. Because of reorganization of elements in the list, when an element is accessed the access cost for following elements is decreased with decreasing total access cost. General operation is performed on the data structure such as insertion, deletion and access that data structure is called as unsorted linear list. Present time, in literature Move to Front (MTF) algorithm is one of the leading online List Accessing algorithm. The current work aims to propose an exceptional algorithm to reduce the cost of accessing element. It should be faster to optimize the cost of searching. The algorithm is based on the perception of separate chaining method of Hash Function and MTF List Accessing Algorithm

Key-Words / Index Term :
List Accessing Problem, Data Structure, Move to Front Algorithm, Hash Technique

References :
[1] J. McCabe, ?On serial files with relocatable records,? Operations Research, Vol.12, pp.609-618, 1965.
[2] J. H. Hester and D. S. Hirschberg, ?Self ?organizing linear search,? ACM Computing Surveys, Vol.17, pp.295-312, 1985.
[3] N. Reingold,j. Westbrook, D.D, ? Sletor Randomize competitive algorithms for the list update problem,? Algorithmica , Vol.11, pp.15-32, 1994.
[4] Susanne Albers, ?A competitive analysis of the list update problem with lookahead,? Theoretical Computer Science, Vol.197, Issue 1?2, pp.95-109, 1998.
[5] R. Mohanty, S. Tripathy, ?An Improved Move-to-Front (IMTF) Off-line Algorithm for the List Accessing Problem,? International Journal of Advanced Computing and Communications, Vol.3, No.1, pp. 19-23, 2011.
[6] R. Mohanty, B. Sharma, and S. Tripathy, ?Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm,? International Journal of Computer Applications, Vol.22, pp.0975-8887, 2011.
[7] D. D. Sleator and R.E. Tarjan, ?Amortized efficiency of list update and paging rules,? Communications of the. ACM, Vol.28, No.2, pp. 202-208, 1985.
[8] D. Rout, "Experimental Analysis of Hybridized MTF- TRANS-FC (H-M-T-FC) Algorithm". International Journal of Research in Advent Technology , Vol.1, Issue 5, pp.85-91, 2013.
[9] J. L. Bentley and C. C. McGeoch, ?Amortized analyses of self organizing sequential search heuristics,? Communications of the ACM, Vol.28, pp. 404-411, 1985.
[10] A. Mishra, "A Study of Some List Accessing Algorithm And Novel Analytical Results," International Journal of Computer Trends and Technology,, Vol.4, Issue 6, pp.1641-1649, 2013.
[11] S. K. Panda, "A novel algorithm for list accessing problem," 2014 Seventh International Conference on Contemporary Computing, Noida, India, pp. 154-159, 2014.
[12] R. Bachrach, R. EI-Yaniv, and M. Reinstadtler, ?on the competitive theory and practice of online list accessing algorithms,? Algorithmica, Vol.32, No.2, pp. 201-245, 2002.
[13] R. Mohanty, S. P. Dash, B. Sharma , and S. Patel, ?Performance Evaluation Of A Proposed Variant of Frequency Count(VFC),? International Journal of System, Algorithms and Applications, Vol.2, pp.2277-2677, 2012.
[14] R. Rivest, ?On Self-Organizing sequential Search Heuristics,? IEEE Computer Society, pp.122-126, 1974.
[15] B. Samanta and S. P. Dash, ?A novel hybrid method to list accessing problem using BIT algorithm,? International Conference on Man and Machine Interface, Bhubaneswar, India, pp.1-5, 2015.
[16] S. Angelopoulos, R. Dorrigiv, and A. Lopez-ortiz, ?List Update With probabilistic Locality of Reference,? Information Processing Letters, Vol.112, No.13, pp.540-543, 2012.