Publication Details
Title: Average Case Analyses of List Update Algorithms, with Applications to Data Compression
Author: S. Albers and M. Mitzenmacher
Group: ICSI Technical Reports
Date: August 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-95-039
Bibliographic Reference:
S. Albers and M. Mitzenmacher. Average Case Analyses of List Update Algorithms, with Applications to Data Compression. ICSI Technical Report TR-95-039, August 1995
Author: S. Albers and M. Mitzenmacher
Group: ICSI Technical Reports
Date: August 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-95-039
Bibliographic Reference:
S. Albers and M. Mitzenmacher. Average Case Analyses of List Update Algorithms, with Applications to Data Compression. ICSI Technical Report TR-95-039, August 1995