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

A New Proposed Cost Model for List Accessing Problem using Buffering

by Rakesh Mohanty, Seetaya Bhoi, 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, Seetaya Bhoi, Sasmita Tripathy
10.5120/2604-3631

Rakesh Mohanty, Seetaya Bhoi, Sasmita Tripathy . A New Proposed Cost Model for List Accessing Problem using Buffering. International Journal of Computer Applications. 22, 8 ( May 2011), 19-23. DOI=10.5120/2604-3631

@article{ 10.5120/2604-3631,
author = { Rakesh Mohanty, Seetaya Bhoi, Sasmita Tripathy },
title = { A New Proposed Cost Model for List Accessing Problem using Buffering },
journal = { International Journal of Computer Applications },
issue_date = { May 2011 },
volume = { 22 },
number = { 8 },
month = { May },
year = { 2011 },
issn = { 0975-8887 },
pages = { 19-23 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume22/number8/2604-3631/ },
doi = { 10.5120/2604-3631 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:08:51.493282+05:30
%A Rakesh Mohanty
%A Seetaya Bhoi
%A Sasmita Tripathy
%T A New Proposed Cost Model for List Accessing Problem using Buffering
%J International Journal of Computer Applications
%@ 0975-8887
%V 22
%N 8
%P 19-23
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

There are many existing well known cost models for the list accessing problem. The standard cost model developed by Sleator and Tarjan is most widely used. In this paper, we have made a comprehensive study of the existing cost models and proposed a new cost model for the list accessing problem. In our proposed cost model, for calculating the processing cost of request sequence using a singly linked list, we consider the access cost, matching cost and replacement cost. The cost of processing a request sequence is the sum of access cost, matching cost and replacement cost. We have proposed a novel method for processing the request sequence which does not consider the rearrangement of the list and uses the concept of buffering, matching, look ahead and flag bit.

References
  1. J. McCabe , “On serial files with relocatable records”,Operations Research, vol. 12. pp 609-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 selforganising 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,” CACM, 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.
Index Terms

Computer Science
Information Sciences

Keywords

Data Structure Linear List List Accessing Cost model buffering look ahead matching