Penemuan Tumpang Tindih Tabel Tanpa Batasan Bentuk: Pendekatan Subhipergraf Umum Maksimum

Memahami bagaimana dua tabel saling tumpang tindih sangat penting untuk banyak tugas pengelolaan data, namun hal ini tetap menantang karena tabel sering berbeda dalam urutan baris dan kolom serta tidak memiliki metadata yang andal. Penelitian sebelumnya mendefinisikan tumpang tindih persegi panjang terbesar, yang mengidentifikasi wilayah bersambung maksimal dari sel yang cocok di bawah permutasi baris dan kolom. Namun, tumpang tindih nyata jarang berbentuk persegi panjang; banyak kecocokan yang valid mungkin berada di luar satu blok bersambung mana pun. Makalah ini memperkenalkan Shape-Agnostic Largest Table Overlap (SALTO), gagasan umum baru tentang tumpang tindih yang menangkap tumpang tindih berbentuk arbitrer dan tak bersambung antar tabel. Penulis mengatasi kompleksitas kombinatorial permutasi baris dan kolom dengan memodelkan setiap tabel sebagai hipergraf dan merumuskan komputasi SALTO sebagai masalah subhipergraf umum maksimum. Mereka membuktikan ekuivalensinya dan menunjukkan masalah tersebut NP-hard untuk diaproksimasi.

Eksperimen pada dataset dunia nyata menunjukkan bahwa HyperSplit menemukan tumpang tindih lebih efektif dan efisien daripada state of the art. Secara spesifik, HyperSplit menemukan tumpang tindih yang lebih besar pada hingga 78,8% kasus dibandingkan metode baseline. Penulis juga melakukan tiga studi kasus untuk menunjukkan dampak praktis pada tiga tugas: deteksi salinan lintas sumber, deduplikasi data, dan perbandingan versi. Dalam deteksi salinan lintas sumber, HyperSplit mengidentifikasi tabel yang disalin bahkan ketika baris dan kolom diacak. Untuk deduplikasi data, ini membantu menggabungkan catatan duplikat dengan kecocokan tak bersambung. Dalam perbandingan versi, ini mengungkap perubahan antar versi tabel dengan menemukan subhipergraf umum terbesar. Optimasi berbasis toleransi memungkinkan penyetelan untuk skalabilitas, mencapai konvergensi lebih cepat dengan kehilangan akurasi yang terbatas.