We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm

by Rakesh Mohanty, Burle Sharma, Sasmita Tripathy
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 22 - Number 8
Year of Publication: 2011
Authors: Rakesh Mohanty, Burle Sharma, Sasmita Tripathy
10.5120/2601-3627

Rakesh Mohanty, Burle Sharma, Sasmita Tripathy . Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm. International Journal of Computer Applications. 22, 8 ( May 2011), 35-40. DOI=10.5120/2601-3627

@article{ 10.5120/2601-3627,
author = { Rakesh Mohanty, Burle Sharma, Sasmita Tripathy },
title = { Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { May 2011 },
volume = { 22 },
number = { 8 },
month = { May },
year = { 2011 },
issn = { 0975-8887 },
pages = { 35-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume22/number8/2601-3627/ },
doi = { 10.5120/2601-3627 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:08:53.494083+05:30
%A Rakesh Mohanty
%A Burle Sharma
%A Sasmita Tripathy
%T Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 22
%N 8
%P 35-40
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

List Accessing Problem is a well studied research problem in the context of linear search. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. Move-To-Front algorithm has been proved to be the best performing list accessing online algorithm till date in the literature. Characterization of the input request sequences corresponding to practical real life situations is a big challenge for the list accessing problem. As far as our knowledge is concerned, no characterization for the request sequences has been done in the literature till date for the list accessing problem. In this paper, we have characterized the request sequences for the list accessing problem based on several factors such as size of the list, size of the request sequence, ordering of elements and frequency of occurrence of elements in the request sequence. We have made a comprehensive study of MTF list accessing algorithm and obtained new theoretical results for our characterized special class of request sequences. Our characterization will open up a new direction of research for empirical analysis of list accessing algorithms for real life inputs.

References
  1. J. McCabe , “On serial files with relocatable records”,Operations Research, vol. 12.pp609-618, 1965.
  2. J. L. Bentley and C. C. McGeoch, “Amortized analysis of self organizing sequential search heuristics,” CACM, vol. 28, pp. 404-411, 1985.
  3. G. H. Gonnet, J.I. Munro, and H. Suwanda, “Towards self-organizing linear search.”IEEE, pp.169-174 , 1979.
  4. R. Rivest, “On self organizing sequential search heuristics,” Communication of the ACM, vol 10. 19, 63- 67,1976.
  5. G.H. Gonet, J.I. Munro, and H. Suwanda, “Towards self organising linear search.” SIAM journal of computing, vol. 10, no. 3,pp. 613-637, 1981.
  6. J. H. Hester and D. S. Hirschberg, “Self –organizing linear search,” vol. 17, pp. 295-312, 1985.
  7. D. D. Sleator and R.E. Tarjan, “Amortized efficiency of list update and paging rules.” Common. ACM, vol. 28, no. 2, 202-208, 1985.
  8. A. Borodin, N. Linial, and M. Saks, “An optimal online algorithm for material task systems,” JACM, vol. 52, pp. 46-52, 1985.
  9. 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.
  10. S Angelopoulos, R Dorrigiv, A López-Ortiz - “List update with locality of reference: MTF outperforms all other algorithms,TR CS-2006-46, School of Computer Science, University of Waterloo, November 2006.
Index Terms

Computer Science
Information Sciences

Keywords

List Request Sequence Linear Search Move-To-Front Cost Model