Determining the Largest Overlap between Tables
Open Access
- 12 March 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (1) , 1-26
Abstract
Both on the Web and in data lakes, it is possible to detect much redundant data in the form of largely overlapping pairs of tables. In many cases, this overlap is not accidental and provides significant information about the relatedness of the tables. Unfortunately, efficiently quantifying the overlap between two tables is not trivial. In particular, detecting their largest overlap, i.e., their largest common subtable, is a computationally challenging problem. As the information overlap may not occur in contiguous portions of the tables, only the ability to permute columns and rows can reveal it. The detection of the largest overlap can help us in relevant tasks such as the discovery of multiple coexisting versions of the same table, which can present differences in the completeness and correctness of the conveyed information. Automatically detecting these highly similar, matching tables would allow us to guarantee their consistency through data cleaning or change propagation, but also to eliminate redundancy to free up storage space or to save additional work for the editors. We present the first formal definition of this problem, and with it Sloth, our solution to efficiently detect the largest overlap between two tables. We experimentally demonstrate on real-world datasets its efficacy in solving this task, analyzing its performance and showing its impact on multiple use cases.Keywords
This publication has 53 references indexed in Scilit:
- Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach2021
- Mining of Massive Datasets2020
- Dataset Discovery in Data Lakes2020
- Aurum: A Data Discovery System2018
- Building the Dresden Web Table Corpus: A Classification Approach2015
- Fine-grained controversy detection in Wikipedia2015
- A hybrid machine-crowdsourcing system for matching web tables2014
- DBpedia - A crystallization point for the Web of DataJournal of Web Semantics, 2009
- The human protein coevolution networkGenome Research, 2009
- Unary and n-ary inclusion dependency discovery in relational databasesJournal of Intelligent Information Systems, 2008