A meta-heuristic approach for RLE compression in a column store table

Structured data are one of the most important segments in the realm of big data analysis that have undeniably prevailed over the years. In recent years, column-oriented design has become a frequent practice to organize structured data in analytical systems. The storage systems that organize data in a column-wise manner are often referred to as column stores. Column-oriented databases or warehouses and spreadsheet applications in particular have recently become a popular and a convenient tool for column-wise data processing and analysis. At the same time, the volume of data is increasing at an extreme rate, which despite the decrease in pricing of storage systems stresses the importance of data compression. Apart from resounding performance gain in large read-mostly data repositories, column-oriented data are easily compressible, which enables efficient query processing and pushes the peak of the overall performance. Many compression algorithms, including the Run Length Encoding (RLE), exploit the similarity among the column values, where repetitions of the same value form columnar runs that can be found in most database systems. This paper presents a comprehensive analysis and comparison of common and well-known meta-heuristics for columnar run minimization, based on standard implementations by using real datasets. We have analyzed genetic algorithms, simulated annealing, cuckoo search, particle swarm optimization, Tabu search, and the bat algorithm. The first three being the most efficient have undergone sensitivity analysis on synthetic datasets to fine-tune their parameters. These meta-heuristics were then tested on real datasets. The experiments show that the algorithms perform consistently well on both synthetic and real data, demonstrating higher run-reduction efficiency compared to existing approaches. Moreover, the results show that the applied meta-heuristics exhibit quick convergence to nearly optimal solutions, accompanied by an insignificant overhead. In addition, we provide comprehensive implementations of the heuristic RLE compression approaches based on common optimization methods. They are effective at physical compression to an extent that makes them suitable as everyday appliances. The experiments on real datasets also indicate that our implementations are able overcome the expected on-disk file compression ratio, in most cases being better than the respective reduction in runs.