Source-linked AI summary
Dataset Discovery in Data Lakes
Alex Bogatu, Alvaro A. A. Fernandes, Norman W. Paton, Nikolaos Konstantinou
TL;DR
Dataset discovery asks how to find useful tables in vast data lakes when conceptual relationships and metadata are limited. The paper proposes D3L, which indexes schema- and instance-level features in a common distance space to retrieve related tables and join opportunities. Across the reported evaluation, D3L is significantly more effective and efficient than state-of-the-art approaches.
Problem
Dataset discovery must identify datasets relevant to populating a target despite limited metadata and weakly known relationships in data lakes.
Method
D3L maps schema- and instance-level evidence into hash-based indexes and a uniform distance space for measuring relatedness to a target.
Results
D3L is reported as significantly more effective and efficient than state-of-the-art approaches across real-world and synthetic data.
Takeaways & Limitations
Fine-grained evidence, common-space aggregation, and LSH-based join-path discovery support more effective and efficient dataset discovery with increased and precise target coverage.
Abstract
from arXiv · showhide
Data analytics stands to benefit from the increasing availability of datasets that are held without their conceptual relationships being explicitly known. When collected, these datasets form a data lake from which, by processes like data wrangling, specific target datasets can be constructed that enable value-adding analytics. Given the potential vastness of such data lakes, the issue arises of how to pull out of the lake those datasets that might contribute to wrangling out a given target. We refer to this as the problem of dataset discovery in data lakes and this paper contributes an effective and efficient solution to it. Our approach uses features of the values in a dataset to construct hash-based indexes that map those features into a uniform distance space. This makes it possible to define similarity distances between features and to take those distances as measurements of relatedness w.r.t. a target table. Given the latter (and exemplar tuples), our approach returns the most related tables in the lake. We provide a detailed description of the approach and report on empirical results for two forms of relatedness (unionability and joinability) comparing them with prior work, where pertinent, and showing significant improvements in all of precision, recall, target coverage, indexing and discovery times.
I. INTRODUCTION
The paper frames dataset discovery as finding useful datasets in conceptually unstructured data lakes for subsequent data-wrangling tasks. D3L uses multiple similarity signals mapped into a common distance space to retrieve related tables, including tables connected through join opportunities.
- Data lakes lack globally cohesive models of dataset interrelationships, making useful datasets difficult to discover for a given analytic task.
- Dataset discovery filters an otherwise unmanageable lake to find datasets useful for populating target attributes and subsequent wrangling stages.
- D3L extracts five evidence types and maps them into locality-sensitive hashing indexes to measure dataset relatedness.
- The framework combines separate relatedness measurements in a common space and weights evidence according to signal strength.
- D3L extends discovery to weakly target-related tables that join with other tables contributing values to additional target attributes.
- Using real-world and synthetic data, D3L is reported as significantly more effective and efficient than state-of-the-art approaches.
III. RELATEDNESS DISCOVERY
The paper defines dataset relatedness through attribute-level relevance to a target and estimates it from evidence available within the datasets themselves. It uses five fine-grained evidence types to accommodate differently represented or dirty data.
- A dataset is related to a target when one of its attributes contains values from the same domain as a target attribute and can help populate it.
- Related datasets may differ in relatedness strength according to the number and strength of their attributes related to target attributes.
- Relatedness supports unionability across attributes linked to the same target attribute and can support join-based extensions when datasets are joinable.
- The framework quantifies relatedness with distance measures, treating closer attributes as more similar and more related.
- Because data lakes provide little metadata, attribute relatedness must be inferred from evidence conveyed by the datasets themselves.
- D3L uses names, values, formats, word embeddings, and domain distributions, with fine-grained representations intended to reduce the impact of dirty data.
B. Attribute Relatedness: Distance Computation
D3L converts attribute names and values into set or vector representations, computes several bounded distance measures, and uses LSH to approximate relatedness efficiently. Separate indexes support retrieval by name, value, format, and embedding evidence.
- Each evidence type yields a distance in [0, 1], allowing multiple signals from attribute names and extents to be combined.
- Name, value, and format relatedness use Jaccard distances, embedding relatedness uses cosine distance, and domain relatedness uses the KS measure.
- LSH replaces pairwise distance comparisons with an approximate solution using MinHash and random projections, trading potential accuracy for efficiency.
- The system builds four LSH indexes for name, value, format, and embedding relatedness and retrieves candidate attributes through index lookups.
- Index construction derives q-grams, informative tokens, regular-expression formats, and embedding vectors before inserting their representations into indexes.
- The representations are hashed rather than full attribute names or values, producing finer-grained similarity signals and efficient approximate measurements.
C. Attribute Relatedness: The Numeric Case
Numeric attributes require special handling because token and word-embedding evidence is unsuitable and corresponding value-based LSH schemes are unavailable. D3L therefore contextualizes numeric values with subject attributes and computes distribution similarity only after blocking.
- For numeric attributes, only name and format evidence is used because tokens and word embeddings are not useful signals.
- D3L uses index evidence from names and formats before deciding whether to compute domain-distribution relatedness.
- The numeric procedure computes KS similarity for attributes whose subject attributes or name and format indexes indicate relatedness.
- A subject attribute identifies the entities described by a dataset, while non-subject attributes describe properties of those entities.
- The framework assumes each dataset has one non-numeric subject attribute and uses it to contextualize numeric properties.
D. Deciding on Table Relatedness
D3L aggregates multiple attribute-level relatedness signals into dataset-level distances, then ranks the k most related datasets for a target. Its weighting scheme emphasizes unusually strong signals and combines evidence types in a weighted Euclidean space.
- Attribute evidence: D3L retrieves attributes related to each target attribute from four indexes, returning distance measures and potentially a fifth numeric distribution-based measure.The pipeline groups retrieved related attributes by source dataset before aggregating their distances.
- Distance aggregation: For each evidence type, D3L aggregates related attribute distances column-wise into a five-dimensional dataset vector using a weighted average.The dimensions are N, V, F, E, and D, corresponding to the available relatedness measures.
- Distance aggregation: Weights are derived from each distance’s position in the lake-wide distribution, so unusually strong relatedness receives greater weight than weak relatedness.The weight represents the probability that the observed distance is the smallest among related distances of that type.
- Dataset ranking: D3L represents each dataset as a point whose coordinates are its five aggregated distances and computes relatedness with a weighted l2-norm.The target is placed at [0, 0, 0, 0, 0], making distance from that point the dataset-level relatedness measure.
- Dataset ranking: The evidence-type weights are learned by treating relatedness as binary classification over five-dimensional distance vectors from a benchmark ground truth.The stated intuition is to reduce distances between related datasets and increase distances between unrelated datasets.
- Dataset ranking: Given a target and repository, dataset discovery returns the k most related datasets according to the resulting distance measure.This formalizes the discovery problem as ranking datasets by Equation 3.
IV. EXTENDING RELATEDNESS THROUGH JOIN PATHS
D3L extends top-k relatedness discovery with join paths that connect highly related tables to weaker-signal tables. These paths can add values to covered attributes or populate previously uncovered target attributes.
- Join-path motivation: Join-path discovery searches beyond the top-k tables for weaker-related datasets that can contribute through joins.The extension is intended to increase target coverage while retaining the initial relatedness ranking.
- Joinability: D3L focuses on joins based on postulated partial inclusion dependencies and defines SA-joinability using subject–attribute and instance-value evidence.The supplied description states that exhaustive data profiling is impractical for the targeted data-lake scale.
- Joinability: The method models the data lake as an SA-join graph whose nodes are datasets and whose edges connect SA-joinable dataset pairs.The graph is defined over the entire lake using the two SA-joinability conditions.
- Path discovery: Depth-first traversal starts from each top-k dataset and retains noncyclic paths whose additional nodes are outside the top-k and related to the target through at least one index.The procedure returns paths within the relevant connected component or across the graph.
- Path benefits: Each discovered path can add values to an already covered target attribute or populate an attribute that was previously uncovered.The reported experiments show improved achievable target coverage and precision when join opportunities are included.
V. EVALUATION
The evaluation measures D3L’s effectiveness on synthetic and real repositories and its efficiency on a larger real repository. Ground truth is derived synthetically or manually, with repository characteristics affecting ranking, coverage, and join-path accuracy.
- Evaluation design: The evaluation compares individual evidence types with the aggregated approach, then assesses D3L against TUS and Aurum for effectiveness and efficiency.A final evaluation measures target coverage and precision after adding datasets joinable with top-k tables.
- Repositories: Synthetic contains approximately 5,000 tables and 1.1GB of synthetically derived data, supporting comparative precision and recall measurement.Its average answer size is 260 related tables over 100 randomly selected targets.
- Repositories: Smaller Real contains approximately 700 tables and 600MB of UK open government data, supporting comparative effectiveness measurement.Its average answer size is 110.
- Repositories: Larger Real contains approximately 43,000 tables and 12GB of NHS data, and is used only to measure comparative efficiency.The repository consists of real-world information from different UK National Health Service organizations.
- Ground truth: Synthetic ground truth records derivation-based relationships, whereas Smaller Real ground truth manually records related tables and attributes.In both repositories, ground truth lists each table’s attributes and the related attributes of other tables.
- Dataset characteristics: Arity affects top-k ranking and target coverage, while cardinality affects similarity estimation and join-path discovery through instance-value overlap.The evaluation passage also notes that numerical-attribute proportions differ across repositories.
A. Baselines and reported measures
D3L is evaluated against TUS and Aurum using top-k precision and recall, with table-level true positives defined by at least one related attribute. Results are averaged over 100 randomly selected targets.
- Baselines: TUS uses three instance-value evidence types and similar indexing and querying models, making it a comparative baseline for unionability effectiveness and efficiency.The passage describes TUS as a framework for measuring unionability from multiple instance-value viewpoints.
- Baselines: Aurum combines schema- and instance-level information in a profiled and indexed graph supporting keyword search, unionability, and joinability discovery.It is compared with D3L on indexing time, effectiveness, and the added value of join paths.
- Reported measures: Precision and recall are reported for the top-k returned datasets because the evaluation focuses on the strongest results rather than all weakly related lake members.The measures are computed over the answer’s top-k tables.
- Reported measures: A returned table counts as a true positive when at least one, but not necessarily all, of its attributes is related to the target.Precision is p = TP/(TP + FP), and recall is r = TP/(TP + FN).
- Reported measures: The evaluation treats missing one related attribute as insufficient to classify the table as unrelated and examines target coverage in joinability experiments.The stated rationale is that every attribute contributing to target population matters.
- Evaluation protocol: Each reported result is averaged over 100 randomly selected targets from the relevant repository.D3L and, where applicable, TUS and Aurum are run over those targets.
B. Individual effectiveness
Individual evidence types vary in effectiveness, while combining all five produces the strongest precision and recall on Smaller Real. Numerical attributes add little beyond other evidence types in this benchmark.
- Format evidence alone achieves low precision and recall, indicating limited discrimination among attributes with similar representations.Reported precision ranges from 0.10 to 0.30 and recall from 0.03 to 0.43.
- At k = 110, individual evidence types achieve 0.43–0.60 precision and 0.49–0.70 recall, with values performing best.The ranges span embeddings through values among the four compared evidence types.
- At k = 110, combining all evidence raises precision from 60% to almost 70% and recall from 65% to more than 70% relative to values alone.The combined approach also yields a 29% increase in the percentage of correct values returned.
- Restricting the experiment to non-numerical attributes decreases aggregated precision and recall by less than 3.5% each.This indicates that most discoverable numerical relatedness is already identified by other evidence types in this benchmark.
C. Comparative Effectiveness
D3L generally outperforms TUS and Aurum in precision and recall across synthetic and smaller-real repositories. Its multi-evidence aggregation and more tolerant value-format handling are especially beneficial on real data.
- On Synthetic, D3L remains highly precise through k = 140 before declining to 0.65 at k = 350.Aurum declines to 0.49 at k = 350, while TUS consistently places 20%–30% false positives above truly related tables.
- D3L’s finer-grained features and aggregation outperform max-score baseline aggregation by balancing evidence dimensions and reducing the impact of highly scored false positives.The comparison explains the stronger overall performance against the baselines.
- D3L identifies up to 20% more relevant tables than TUS and up to 10% more than Aurum as answer size increases.Recall rises quickly through k ∈[5, 140] and levels out beyond the average answer size.
- On Smaller Real, D3L precision exceeds TUS by 0.2–0.4 and Aurum by 0.05–0.3 for k ∈[5, 110].The reported advantage is attributed to D3L’s aggregation framework and its use of value-based evidence without requiring exact instance-value equality.
- At k = 110 on Smaller Real, D3L recalls more than 70% of related datasets, compared with around 55% for both TUS and Aurum.The gap is wider on Smaller Real because D3L uses a more lenient approach to value-format representation, while the baselines depend more on clean, consistent values.
D. Comparative Efficiency
D3L improves indexing efficiency over TUS as data lakes grow and searches are faster than TUS, although its richer indexes require more space and numeric processing can reduce the search-time gap.
- Compared with TUS, D3L indexes up to 4x faster on small and medium lakes and up to 6x faster on larger lakes.Aurum is up to 5x faster than D3L on small lakes and comparable on larger ones.
- On Synthetic, D3L searches faster than TUS because it avoids knowledge-base mapping and directly connects distance-based search with relatedness measurements.TUS also performs additional computation after index lookup to obtain unionability measurements.
- Aurum’s average search time is 22.42 seconds on Synthetic and 18.37 seconds on Smaller Real for 100 queries.These timings use graph structures accommodating at least 260 and 110 datasets, respectively, and are reported as not directly comparable.
- On Smaller Real, D3L still outperforms TUS in search time, but the gap shrinks for k > 50 because the repository has more numeric values and fewer tables.TUS ignores numeric attributes, whereas D3L spends computation time considering them; TUS consequently loses about 0.2 in both precision and recall at k = 110.
- D3L’s indexes occupy more space because they encode more evidence types and finer-grained relatedness features.For Synthetic, TUS and Aurum occupy 13% less space than D3L; the space difference increases for Smaller and Larger Real repositories.
E. Impact of join opportunities
The evaluation measures how join opportunities affect target coverage and attribute precision. Adding joinable datasets generally improves coverage, while D3L(+J) maintains higher precision than the compared systems.
- Coverage and precision measures: Coverage is evaluated by averaging how many target attributes are related to the top-k datasets and their join-path results.Join-path coverage combines attributes contributed by all join paths starting from each selected dataset.
- Synthetic repository: Join paths allow D3L+J and Aurum+J to cover most target attributes on Synthetic, whereas coverage drops sharply without join paths.The result supports the hypothesis that relevant sources may be distant from the target in the initial ranking.
- Synthetic repository: 85%–100% attribute precision is achieved by D3L+J for k < 260 on Synthetic, compared with a 65% lower bound for Aurum+J at k = 260.The paper links the difference to finer-grained, multi-evidence similarity signals and more restrictive join-path conditions.
- Smaller Real repository: D3L covers more target attributes than TUS and Aurum across the entire k interval on Smaller Real.The paper attributes this to D3L retrieving higher-quality datasets related to the target.
- Smaller Real repository: TUS and Aurum populate only 35%–45% and 20%–50% correct target attributes, respectively, on Smaller Real.The reported ranges are consistent with their lower dataset-level precision.
- Smaller Real repository: D3L+J attribute precision increases by up to 0.2 for k ∈[50, 170] when joinable tables are included.The precision advantage persists because D3L can identify relatedness despite differing value formats.
VI. CONCLUSIONS
The paper presents D3L as an effective and efficient solution for dataset discovery in data lakes. It combines schema- and instance-based features in hash-based indexes and reports advantages over similar approaches.
- VI. CONCLUSIONS: D3L uses schema- and instance-based features in hash-based indexes to map similarity evidence into a uniform distance space.Hash-value similarity is used as a relatedness measurement while reducing computational effort.
- VI. CONCLUSIONS: The paper identifies fine-grained schema and instance features as more effective for detecting relatedness when similar entities are inconsistently represented.This is presented as one of D3L’s main advantages over similar approaches.