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

Authors

  • Pujarani Nanda Dept. of Computer Science & Engineering, Biju Patnaik University of Technology, Rourkela, Odisha, India
  • Shiba Prasad Dash Dept. of Computer Science & Engineering, Biju Patnaik University of Technology, Rourkela, Odisha, India

Keywords:

List Accessing Problem, Data Structure, Move to Front Algorithm, Hash Technique

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

 

References

J. McCabe, ?On serial files with relocatable records,? Operations Research, Vol.12, pp.609-618, 1965.

J. H. Hester and D. S. Hirschberg, ?Self ?organizing linear search,? ACM Computing Surveys, Vol.17, pp.295-312, 1985.

N. Reingold,j. Westbrook, D.D, ? Sletor Randomize competitive algorithms for the list update problem,? Algorithmica , Vol.11, pp.15-32, 1994.

Susanne Albers, ?A competitive analysis of the list update problem with lookahead,? Theoretical Computer Science, Vol.197, Issue 1?2, pp.95-109, 1998.

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.

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.

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.

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.

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.

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.

S. K. Panda, "A novel algorithm for list accessing problem," 2014 Seventh International Conference on Contemporary Computing, Noida, India, pp. 154-159, 2014.

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.

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.

R. Rivest, ?On Self-Organizing sequential Search Heuristics,? IEEE Computer Society, pp.122-126, 1974.

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.

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.

Downloads

Published

2020-08-31

How to Cite

[1]
P. Nanda and S. P. Dash, “An Approach to Improve the Performance of MTF Algorithm in List Accessing Problem”, Int. J. Sci. Res. Comp. Sci. Eng., vol. 8, no. 4, pp. 32–36, Aug. 2020.

Issue

Vol. 8 No. 4 (2020): August

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.