Average Case Analyses of List Update Algorithms, with Applications to Data Compression

TitleAverage Case Analyses of List Update Algorithms, with Applications to Data Compression
Publication TypeTechnical Report
Year of Publication1995
AuthorsAlbers, S., & Mitzenmacher M.
Other Numbers979
Abstract

We study the performance of the Timestamp(0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such sources, and determine performance ratios for TS(0) 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(0) in place of Move-to-front in schemes that use the latter should improve compression. Tests using implementations on a standard corpus of test documents demonstrate that TS(0) leads to improved compression.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-039.pdf
Bibliographic Notes

ICSI Technical Report TR-95-039

Abbreviated Authors

S. Albers and M. Mitzenmacher

ICSI Publication Type

Technical Report