Self-organizing Doubly-linked Lists. Valiveti, R. S. & Oommen, B. J. 14(6):88–114.
Paper doi abstract bibtex In this paper, we study the problem of maintaining a doubly-linked list (DLL) in approximately optimal order, with respect to the mean search time. We study two types of DLL reorganization strategies. Move-To-End (MTE) [12] and SWAP [14] are two memoryless DLL heuristics obtained from natural extensions of the well-known singly-linked-list (SLL) heuristics, move-to-front and transposition, respectively. We first derive a general sufficient condition which permits comparison of any two DLL heuristics. We use this condition as a guideline to identify families of access distributions for which SWAP yields a lower expected cost than the MTE. We have also presented an absorbing DLL heuristic. The strategy requires one additional memory location and is analogous to the scheme presented in [15]. The reorganization is achieved by moving each element exactly once to its final position in the reorganized list. The scheme is stochastically absorbing and it is shown to be optimal for a restricted family of distributions. Thus, for these distributions, the probability of the scheme converging to the optimal list order can be made as close to unity as desired.
@Article{ valiveti_self-organizing_1993,
title = {Self-organizing Doubly-linked Lists},
volume = {14},
issn = {0196-6774},
url = {http://www.sciencedirect.com/science/article/pii/S0196677483710059},
doi = {https://doi.org/10.1006/jagm.1993.1005},
abstract = {In this paper, we study the problem of maintaining a
doubly-linked list ({DLL}) in approximately optimal order,
with respect to the mean search time. We study two types of
{DLL} reorganization strategies. Move-To-End ({MTE}) [12]
and {SWAP} [14] are two memoryless {DLL} heuristics
obtained from natural extensions of the well-known
singly-linked-list ({SLL}) heuristics, move-to-front and
transposition, respectively. We first derive a general
sufficient condition which permits comparison of any two
{DLL} heuristics. We use this condition as a guideline to
identify families of access distributions for which {SWAP}
yields a lower expected cost than the {MTE}. We have also
presented an absorbing {DLL} heuristic. The strategy
requires one additional memory location and is analogous to
the scheme presented in [15]. The reorganization is
achieved by moving each element exactly once to its final
position in the reorganized list. The scheme is
stochastically absorbing and it is shown to be optimal for
a restricted family of distributions. Thus, for these
distributions, the probability of the scheme converging to
the optimal list order can be made as close to unity as
desired.},
pages = {88--114},
number = {6},
journaltitle = {Journal of Algorithms,},
author = {Valiveti, R. S. and Oommen, B. J.},
date = {1993}
}
Downloads: 0
{"_id":"2vzC8vnwpsbWQipNp","bibbaseid":"valiveti-oommen-selforganizingdoublylinkedlists","author_short":["Valiveti, R. S.","Oommen, B. J."],"bibdata":{"bibtype":"article","type":"article","title":"Self-organizing Doubly-linked Lists","volume":"14","issn":"0196-6774","url":"http://www.sciencedirect.com/science/article/pii/S0196677483710059","doi":"https://doi.org/10.1006/jagm.1993.1005","abstract":"In this paper, we study the problem of maintaining a doubly-linked list (DLL) in approximately optimal order, with respect to the mean search time. We study two types of DLL reorganization strategies. Move-To-End (MTE) [12] and SWAP [14] are two memoryless DLL heuristics obtained from natural extensions of the well-known singly-linked-list (SLL) heuristics, move-to-front and transposition, respectively. We first derive a general sufficient condition which permits comparison of any two DLL heuristics. We use this condition as a guideline to identify families of access distributions for which SWAP yields a lower expected cost than the MTE. We have also presented an absorbing DLL heuristic. The strategy requires one additional memory location and is analogous to the scheme presented in [15]. The reorganization is achieved by moving each element exactly once to its final position in the reorganized list. The scheme is stochastically absorbing and it is shown to be optimal for a restricted family of distributions. Thus, for these distributions, the probability of the scheme converging to the optimal list order can be made as close to unity as desired.","pages":"88–114","number":"6","journaltitle":"Journal of Algorithms,","author":[{"propositions":[],"lastnames":["Valiveti"],"firstnames":["R.","S."],"suffixes":[]},{"propositions":[],"lastnames":["Oommen"],"firstnames":["B.","J."],"suffixes":[]}],"date":"1993","bibtex":"@Article{\t valiveti_self-organizing_1993,\n title\t\t= {Self-organizing Doubly-linked Lists},\n volume\t= {14},\n issn\t\t= {0196-6774},\n url\t\t= {http://www.sciencedirect.com/science/article/pii/S0196677483710059},\n doi\t\t= {https://doi.org/10.1006/jagm.1993.1005},\n abstract\t= {In this paper, we study the problem of maintaining a\n\t\t doubly-linked list ({DLL}) in approximately optimal order,\n\t\t with respect to the mean search time. We study two types of\n\t\t {DLL} reorganization strategies. Move-To-End ({MTE}) [12]\n\t\t and {SWAP} [14] are two memoryless {DLL} heuristics\n\t\t obtained from natural extensions of the well-known\n\t\t singly-linked-list ({SLL}) heuristics, move-to-front and\n\t\t transposition, respectively. We first derive a general\n\t\t sufficient condition which permits comparison of any two\n\t\t {DLL} heuristics. We use this condition as a guideline to\n\t\t identify families of access distributions for which {SWAP}\n\t\t yields a lower expected cost than the {MTE}. We have also\n\t\t presented an absorbing {DLL} heuristic. The strategy\n\t\t requires one additional memory location and is analogous to\n\t\t the scheme presented in [15]. The reorganization is\n\t\t achieved by moving each element exactly once to its final\n\t\t position in the reorganized list. The scheme is\n\t\t stochastically absorbing and it is shown to be optimal for\n\t\t a restricted family of distributions. Thus, for these\n\t\t distributions, the probability of the scheme converging to\n\t\t the optimal list order can be made as close to unity as\n\t\t desired.},\n pages\t\t= {88--114},\n number\t= {6},\n journaltitle\t= {Journal of Algorithms,},\n author\t= {Valiveti, R. S. and Oommen, B. J.},\n date\t\t= {1993}\n}\n\n","author_short":["Valiveti, R. S.","Oommen, B. J."],"key":"valiveti_self-organizing_1993","id":"valiveti_self-organizing_1993","bibbaseid":"valiveti-oommen-selforganizingdoublylinkedlists","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0196677483710059"},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://raw.githubusercontent.com/rsvaliveti/pubs/main/papers.bib","dataSources":["Ya3KsBG9WEWneaMEw"],"keywords":[],"search_terms":["self","organizing","doubly","linked","lists","valiveti","oommen"],"title":"Self-organizing Doubly-linked Lists","year":null}