@InProceedings{Riv74d, replaced-by = { Riv76a }, author = { Ronald L. Rivest }, title = { On self-organizing sequential search heuristics }, pages = { 122--126 }, doi = { 10.1109/SWAT.1974.18 }, booktitle = { IEEE Conference Record of 15th Annual Symposium on Switching and Automata Theory }, issn = { 0272-5428 }, publisher = { IEEE }, date = { 1974 }, OPTorganization = { IEEE }, OPTyear = { 1974 }, OPTmonth = { October 14--16, }, eventtitle = { SWAT '74 }, eventdate = { 1974-10-14/1974-10-16 }, venue = { New Orleans }, editor = { Ronald Book }, keywords = { searching, self-organizing, list-processing, heuristics }, abstract = { We examine a class of heuristics for maintaining a sequential list in approximately optimal order with respect to the average time required to search for a specified element, assuming that we search for each element with a fixed probability independent of previous searches performed. The ``move to front'' and ``transposition'' heuristics are shown to be optimal to within a constant factor, and the transposition rule is shown to be the more efficient of the two. Empirical evidence suggests that transposition is in fact optimal for any distribution of search probabilities. }, }