We study the performance of the Timestamp(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 sue of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases uning TS(0) 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(0) leads in fact to improved compression.
展开▼
