Perpustakaan Digital ITB

Pencarian kata kunci pada suatu graf merupakan ilmu yang tergolong baru dan mulai untuk diteliti pada tahun 2010. Pada laporan tugas akhir ini, akan dibahas mengenai suatu pendekatan untuk mendapatkan jawaban dari suatu atau kumpulan kata kunci. Pendekatan tersebut menekankan pada mencari aproksimasi kemiripan suatu graf dengan menggunakan metrik baru yang diusung oleh Sinha dan rekannya. Masih oleh pengusung yang sama, untuk mencari kandidat jawaban dalam suatu graf besar, digunakan suatu graf baru yang merepresentasikan graf besar untuk mempercepat pencarian dan mempermudah mendapatkan ringkasan kandidat jawaban. Setelah itu, diambil graf yang sesuai dengan graf yang diharapkan menggunakan metrik aproksimasi yang diusung oleh Sinha dan rekannya untuk mencari graf yang mirip dengan graf yang diharapkan. Berdasarkan hasil analisis, algoritma personalisasi kata kunci memiliki kompleksitas eksponensial yang menyebabkan algoritma ini pada awalnya tidak scalable. Setelah dianalisis lebih lanjut, terdapat variabel yang dapat dikontrol sehingga kompleksitas algoritma ini dapat direduksi menjadi polinomial. Variabel yang dimaksud adalah jumlah kata kunci masukan. Pada tahap pengujian dilakukan dengan menggunakan data uji yang sudah disediakan oleh QALD karena sudah memiliki standar baku. Setiap kasus uji dicari jawaban kasus uji secara terpisah dan dihitung nilai F1-nya secara terpisah. Kemudian dicari nilai rata-rata F1-nya untuk dibandingkan dengan algoritma pencocokan semantik SPAQRL. Berdasarkan hasil tersebut, algoritma personalisasi kata kunci belum mampu menyaingin tingkat keefektifan menjawab kueri dibanding algoritma pencocokan semantik SPARQL.