A multi-start simulated annealing strategy for data lake organization problem

Abstract

Data Lake is the solution for Big Data that has received the most attention recently. Its main feature is handling vast volumes of heterogeneous data in its raw format. However, this makes data access, management, and exploration more complex. Such a challenge defines the organizational problem. The Data Lake Organization Problem comprises optimized data navigation structures generation to reduce the user’s time exploring all available data. The goal is to find a data organization that maximizes the expected probability of table discovery during user navigation. For this problem, we propose a simulated annealing metaheuristic and compare it with the Organize literature solution on benchmark instances. We also propose a more efficient variation that prunes excessive computations. The instances are Socrata Open Data Lake samples with varying topics and open data from government entities worldwide. To validate our proposals, we performed statistical analysis using a non-parametric test, which confirmed the dominance of our proposition over the state-of-the-art. Our best proposal was more efficient and increased the expected probability of table discovery up to 44%. Thus, our strategy can find better solutions in the benchmarks evaluated even without exhaustively analyzing all of them and more effectively exploring the space of solutions.