Analisis dan Implementasi Graph Indexing Pada Graph Database Menggunakan Algoritma GraphGrep

Abstract

Graph database adalah basis data yang menggunakan struktur graf untuk merepresentasikan dan mengelola data. Sebagian besar basis data yang digunakan basis data relasional karena penggu naannya yang relatif mudah dan mendukung banyak tipe data. Namun, untuk tipe data tertentu seperti tipe data molekul yang memiliki ciri vertex berlabel dan edge yang tidak berarah, basis data relasional kurang begitu efektif digunakan karena tipe data tersebut memiliki keterkaitan secara independen. Untuk menangani hal tersebut, basis data graf atau biasa disebut graph database adalah solusi yang paling tepat. Pada tugas akhir ini akan mengaplikasikan graph indexing menggunakan algoritma GraphGrep. GraphGrep adalah metode yang paling tepat untuk studi kasus data bertipe molekul. Karena GraphGrep menganggap setiap node yang ada di graph database mempunyai nomor (id-node) dan label (label-node) Sehingga sangat cocok untuk tipe data molekul. GraphGrep menggunakan hash table (fingerprint) sebagai index, membandingkan fingerprint database dengan fingerprint query untuk mem-filter database dan menggunakan algoritma Ullman untuk melakukan subgraph matching. Dari penelitian ini diharapkan mampu menerapkan algoritma GraphGrep pada graph indexing dengan menggunakan dataset bertipe molekul serta menganalisis performansi yang dihasilkan.

Kata kunci: graph, graph database, graph indexing, GraphGrep, subgraph matching, backtrack, Ullman