No CrossRef data available.
Article contents
A Transposition Rule Analysis Based on a Particle Process
Published online by Cambridge University Press: 14 July 2016
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
A linear list is a collection of items that can be accessed sequentially. The cost of a request is the number of items that need to be examined before the desired item is located, i.e. the distance of the requested item from the beginning of the list. The transposition rule is one of the algorithms designed to reduce the search cost by organizing the list. In particular, upon a request for a given item, the item is transposed with the preceding one. We develop a new approach for analyzing the algorithm, based on a coupling to a certain constrained asymmetric exclusion process. This allows us to establish an asymptotic optimality of the rule for two families of request distributions.
MSC classification
Information
- Type
- Research Papers
- Information
- Copyright
- © Applied Probability Trust 2005
Footnotes
∗∗
Current address: Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA. Email address: petar@eecs.umich.edu
References
Anderson, E., Nash, P. and Weber, R. (1982). A counterexample to a conjecture in optimal list ordering. J. Appl. Prob.
19, 730–732.CrossRefGoogle Scholar
Bachrach, R. and El-Yaniv, R. (1997). Online list accessing algorithms and their applications: Recent empirical evidence. In Proc. Eighth Annual Symp. Discrete Algorithms (New Orleans, LA), ACM, New York, pp. 53–62.Google Scholar
Barrera, J. and Paroissin, C. (2004). On the distribution of the search cost for the move-to-front rule with random weights. J. Appl. Prob.
41, 250–262.CrossRefGoogle Scholar
Fill, J. (1996). An exact formula for the move-to-front rule for self-organizing lists. J. Theoret. Prob.
9, 113–159.CrossRefGoogle Scholar
Fill, J. (1996). Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theoret. Comput. Sci.
164, 185–206.CrossRefGoogle Scholar
Fill, J. and Holst, L. (1996). On the distribution of search cost for the move-to-front rule. Random Structures Algorithms
8, 179–186.3.0.CO;2-V>CrossRefGoogle Scholar
Flajolet, P., Gardy, D. and Thimonier, L. (1992). Birthday paradox, coupon collector, caching algorithms and self-organizing search. Discrete Appl. Math.
39, 207–229.CrossRefGoogle Scholar
Hester, J. and Hirchberg, D. (1985). Self-organizing linear search. Comput. Surveys
17, 295–311.CrossRefGoogle Scholar
Jelenković, P. (1999). Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. Ann. Appl. Prob.
9, 430–464.CrossRefGoogle Scholar
Kan, Y. and Ross, S. (1980). Optimal list order under partial memory constraints. J. Appl. Prob.
17, 1004–1015.CrossRefGoogle Scholar
Knuth, D. (1998). The Art of Computer Programming, Vol. 3, 2nd edn. Addison-Wesley, Reading, MA.Google Scholar
Lam, K., Leung, M. Y. and Siu, M. K. (1984). Self-organizing files with dependent accesses. J. Appl. Prob.
21, 343–359.CrossRefGoogle Scholar
Rivest, R. (1976). On self-organizing sequential search heuristics. Commun. ACM
19, 63–67.CrossRefGoogle Scholar
Sleator, D. and Tarjan, R. (1985). Amortized efficiency of list update and paging rules. Commun. ACM
28, 202–208.CrossRefGoogle Scholar
Tenenbaum, A. and Nemes, R. (1982). Two spectra of self-organizing sequential search algorithms. SIAM J. Comput.
11, 557–566.CrossRefGoogle Scholar
You have
Access
- 1
- Cited by