Diverse Unionable Tuple Search: Novelty-Driven Discovery in Data Lakes [Technical Report] Conference: Extending Database Technology; 24-27 March 2026; Tampere (Finland)

Aamod Khatiwada, Roee Shraga, Renée J. Miller · 2025

Read Diverse Unionable Tuple Search: Novelty-Driven Discovery in Data Lakes [Technical Report] Conference: Extending Database Technology; 24-27 March 2026; Tampere (Finland) by Aamod Khatiwada, Roee Shraga, Renée J. Miller (2025) 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-2509-01012.txt.

Introduction

Aamod Khatiwada, with two co-authors, introduces diverse unionable tuple search in data lakes. Unionable table search finds tables that can add rows to a query table. Data lakes hold many copies and versions of tables. The most unionable tables may thus be near duplicates of the query. They may add little new information for the user.

The team defines the problem of finding diverse unionable tuples instead. Tuples should differ from those already in the query table. An extensive analysis of diversity algorithms reveals a gap. Their DUST algorithm addresses it with clustering-based diversification. A novel embedding model represents unionable tuples better than rivals. On real data lake benchmarks, DUST is over six times faster than the best baseline. It is also more effective at diversifying results.

Catalog record

CREATORAamod Khatiwada, Roee Shraga, Renée J. Miller
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01012

Browse the full library · About the Tower of Babel

Full text

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

Diverse Unionable Tuple Search: Novelty-Driven Discovery in Data Lakes [Technical Report] Conference: Extending Database Technology; 24-27 March 2026; Tampere (Finland) Aamod Khatiwada, Roee Shraga, Renée J. Miller Abstract . Unionable table search techniques input a query table from a user and search for data lake tables that can contribute additional rows to the query table. The definition of unionability is generally based on similarity measures which may include similarity between columns (e.g., value overlap or semantic similarity of the values in the columns) or tables (e.g., similarity of table embeddings). Due to this and the large redundancy in many data lakes (which can contain many copies and versions of the same table), the most unionable tables may be identical or nearly identical to the query table and may contain little new information. Hence, we introduce the problem of identifying unionable tuples from a data lake that are diverse with respect to the tuples already present in a query table. We perform an extensive experimental analysis of well-known diversity algorithms applied to this novel problem and identify a gap that we address with a novel, clustering-based tuple diversity algorithm called DUST . DUST uses a novel embedding model to represent unionable tuples that outperforms other tuple representation models by at least 15 % 15\% when representing unionable tuples. Using real data lake benchmarks, we show that our diversification algorithm is more than six times faster than the most efficient diversification baseline. We also show that it is more effective in diversifying unionable tuples than existing diversification algorithms. \AtBeginMaketitle 1. Introduction Figure 1 . Table (a) is a Query Table (left) and Tables (b)-(d) are Data Lake Tables (right). Existing Work will add the tuples in Table (e) (most unionable) while our work will return the ones in Table (f), which are also the most diverse. Content-based table search (or table as a query) has become the dominant paradigm for table discovery in data lakes ( Fan et al. 2023a ; Dong et al. 2023 ; Hu et al. 2023 ; Hai et al. 2023 ) , particularly when metadata may be missing, ambiguous, inconsistent, or incomplete ( Nargesian et al. 2019 ; Khatiwada et al. 2023b ) . In this paradigm, users input a table as a query, and the table search system uses the data available within the query table to retrieve relevant tables. Among different types of relevance search ( Hai et al. 2023 ; Fan et al. 2023a ; Khatiwada et al. 2025 ) , we focus on Table Union Search ( Nargesian et al. 2018 ) , where the objective is to search for additional "unionable" tables. Note that an important end goal of searching for the unionable tables is to add new rows to a given query table. However, table union search techniques return the data lake tables that are most unionable to the query table ( Khatiwada et al. 2023a ; Nargesian et al. 2018 ; Bogatu et al. 2020 ) . They measure unionability between tables based on different similarity measures including value overlap between the columns ( Nargesian et al. 2018 ; Bogatu et al. 2020 ) , knowledge graphs concept similarity ( Nargesian et al. 2018 ; Khatiwada et al. 2023a ) , word embedding similarity ( Nargesian et al. 2018 ) , similarity of table representations ( Fan et al. 2023b ; Hu et al. 2023 ) , and so on. But such similarity-based techniques tend to return tables containing similar or even redundant tuples (with respect to the query table) in the top rankings. In fact, a table is most similar to itself. Example 1. Consider Query Table (a) and Data Lake Tables (b), (c) and (d) in Fig. 1 . Tables (a), (b) and (d) are about parks and their different properties, and both Tables (b) and (d) are unionable with the query table. Table (c) is about paintings and as it shares only the country attribute with (a), it is determined to be not unionable with the query table. Since table union search techniques ( Hu et al. 2023 ; Khatiwada et al. 2023a ; Nargesian et al. 2018 ; Fan et al. 2023b ) measure similarity between query and data lake tables to infer unionability, they return Table (b) as the most unionable table (Table (d) while unionable is less similar to the query). However, Table (b) is mostly a copy of the query table with a single new tuple and thus does not extend the user’s analysis much (we illustrate this in Table (e) which is "most unionable"). In contrast, Table (d) is both unionable and contains tuples with new information. If the data lake contains tables with overlapping tuples, these are likely to be returned by a union search method. Others have documented the tremendous redundancy in real data lakes ( Zhu et al. 2019 ) , noting that almost 90% of the data found in newly created datasets duplicates information already present in existing datasets in a lake ( Shraga and Miller 2023 ) . So, the top-ranked tables returned by a similarity-based union search technique may not offer much new information. An example of the impact of such redundancy could be if one were trying to integrate the discovered tables to achieve a fairness goal ( Nargesian et al. 2022 ; Yang et al. 2019 ; Stoyanovich et al. 2018 ) where most approaches assume that the discovered tables have enough tuples available to satisfy fairness constraints ( Nargesian et al. 2022 ) . However, if redundancy is high, this may not be the case. Table search is used to find training data for machine learning models ( Galhotra et al. 2023 ; Han et al. 2023 ) and redundancy in the discovered data may hamper the model’s ability to generalize. A user study on diversifying information retrieval (IR) search results reflects that when looking for new information, users are interested in finding more information within their specific subtopics of interest, rather than arbitrarily looking for any new information ( Xu and Yin 2008 ) . In our case, for instance, a user is looking for information on new parks that are not present in the query table. In this paper, we present a novel evaluation of the ability of existing diversity algorithm to diversify the tuples returned by unionability methods. We further offer DUST , a method designed to address gaps identified in existing algorithms and scalably provide a diverse set of unionable tuples. Referring to Example 1 ( Fig. 1 ), our proposed approach will find unionable tuples from a set of unionable tables where the tuples add new and diverse information to the query table as illustrated by Table (f). Figure 2 . Table (left) and Tuple (right) embedding distributions of unionable tables (tuples) from Open Data ( Khatiwada et al. 2023a ) . Each color/marker represents a distinct set of unionable tuples/tables. Tables from different sets are non-unionable. Tuple vs. Table Diversity. Our important design decision is to return a set of diverse, unionable tuples (which may come from different tables), rather than a set of diverse, unionable tables . Fig. 2 provides a motivation for this decision. Using

Read the complete text