MosaicJoin: Sketsa Semantik Ringkas untuk Penemuan Join Tingkat Nilai

Strategi sketsa tanpa pelatihan yang membuat penemuan join semantik tingkat nilai dapat diskalakan ke kolom berkardinalitas tinggi sekaligus mempertahankan penyelarasan nilai yang terperinci

Grace Fan; Eden Wu; Majid Daliri; Juliana Freire· 2026· DOI 10.48550/arXiv.2607.21781

Masalah inti

Penemuan join adalah tugas inti dalam pencarian dataset: diberikan sebuah kolom kueri, tujuannya adalah menemukan kolom di data lake yang dapat di-join dengannya. Pendekatan awal berfokus pada equi-join, di mana nilai cocok secara persis. Namun, data lake dan repositori open-data sering kali memuat kolom yang nilainya merujuk pada entitas dunia nyata yang sama tetapi memakai representasi sintaktis berbeda—misalnya, "IBM" vs. "International Business Machines" atau "NYC" vs. "New York City". Kolom yang dapat di-join secara semantik seperti itu tidak dapat ditemukan melalui pencocokan persis. Pendekatan terkini untuk penemuan join semantik menghadapi trade-off mendasar. Metode tingkat nilai membandingkan nilai secara langsung dan dapat mengidentifikasi kolom yang dapat di-join secara akurat, tetapi skalanya buruk untuk kolom berkardinalitas tinggi karena jumlah perbandingan nilai berpasangan tumbuh dengan cepat. Metode tingkat kolom mengodekan seluruh kolom menjadi satu embedding, yang efisien, tetapi kehilangan penyelarasan nilai yang terperinci yang menentukan apakah suatu join benar-benar mungkin. MosaicJoin disajikan sebagai metode penemuan join semantik tingkat nilai yang menyei

Inovasi

Penulis melakukan eksperimen ekstensif untuk mengevaluasi MosaicJoin terhadap metode yang telah dipublikasikan sebelumnya pada berbagai benchmark. Temuan utamanya adalah: - **Akurasi.** MosaicJoin mengungguli metode yang telah dipublikasikan sebelumnya pada semua benchmark. Hal ini menunjukkan bahwa pendekatan sketsa tingkat nilainya mempertahankan penyelarasan terperinci yang dibutuhkan untuk penemuan join semantik yang akurat, tidak seperti metode embedding tingkat kolom. - **Kecepatan.** MosaicJoin berjalan hingga 66 kali lebih cepat daripada metode tingkat nilai lainnya. Percepatan ini diatribusikan pada strategi sketsa dan subsampling kueri, yang membatasi biaya penilaian daring oleh ukuran sketsa alih-alih kardinalitas kolom. - **Skalabilitas.** MosaicJoin dapat diskalakan secara robust ke kolom kueri yang memuat hingga 57K nilai dan kolom data lake yang memuat hingga 1M nilai. Hal ini menunjukkan kemampuannya menangani kolom berkardinalitas tinggi yang menantang metode perbandingan tingkat nilai. - **Tanpa pelatihan.** Metode ini tidak memerlukan pelatihan atau fine-tuning, yang menyederhanakan penerapan dan menghindari kebutuhan data berlabel. Hasil-hasil tersebut secara

Penemuan join adalah tugas inti dalam pencarian dataset: diberikan sebuah kolom kueri, tujuannya adalah menemukan kolom di data lake yang dapat di-join dengannya. Pendekatan awal berfokus pada equi-join, di mana nilai cocok secara persis. Namun, data lake dan repositori open-data sering kali memuat kolom yang nilainya merujuk pada entitas dunia nyata yang sama tetapi memakai representasi sintaktis berbeda—misalnya, "IBM" vs. "International Business Machines" atau "NYC" vs. "New York City". Kolom yang dapat di-join secara semantik seperti itu tidak dapat ditemukan melalui pencocokan persis.

Pendekatan terkini untuk penemuan join semantik menghadapi trade-off mendasar. Metode tingkat nilai membandingkan nilai secara langsung dan dapat mengidentifikasi kolom yang dapat di-join secara akurat, tetapi skalanya buruk untuk kolom berkardinalitas tinggi karena jumlah perbandingan nilai berpasangan tumbuh dengan cepat. Metode tingkat kolom mengodekan seluruh kolom menjadi satu embedding, yang efisien, tetapi kehilangan penyelarasan nilai yang terperinci yang menentukan apakah suatu join benar-benar mungkin. MosaicJoin disajikan sebagai metode penemuan join semantik tingkat nilai yang menyeimbangkan trade-off ini. Metode ini mencapai skalabilitas melalui strategi sketsa baru yang mengaproksimasi kelayakan join suatu pasangan kolom tanpa membandingkan semua nilai. Pada waktu kueri, setiap sketsa kandidat dinilai memakai skor kelayakan join dengan biaya yang dibatasi oleh ukuran sketsa, sehingga pengambilan tetap efisien bahkan untuk kolom berkardinalitas tinggi. Operator subsampling kueri lebih lanjut mengurangi waktu pencarian daring dengan jaminan akurasi yang dapat dibuktikan, sehingga memungkinkan pengambilan yang robust untuk kolom kueri berukuran besar. Metode ini tidak memerlukan pelatihan atau fine-tuning dan dievaluasi secara ekstensif terhadap metode yang telah dipublikasikan sebelumnya.

Mengapa penting

Tantangan mendasar yang ditangani MosaicJoin adalah ketegangan antara akurasi tingkat nilai dan skalabilitas. Metode tingkat nilai akurat karena membandingkan nilai aktual, tetapi menjadi sangat mahal seiring pertumbuhan kardinalitas. Metode tingkat kolom efisien tetapi kehilangan granularitas yang dibutuhkan untuk menentukan apakah suatu join mungkin dilakukan. MosaicJoin menyelesaikan hal ini dengan memperkenalkan sketsa yang mengaproksimasi kelayakan join tanpa membandingkan semua nilai. Strategi sketsa adalah inovasi kuncinya. Dengan membatasi biaya penilaian oleh ukuran sketsa, MosaicJoin membuat pengambilan efisien bahkan untuk kolom dengan hingga 1M nilai. Operator subsampling kueri menambah lapisan efisiensi lain, dengan jaminan akurasi yang dapat dibuktikan yang memastikan pengambilan robust untuk kolom kueri berukuran besar. Hal ini khususnya penting karena kolom kueri dapat memuat hingga 57K nilai, dan subsampling mengurangi waktu pencarian daring tanpa mengorbankan keandalan. Fakta bahwa MosaicJoin tidak memerlukan pelatihan atau fine-tuning merupakan keunggulan praktis yang signifikan. Metode ini dapat diterapkan langsung pada data lake dan domain baru, menghindari overhead pelatihan model dan kebutuhan data berlabel. Eksperimen ekstensif menunjukkan bahwa MosaicJoin mengungguli metode sebelumnya pada semua benchmark sekaligus hingga 66 kali lebih cepat daripada metode tingkat nilai lainnya. Salah satu batasannya adalah makalah tidak memberikan rincian tentang benchmark spesifik yang digunakan atau metrik akurasi yang tepat, tetapi hasil yang dilaporkan konsisten pada semua benchmark. Pekerjaan mendatang dapat mengeksplorasi perluasan pendekatan sketsa ke jenis join lain, seperti yang melibatkan banyak kolom atau fungsi pencocokan yang kompleks. Secara keseluruhan, MosaicJoin merupakan langkah maju yang signifikan dalam membuat penemuan join semantik tingkat nilai praktis untuk data lake berskala besar.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…