Taking into account access patterns irregularity when compressing address traces

In this paper we propose an approach for compressing address traces with access patterns irregularity. This approach is based on a cluster analysis of the trace. This analysis do not rely on any locality assumption and thus is suitable in case where space locality is poor due to access patterns irregularity. This approach can be used efficiently as a complement to other compressing techniques which rely exclusively on locality to achieve their results. As much as 50% reduction in storage requirements have been observed on synthetic traces.