Perpustakaan Digital ITB

Abstrak: Pada Tugas Akhir ini dibangun program PrefixSpan untuk sequential pattern mining. Program ini dibangun untuk mengimplementasi algoritma PrefixSpan dan meningkatkan kinerja waktu proses dari implementasi tersebut dengan strategi-strategi implementasi yang tidak mengubah konsep dasar algoritma tersebut. Algoritma PrefixSpan merupakan algoritma tercepat untuk sequential pattern mining, namun belum terdapat literatur yang membahas bagaimana mengubah algoritma PrefixSpan menjadi program yang dapat dijalankan. Karena sequential pattern mining seringkali melibatkan data yang besar, perlu diterapkan strategi implementasi agar dapat mengurangi waktu proses yang dibutuhkan algoritma ini. Faktor lainnya adalah PrefixSpan merupakan algoritma rekursif, sehingga akan terdapat kemungkinan untuk tidak dapat berjalan sampai proses selesai karena call stack komputer telah penuh. Selain itu, PrefixSpan menyimpan data yang diprosesnya pada main memory, sehingga besar kemungkinan main memory tersebut tidak dapat menampung data tersebut. Agar dapat mengimplementasi PrefixSpan, terdapat 3 mekanisme dasar yang harus dipahami, yaitu mekanisme proyeksi, mekanisme penggabungan prefix dan postfix, dan mekanisme pencarian frequent sequence 1 elemen. Kemudian konsep algoritma perlu diubah dari rekursif menjadi iteratif untuk menangani kasus call stack penuh. Untuk dapat meningkatkan kinerja dari PrefixSpan, program dibangun dalam bentuk multithreading dan mekanisme pencarian frequent sequence 1 elemen dibatasi hanya melakukan pencarian pada elemen yang telah ditemukan pada pencarian sebelumnya. Penyimpanan data yang akan diproses dilakukan dengan menggunakan file. Hasil dari Tugas Akhir ini adalah membuktikan penerapan strategi implementasi multithreading, bentuk algoritma iteratif, pembatasan pencarian dan penyimpanan menggunakan file dapat membuat PrefixSpan berjalan hingga selesai dan juga meningkatkan kinerjanya dari segi waktu proses.