Pencarian Dependensi Pencocokan Super Cepat dengan Desbordante

Teknik optimasi untuk HyMD mencapai percepatan rata-rata lebih dari 40x, bahkan hingga 170x pada beberapa kasus, dan kini tersedia di profiler open-source Desbordante dengan integrasi Python.

Alexey Shlyonskikh; Michael Sinelnikov; Daniil Nikolaev; Yurii Litvinov; George Chernishev· 2026· DOI 10.48550/arXiv.2607.10771

Masalah inti

Dependensi pencocokan (MD) menggeneralisasi dependensi fungsional dengan mengizinkan fungsi kemiripan kustom untuk mencocokkan nilai atribut. MD sangat penting untuk tugas kualitas data seperti resolusi entitas, deduplikasi, integrasi data, dan pencocokan skema. Namun, penemuan MD sangat intensif secara komputasi, sehingga membatasi adopsi praktisnya. Penelitian ini mengatasi hambatan kinerja dengan mengoptimalkan HyMD, algoritma penemuan MD mutakhir saat ini. Penulis memperkenalkan tiga optimasi utama: teknik sampling baru untuk meningkatkan inferensi dari pasangan rekaman, teknik pencarian generalisasi yang lebih cepat, dan representasi dependensi yang lebih baik. Optimasi ini menyasar fase inferensi dan operasi terkait lattice. HyMD yang telah ditingkatkan diimplementasikan dalam Desbordante, profiler data berperforma tinggi open-source, dan tersedia dengan integrasi Python dua arah, memungkinkan pengguna memanggil implementasi C++ dari Python dan menyediakan fungsi pencocokan kustom.

Eksperimen menunjukkan bahwa optimasi menghasilkan percepatan lebih dari 40x secara rata-rata dibandingkan implementasi mutakhir, dengan beberapa kasus mencapai percepatan lebih dari 170x. Evaluasi dilakukan menggunakan implementasi Desbordante. Makalah ini melaporkan hasil tersebut sebagai bukti efektivitas teknik yang diusulkan. Versi HyMD yang telah ditingkatkan siap digunakan dan disertai integrasi Python dua arah, memungkinkan pengguna memanggil algoritma C++ dari program Python sekaligus menyediakan fungsi pencocokan kustom mereka sendiri.

Dependensi pencocokan (MD) menggeneralisasi dependensi fungsional dengan mengizinkan fungsi kemiripan kustom untuk mencocokkan nilai atribut. MD sangat penting untuk tugas kualitas data seperti resolusi entitas, deduplikasi, integrasi data, dan pencocokan skema. Namun, penemuan MD sangat intensif secara komputasi, sehingga membatasi adopsi praktisnya. Penelitian ini mengatasi hambatan kinerja dengan mengoptimalkan HyMD, algoritma penemuan MD mutakhir saat ini. Penulis memperkenalkan tiga optimasi utama: teknik sampling baru untuk meningkatkan inferensi dari pasangan rekaman, teknik pencarian generalisasi yang lebih cepat, dan representasi dependensi yang lebih baik. Optimasi ini menyasar fase inferensi dan operasi terkait lattice. HyMD yang telah ditingkatkan diimplementasikan dalam Desbordante, profiler data berperforma tinggi open-source, dan tersedia dengan integrasi Python dua arah, memungkinkan pengguna memanggil implementasi C++ dari Python dan menyediakan fungsi pencocokan kustom.

Makalah ini menjelaskan tiga optimasi utama untuk HyMD:

Percepatan signifikan yang dicapai oleh optimasi membuat penemuan dependensi pencocokan lebih praktis untuk tugas kualitas data di dunia nyata. Kombinasi teknik sampling baru, pencarian generalisasi yang lebih cepat, dan representasi dependensi yang lebih baik mengatasi hambatan pada inferensi dan operasi lattice. Integrasi ke dalam Desbordante, profiler open-source, dan antarmuka Python dua arah menurunkan hambatan adopsi, memungkinkan pengguna memanfaatkan fungsi kemiripan kustom. Penelitian ini berkontribusi pada penerapan MD yang lebih luas dalam resolusi entitas, deduplikasi, integrasi data, dan pencocokan skema. Penelitian selanjutnya dapat mengeksplorasi optimasi lebih lanjut atau perluasan ke jenis dependensi lain.

Praktisi dan peneliti ilmu komputer

Membuka konten member…