Splaying for Compression: An Experimental Study

In this paper, we propose novel randomized versions of the splay trees. We have evaluated the practical performance of these structures in comparison with the original version of splay trees and with their loglogn-competitive variations, in the application field of compression. In order to evaluate performance, we utilize plain splay trees, their loglog n-competitive variations, and our proposed randomized version with the Chain Splay technique to compress data. It is observed in practice, that the compression achieved in the case of the loglog n-competitive technique is, as intuitively expected, more efficient than the one of the plain splay trees.