Behavioral insights into compression: a study of Move-to-Front-or-Middle deterministic online algorithm through sequence classification and characterization

Since the list update problem was applied to data compression as an effective encoding technique, numerous deterministic algorithms have been studied and analyzed. A powerful strategy, Move-to-Front (MTF), involves moving an accessed item to the front of the list immediately. Theoretical analysis has demonstrated MTF’s potential, showing it to be 2-competitive through competitive analysis. This success has inspired researchers to develop various intriguing MTF variants and assess their performance both theoretically and experimentally. One such variant, Move-to-Front-or-Middle (MFM), has been experimentally shown that MFM performed better than the classic MTF on Calgary and Cantebury Datasets. However, the experimental performance alone does not provide sufficient insight into the internal behavior of the algorithm or explain why its performance surpasses MTF on certain datasets. Therefore, in this paper, we conduct a detailed behavioral study of MFM through sequence classification and characterization to gain deeper understanding of the algorithm and aims to reconcile the disparity between theoretical and experimental outcomes. This paper also by classifying and characterizing MFM’s performance across various request sequences, considering both the presence and absence of locality of reference.