A Study of Some List Accessing Algorithm And Novel Analytical Results
 | International Journal of Computer Trends and Technology (IJCTT) |  |
| © - June Issue 2013 by IJCTT Journal | ||
| Volume-4 Issue-6 | ||
| Year of Publication : 2013 | ||
| Authors :Ms. Aishwarya Mishra |
Ms. Aishwarya Mishra"A Study of Some List Accessing Algorithm And Novel Analytical Results"International Journal of Computer Trends and Technology (IJCTT),V4(6):1641-1649 June Issue 2013 .ISSN 2231-2803.www.ijcttjournal.org. Published by Seventh Sense Research Group.
Abstract: -List Accessing Problem is a sound deliberate research problem in the circumstance of linear search. The entire problem of efficiently reorganizing and accessing the elements of the list for obtaining optimal cost is known as list accessing problem. 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. The list accessing problem is of significant practical interest in the context of self organizing data structure. Self organizing data structures reorganize their structure while processing a sequence of operations. The purpose of this reorganization is to pledge (guarantee) the competence (efficiency) of prospect operation and improve the performance of this data structure. An algorithm which proficiently reorganizes the list to diminish the access cost is a List Accessing Algorithm. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. List accessing techniques have been comprehensively used in practices when storing and maintaining diminutive dictionaries. One of the significant applications of list accessing problem is data compression. When a sender wants to send a compressed message to a receiver, both the sender and receiver maintains a list containing all the words in the dictionary. Here, initially both lists are in the same order and they both agree upon some list accessing algorithm. When the sender wants to send a word, one sends the current position of the word in the list, which is encoded using some variable length prefix encoding. Move-to-Front algorithm has been proved to be the preeminent performing list accessing online algorithm till date in the literature. In this paper, a comprehensive study of list accessing problem and some well known deterministic list accessing algorithms have been studied along with some novel theoretical and analytical results for different permutation of request sequences towards their access cost associated with both MTF and IMTF algorithms.
References-
[1] McCabe J. (1965). On-line serial files with reloadable records. Operation Research. vol.12. pp.609-618.
[2] Mohanty R and Narayanaswamy, N.S. (2009). Algorithms for Self-Organizing Sequential Search - A Survey. Electronic Colloquium on Computational Complexity. pp.1-9.
[3] Bachrach Ran and El-Yaniv Ran. (1997). Online List Accessing Algorithms and their Applications: Recent Empirical Evidence, In: SODA’97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics. Pp. 53–62. (www. http://dl.acm.org/) (Accessed on 30.4.11)
[4] Albers S, (1998), Improved Randomized On-Line Algorithms for the List Update Problem. SIAM Journal on Computing, 27 (3), Pp.682-693. (http://dl.acm.org/). (Accessed on 1.3.12)
[5] Albers S and Westbrook J (1998), Self-Organizing Data Structures. CT06520-2158 and AT&TLabs.Pp.1-39.(http://www2.informatik.hu-berlin.de/~albers/papers/ chapter. pdf) (Accessed on 1.3.12)
[6] Bentley J L and McGeoch C C. (1985), Amortized analysis of self-organizing sequential search heuristics.Communications of the ACM. 28 (4). Pp.404-411. (http://cacm.acm.org/) (Accessed on 1.3.12)
[7] Manasse M S, McGeoch L. A. & Sleator D D (1988), Competitive Algorithms for on- line Problems. In .STOC, 88 Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. ACM; New York. Pp.322-332 (http://dl.acm.org/) (Accessed on 2.3.12)
[8] Reingold N Westbrook J. (1996). Off-line Algorithms for the List Update Problem. Science Direct. 60(2), Pp.75-80.
[9] Ambuhi Christoph, Gartner Bernd and Bernhard von Stengel (2000). Optimal Projective Algorithms for the List Update Problem. ICALP. Proceedings of the 27th International Colloquium on ACM Digital Library. Vol 1853. Automata Languages and Programming. Pp.305-316. (http://springerlink.com/) (Accessed on 3.3.12)
[10] Albers S. (1994). A Competitive Analysis of the List Update Problem with Look ahead, Springer Lecture Notes in Computer Science, v..841. Mathematical Foundations of Computer Science. Pp. 199-210. (http://www.springerlink.com/) (Accessed on 3.3.12).
Keywords — List Accessing Problem, List Accessing Cost Models, List Accessing Algorithms, MTF and IMTF Algorithms.