Freyja : Efficient Join Discovery in Data Lakes

Marc Maynou, Sergi Nadal, Raquel Panadero, Javier Flores, Oscar Romero, Anna Queralt · 2024

Read Freyja : Efficient Join Discovery in Data Lakes by Marc Maynou, Sergi Nadal, Raquel Panadero, Javier Flores, Oscar Romero, Anna Queralt (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06637.txt.

Introduction

Marc Maynou and co-authors present FREYJA, a system for finding useful joins in data lakes, in this 2024 paper. Data lakes store vast raw data in mixed forms. Their freedom makes it hard to find tables worth combining for a task.

FREYJA explores a lake and ranks possible joins by relevance. Good joins add new attributes that enrich later analysis. Modern table learning methods guide the search for candidates. Ranking matters because no team can test every pair by hand. The system aims to turn a swamp of files into usable data sets. Analysts in business and science both face that discovery problem daily. Tests on real lakes check speed as well as ranking quality.

Catalog record

CREATORMarc Maynou, Sergi Nadal, Raquel Panadero, Javier Flores, Oscar Romero, Anna Queralt
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06637

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Freyja : Efficient Join Discovery in Data Lakes Marc Maynou, Sergi Nadal, Raquel Panadero, Javier Flores, Oscar Romero, Anna Queralt Abstract We study the problem of efficiently computing rankings of joinable attributes in data lakes. Traditional set-overlap measures produce numerous false positives in this scenario, while modern, more accurate Table Representation Learning (TRL) techniques incur prohibitive computational costs. In contrast to the state-of-the-art, we adopt a novel notion of join quality tailored to data lakes relying on a metric that combines multiset Jaccard and cardinality proportion. The proposed metric merges the best of both worlds by leveraging syntactic measures while achieving accuracy scores comparable to those of TRL approaches. Generating rankings of joinable pairs is highly scalable at both preparation and query time, since we train a general-purpose predictive model. Predictions are based on data profiles, succinct and efficiently computed representations of dataset characteristics. Our experiments show that our system, Freyja , matches and improves upon, the results obtained by the state-of-the-art while reducing execution costs by orders of magnitude. I Introduction Data discovery involves navigating vast data sources to find relevant datasets and their relationships [ 1 , 2 ] , making it a vital step in the Data Science pipeline for applications like search and data augmentation [ 3 ] . This is particularly important for data-driven organizations, which rely on data lakes [ 4 , 5 ] , where they centralize the storage of their data assets (i.e., any dataset potentially relevant to the organization’s data analysts) to promote accessibility and reusability. Data discovery on data lakes presents several challenges. First, data lakes are characterized by data heterogeneity , including semantic diversity (disparate topics) and syntactic variability (differences in attributes, values or cardinalities) [ 4 ] . Second, data lakes contain a massive number of datasets , typically not large in cardinality but with a substantial number of columns. These two characteristics arise from the fact that data lakes store data coming from a myriad of independent stakeholders, whose generated datasets present properties unique to the domain they belong to. These distinctive features render classical data discovery solutions that rely on integrity constraints (e.g. PK-FKs) infeasible and ineffective. Thus, in sight of the above-mentioned challenges, we study the problem of data discovery tasks in data lakes. More precisely, we focus on computing rankings of joinable attributes. The problem is defined as follows: given a query column , our aim is to discover high-quality joins with columns in the data lake, where a high-quality join produces a semantically rich dataset. Materializing these joins provides downstream applications with an extended set of features from the data lake. State-of-the-art join discovery methods can be classified as either syntactic or semantic . Syntactic approaches define joinability via set-overlap metrics (e.g. Jaccard or containment), following the traditional inner-join paradigm. Joins are thus ranked higher in proportion to the number of shared values between two columns Since performing pairwise column computations is unfeasible on a data lake, these systems propose mechanisms to approximate their calculation (e.g. locality-sensitive hashing schemes [ 6 , 7 ] , or compact inverted indexes [ 8 , 9 ] ). While these methods are scalable, the quality of the generated rankings is negatively affected by data heterogeneity [ 10 ] . As illustrated in Example 1, when the same values are used to represent semantically disparate concepts, value-overlap methods are prone to false positives. Example 1 Consider the toy datasets of Figure 1 . Using D_{1}.Country as query column, a purely syntactic approach based on value overlap would identify D_{2}.Country , D_{3}.Language and D_{4}.X as good candidates. The first observation is that schema-based methods, such as LogMap [ 11 ] , would fail to propose the combination D_{1}.Country=D_{4}.X due to the lack of embedded semantics in the schema of D_{4} . More importantly, the pair D_{1}.Country=D_{3}.Language constitutes a false positive; despite value overlap, they represent different semantic concepts, and their join would be meaningless. D_{1} – Happiness scores Country Happiness POL 6.595 DEU 6.354 ITA 6.892 JPN 6.592 D_{2} – Satisfaction index Country Location Satisfaction ITA Bologna 1484,7 ITA Milan 1526,7 DEU Munich 1678,6 DEU Berlin 1720,6 D_{3} – Language speakers Language Speakers DEU 134M POL 50M ITA 67M JPN 123M D_{4} – Population data X Y Z DEU 84.7M 2024 ITA 58.9M 2024 POL 37.5M 2024 JPN 123.7M 2024 Fig. 1 : Toy datasets In contrast to syntactic approaches, semantic methodologies enhance the accuracy of join discovery by assessing relatedness in a higher dimensional space. To that end, Table Representation Learning (TRL) techniques are used to generate embeddings that capture the semantic properties of columns. These systems leverage deep learning algorithms that fine-tune pre-trained language models [ 2 , 12 ] or general-purpose knowledge bases [ 13 ] to semantically categorize columns. These approaches tend to produce highly accurate rankings of candidate joins, yet they are resource-intensive processes that require high-end GPUs and large memories to compute and store the necessary artifacts. Overall, syntactic approaches can operate in large-scale contexts since their methods are highly scalable, but they generate a considerable amount of false positives due to not properly addressing data heterogeneity. Conversely, TRL-based methods improve joinability assessment by capturing semantic relationships, but they are constrained by high execution costs from the underlying deep learning methods. I-A Freyja : effective and efficient joinability discovery In order to overcome the limitations present in the state-of-the-art, we present Freyja , a novel approach to accurately and efficiently compute rankings of joinable columns on data lakes. Our approach aims to retain the best of both syntactic and semantic families. Freyja enjoys the simplicity and efficiency of approximating the computation of a syntactic metric while including mechanisms to capture the semantic relationships of the sets of values to improve joinability assessment. Freyja introduces the following two novelties. I-A 1 A novel, semantic-aware data lake joinability metric Traditional set-overlap metrics are prone to false positives as they lack a mechanism to detect semantic relatedness. Hence, we propose an alternative to classical approaches that avoids costly embedding representations by introducing semantic-awareness into a scalable syntactic metric. We first employ a multiset variant of the Jaccard index for set-overlap measurement, addressing the overrepresentation of multisets in data lakes [ 14 ] . Second, building on research showing that set-overlap metrics are inaccurate when column cardinalities differ greatly [ 15 ] , which is common in real-world data lakes due to data variability and diversity, we use the cardinality proportion between sets as a lightweight proxy for semantic comparison. Our final metric is a linear combination of these two measurements, and, as we demonstrate experimentally in Section VI-B , the quality of the generated rankings is comparable to that obtained by TRL-based approaches. I-A 2 A lightweight structure to approximate the joinability metric Computing our novel metric is still expensive in large-scale data lakes due to the required set-overlap evaluation. We, therefore, propose to predict it based on data profiles , compact descriptive representations of a column. Underpinning our method is the hypothesis that profile similarity is related to the semantic relatedness of columns, assuming that a generalized closeness in the properties included in the profiles identifies meaningfully related columns. For that, we rely on

Read the complete text