{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:33:31Z","timestamp":1790750011425,"version":"4.1.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT240100832"],"award-info":[{"award-number":["FT240100832"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP240101211"],"award-info":[{"award-number":["DP240101211"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["IC200100022"],"award-info":[{"award-number":["IC200100022"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    Understanding how two tables overlap is useful for many data management tasks, but challenging because tables often differ in row and column orders and lack reliable metadata in practice. Prior work defines the largest rectangular overlap, which identifies the maximal contiguous region of matching cells under row and column permutations. However, real overlaps are rarely rectangular, where many valid matches may lie outside any single contiguous block. In this paper, we introduce the\n                    <jats:italic toggle=\"yes\">Shape-Agnostic Largest Table Overlap<\/jats:italic>\n                    (SALTO), a novel generalized notion of overlap that captures\n                    <jats:italic toggle=\"yes\">arbitrary-shaped, non-contiguous overlaps<\/jats:italic>\n                    between tables.\n                  <\/jats:p>\n                  <jats:p>To tackle the combinatorial complexity of row and column permutations, we propose to model each table as a hypergraph, casting SALTO computation into a maximum common subhypergraph problem. We prove their equivalence and show the problem is NP-hard to approximate. To solve it, we propose HyperSplit, a novel branch-and-bound algorithm tailored to table-induced hypergraphs. HyperSplit introduces (i) hypergraph-aware label classes that jointly encode cell values and their row\u2013column memberships to ensure structurally valid correspondences without explicit permutation enumeration, (ii) incidence-guided refinement and upper-bound pruning that leverage row\u2013column connectivity to eliminate infeasible partial matches early, and (iii) a tolerance-based optimization mechanism with a tunable parameter that relaxes pruning by a bounded margin to accelerate convergence, enabling scalable yet accurate overlap discovery. Experiments on real-world datasets show that HyperSplit discovers overlaps more effectively (larger overlaps in up to 78.8% of the cases) and more efficiently than state of the art. Three case studies further demonstrate its practical impact across three tasks: cross-source copy detection, data deduplication, and version comparison.<\/jats:p>","DOI":"10.1145\/3802108","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["Shape-Agnostic Table Overlap Discovery: A Maximum Common Subhypergraph Approach"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8790-1495","authenticated-orcid":false,"given":"Ge","family":"Lee","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1195-9917","authenticated-orcid":false,"given":"Shixun","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Wollongong, Wollongong, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"The University of Queensland, Brisbane, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4483-1389","authenticated-orcid":false,"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6739-4145","authenticated-orcid":false,"given":"Shazia","family":"Sadiq","sequence":"additional","affiliation":[{"name":"The University of Queensland, Brisbane, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0209-3971","authenticated-orcid":false,"given":"Yanchang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Canberra, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. List of Olympic Medalists in Atheletics (men). https:\/\/en.wikipedia.org\/wiki\/List_of_Olympic_medalists_in_athletics_(men)."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Web Data Commons - Web Tables Corpus. https:\/\/km.aifb.kit.edu\/sites\/webdatacommons\/webtables\/index.html."},{"key":"e_1_2_1_3_1","unstructured":"2025. Source code for HyperSplit. https:\/\/github.com\/DataAutonomyLab\/SALTO."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536343"},{"key":"e_1_2_1_5_1","first-page":"906","article-title":"Schema and ontology matching with COMA","author":"Aumueller David","year":"2005","unstructured":"David Aumueller, Hong Hai Do, Sabine Massmann, and Erhard Rahm. 2005. Schema and ontology matching with COMA. In SIGMOD. ACM, 906-908.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_6_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"598","author":"Bai Yunsheng","year":"2021","unstructured":"Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. 2021. GLSearch: Maximum Common Subgraph Detection via Learning to Search. In ICML (Proceedings of Machine Learning Research, Vol. 139). PMLR, 588-598."},{"key":"e_1_2_1_7_1","first-page":"425","article-title":"TabEL: Entity Linking in Web Tables. In ISWC (1) (Lecture Notes in Computer Science, Vol. 9366)","author":"Bhagavatula Chandra Sekhar","year":"2015","unstructured":"Chandra Sekhar Bhagavatula, Thanapon Noraset, and Doug Downey. 2015. TabEL: Entity Linking in Web Tables. In ISWC (1) (Lecture Notes in Computer Science, Vol. 9366). Springer, 425-441.","journal-title":"Springer"},{"key":"e_1_2_1_8_1","first-page":"85","article-title":"Exploring Change - A New Dimension of Data Analytics","volume":"12","author":"Bleifu\u00df Tobias","year":"2018","unstructured":"Tobias Bleifu\u00df, Leon Bornemann, Theodore Johnson, Dmitri V. Kalashnikov, Felix Naumann, and Divesh Srivastava. 2018. Exploring Change - A New Dimension of Data Analytics. PVLDB 12, 2 (2018), 85-98.","journal-title":"PVLDB"},{"key":"e_1_2_1_9_1","volume-title":"SEA-Data@VLDB (CEUR Workshop Proceedings","author":"Bleifu\u00df Tobias","unstructured":"Tobias Bleifu\u00df, Leon Bornemann, Dmitri V. Kalashnikov, Felix Naumann, and Divesh Srivastava. 2021. The Secret Life of Wikipedia Tables. In SEA-Data@VLDB (CEUR Workshop Proceedings, Vol. 2929). CEUR-WS.org, 20-26."},{"key":"e_1_2_1_10_1","first-page":"1284","article-title":"Structured Object Matching across Web Page Revisions","author":"Bleifu\u00df Tobias","year":"2021","unstructured":"Tobias Bleifu\u00df, Leon Bornemann, Dmitri V. Kalashnikov, Felix Naumann, and Divesh Srivastava. 2021. Structured Object Matching across Web Page Revisions. In ICDE. IEEE, 1284-1295.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_11_1","first-page":"709","article-title":"Dataset Discovery in Data Lakes","author":"Bogatu Alex","year":"2020","unstructured":"Alex Bogatu, Alvaro A. A. Fernandes, Norman W. Paton, and Nikolaos Konstantinou. 2020. Dataset Discovery in Data Lakes. In ICDE. IEEE, 709-720.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453916"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Pei Chen Soumajyoti Sarkar Leonard Lausen Balasubramaniam Srinivasan Sheng Zha Ruihong Huang and George Karypis. 2023. HyTrel: Hypergraph-enhanced Tabular Data Representation Learning. In NeurIPS.","DOI":"10.52202\/075280-1397"},{"key":"e_1_2_1_14_1","first-page":"2201","article-title":"Data Cleaning","author":"Chu Xu","year":"2016","unstructured":"Xu Chu, Ihab F. Ilyas, Sanjay Krishnan, and Jiannan Wang. 2016. Data Cleaning: Overview and Emerging Challenges. In SIGMOD. ACM, 2201-2206.","journal-title":"Overview and Emerging Challenges. In SIGMOD. ACM"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/P09008"},{"key":"e_1_2_1_16_1","first-page":"610","article-title":"COMA - A System for Flexible Combination of Schema Matching Approaches","author":"Do Hong Hai","year":"2002","unstructured":"Hong Hai Do and Erhard Rahm. 2002. COMA - A System for Flexible Combination of Schema Matching Approaches. In VLDB. Morgan Kaufmann, 610-621.","journal-title":"VLDB. Morgan Kaufmann"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687691"},{"key":"e_1_2_1_19_1","first-page":"456","article-title":"Efficient Joinable Table Discovery in Data Lakes","author":"Dong Yuyang","year":"2021","unstructured":"Yuyang Dong, Kunihiro Takeoka, Chuan Xiao, and Masafumi Oyamada. 2021. Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach. In ICDE. IEEE, 456-467.","journal-title":"A High-Dimensional Similarity-Based Approach. In ICDE. IEEE"},{"key":"e_1_2_1_20_1","first-page":"1684","article-title":"MATE: Multi-Attribute Table Extraction","volume":"15","author":"Esmailoghli Mahdi","year":"2022","unstructured":"Mahdi Esmailoghli, Jorge-Arnulfo Quian\u00e9-Ruiz, and Ziawasch Abedjan. 2022. MATE: Multi-Attribute Table Extraction. PVLDB 15, 8 (2022), 1684-1696.","journal-title":"PVLDB"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587146"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2899391"},{"key":"e_1_2_1_23_1","first-page":"627","article-title":"Clique is Hard to Approximate Within n1-epsilon","author":"H\u00e5stad Johan","year":"1996","unstructured":"Johan H\u00e5stad. 1996. Clique is Hard to Approximate Within n1-epsilon. In FOCS. IEEE Computer Society, 627-636.","journal-title":"FOCS. IEEE Computer Society"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_1_25_1","volume-title":"GitTables: A Large-Scale Corpus of Relational Tables. PACMMOD 1, 1","author":"Hulsebos Madelon","year":"2023","unstructured":"Madelon Hulsebos, \u00c7agatay Demiralp, and Paul Groth. 2023. GitTables: A Large-Scale Corpus of Relational Tables. PACMMOD 1, 1 (2023), 30:1-30:17."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000045"},{"key":"e_1_2_1_27_1","volume-title":"Reducibility Among Combinatorial Problems. In 50 Years of Integer Programming","author":"Karp Richard M.","unstructured":"Richard M. Karp. 2010. Reducibility Among Combinatorial Problems. In 50 Years of Integer Programming. Springer, 219-241."},{"key":"e_1_2_1_28_1","volume-title":"SANTOS: Relationship-based Semantic Table Union Search. PACMMOD 1, 1","author":"Khatiwada Aamod","year":"2023","unstructured":"Aamod Khatiwada, Grace Fan, Roee Shraga, Zixuan Chen,Wolfgang Gatterbauer, Ren\u00e9e J. Miller, and Mirek Riedewald. 2023. SANTOS: Relationship-based Semantic Table Union Search. PACMMOD 1, 1 (2023), 9:1-9:25."},{"key":"e_1_2_1_29_1","volume-title":"BTW (LNI","author":"Koch Maximilian","unstructured":"Maximilian Koch, Mahdi Esmailoghli, S\u00f6ren Auer, and Ziawasch Abedjan. 2023. Duplicate Table Discovery with Xash. In BTW (LNI, Vol. P-331). Gesellschaft f\u00fcr Informatik e.V., 367-390."},{"key":"e_1_2_1_30_1","volume-title":"Shape-Agnostic Table Overlap Discovery: A Maximum Common Subhypergraph Approach. arXiv preprint arXiv:2603.14419","author":"Lee Ge","year":"2026","unstructured":"Ge Lee, Shixun Huang, Zhifeng Bao, Felix Naumann, Shazia Sadiq, and Yanchang Zhao. 2026. Shape-Agnostic Table Overlap Discovery: A Maximum Common Subhypergraph Approach. arXiv preprint arXiv:2603.14419 (2026)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448943"},{"key":"e_1_2_1_32_1","first-page":"89","article-title":"Scaling up copy detection","author":"Li Xian","year":"2015","unstructured":"Xian Li, Xin Luna Dong, Kenneth B. Lyons, Weiyi Meng, and Divesh Srivastava. 2015. Scaling up copy detection. In ICDE. IEEE Computer Society, 89-100.","journal-title":"ICDE. IEEE Computer Society"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5619"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3742728.3742757"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i4.25519"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/99"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3240491"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352116"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192973"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336665"},{"key":"e_1_2_1_41_1","volume-title":"Table Overlap Estimation through Graph Embeddings. PACMMOD 3, 3","author":"Pugnaloni Francesco","year":"2025","unstructured":"Francesco Pugnaloni, Luca Zecchini, Matteo Paganelli, Matteo Lissandrini, Felix Naumann, and Giovanni Simonini. 2025. Table Overlap Estimation through Graph Embeddings. PACMMOD 3, 3 (2025), 228:1-228:25."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213962"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583169"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626756"},{"key":"e_1_2_1_45_1","first-page":"1502","article-title":"Sudowoodo","author":"Wang Runhui","year":"2023","unstructured":"Runhui Wang, Yuliang Li, and Jin Wang. 2023. Sudowoodo: Contrastive Self-supervised Learning for Multi-purpose Data Integration and Preparation. In ICDE. IEEE, 1502-1515.","journal-title":"In ICDE. IEEE"},{"key":"e_1_2_1_46_1","first-page":"1149","article-title":"ZeroER: Entity Resolution using Zero Labeled Examples","author":"Wu Renzhi","year":"2020","unstructured":"Renzhi Wu, Sanya Chaba, Saurabh Sawlani, Xu Chu, and Saravanan Thirumuruganathan. 2020. ZeroER: Entity Resolution using Zero Labeled Examples. In SIGMOD. ACM, 1149-1164.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3749646.3749714"},{"key":"e_1_2_1_48_1","volume-title":"Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach. CoRR abs\/2502.11557","author":"Yu Kaiqiang","year":"2025","unstructured":"Kaiqiang Yu, Kaixin Wang, Cheng Long, Laks V. S. Lakshmanan, and Reynold Cheng. 2025. Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach. CoRR abs\/2502.11557 (2025)."},{"key":"e_1_2_1_49_1","volume-title":"Determining the Largest Overlap between Tables. PACMMOD 2, 1","author":"Zecchini Luca","year":"2024","unstructured":"Luca Zecchini, Tobias Bleifu\u00df, Giovanni Simonini, Sonia Bergamaschi, and Felix Naumann. 2024. Determining the Largest Overlap between Tables. PACMMOD 2, 1 (2024), 48:1-48:26."},{"key":"e_1_2_1_50_1","first-page":"1951","article-title":"Finding Related Tables in Data Lakes for Interactive Data Science","author":"Zhang Yi","year":"2020","unstructured":"Yi Zhang and Zachary G. Ives. 2020. Finding Related Tables in Data Lakes for Interactive Data Science. In SIGMOD. ACM, 1951-1966.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_1_51_1","volume-title":"IJCAI. ijcai.org","author":"Zhou Jianrong","year":"1908","unstructured":"Jianrong Zhou, Kun He, Jiongzhi Zheng, Chu-Min Li, and Yanli Liu. 2022. A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem. In IJCAI. ijcai.org, 1908-1914."},{"key":"e_1_2_1_52_1","volume-title":"Miller","author":"Zhu Erkang","year":"2019","unstructured":"Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Ren\u00e9e J. Miller. 2019. JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD. ACM, 847-864."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:20:01Z","timestamp":1779128401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802108"],"URL":"https:\/\/doi.org\/10.1145\/3802108","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}