TY - GEN
T1 - Average case analyses of list update algorithms, with applications to data compression
AU - Albers, Susanne
AU - Mitzenmacher, Michael
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - We study the performance of the Timestamp(O) (TS(O)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(O) is better than Move-to-front on such sources, and determine performance ratios for TS(O) against the optimal offline and static adversaries in this situation. Previous work on such sources compared online algorithms only to static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(O) in place of Move-to-front in schemes that use the latter should improve compression. Tests on a standard corpus of documents demonstrate that TS(O) leads in fact to improved compression.
AB - We study the performance of the Timestamp(O) (TS(O)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(O) is better than Move-to-front on such sources, and determine performance ratios for TS(O) against the optimal offline and static adversaries in this situation. Previous work on such sources compared online algorithms only to static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(O) in place of Move-to-front in schemes that use the latter should improve compression. Tests on a standard corpus of documents demonstrate that TS(O) leads in fact to improved compression.
UR - http://www.scopus.com/inward/record.url?scp=84877947090&partnerID=8YFLogxK
U2 - 10.1007/3-540-61440-0_155
DO - 10.1007/3-540-61440-0_155
M3 - Conference contribution
AN - SCOPUS:84877947090
SN - 3540614400
SN - 9783540614401
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 514
EP - 525
BT - Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
A2 - Meyer auf der Heide, Friedhelm
A2 - Monien, Burkhard
PB - Springer Verlag
T2 - 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
Y2 - 8 July 1996 through 12 July 1996
ER -