Efficient distinctiveness maximization in datasets assemblage: from homogeneous to heterogeneous datasets

Abstract

Abstract We study the distinctiveness maximization problem for datasets assemblage: assembling a set of datasets from a repository that satisfies a user-specified target schema and query set under a budget constraint, while maximizing the number of distinct tuples. This problem is NP-hard in two scenarios: (i) when the repository contains datasets conforming to the target schema, and (ii) when no dataset individually satisfies the schema and candidates must be constructed through joins. For the first scenario, a greedy algorithm with exact distinctiveness computation achieves a $$(1-e^{-1})/2$$ ( 1 - e - 1 ) / 2 -approximation ratio, but is costly due to exhaustive tuple-wise marginal gain computation. We therefore propose an efficient machine learning (ML)-based method that directly estimates the marginal distinctiveness gain of each candidate dataset, avoiding costly exact computations. For the second scenario, we integrate a column-level merging technique into our ML framework to construct candidate datasets and estimate their distinctiveness without physically materializing join results, supporting efficient assemblage over heterogeneous datasets. Extensive experiments on real-world data pools show that our methods consistently outperform relevant baselines in effectiveness, efficiency, and scalability. A downstream case study on two ML tasks further shows that our approach identifies datasets with more useful tuples and improves ML performance.