Implementasi Prinsip MDL untuk Kompresi Graph Database Menggunakan Algoritma Greedy

Abstract

Graph secara konsep merupakan abstraksi yang secara fundamental telah lama dipakai, yang memungkinkan untuk memodelkan pada sistem di dunia nyata. Begitu pula pada data, data jenis apapun dapat dimodelkan relasi antar data tersebut menggunakan graph. Graph database diadopsi untuk memudahkan dan membantu dalam memahami, memodelkan, serta menganalisis suatu proses. Graph database sangat cocok digunakan pada data bersifat tidak terstruktur dan semi terstruktur dibanding relational database yang mana memiliki kelemahan jika data dan ukuran tabel bertambah menyebabkan kemungkinan join antar tabel sangat besar. Dalam aplikasinya jumlah data pada graph database semakin lama akan berkembang semakin besar menjadi jutaan bahkan miliaran node dan edge, sehingga cost untuk untuk melakukan analisa dan visualisasi graph databse menjadi sangat besar untuk kemampuan sistem saat ini. Untuk menyelesaikan permasalahan tersebut maka diperlukan suatu metode untuk mengurangi ukuran dari graph tetapi tetap menyimpan informasi-informasi penting dari graph. Dengan menerapkan prinsip Rissaenen’s Minimum Description Length (MDL) dan melakukan penggabungan secara greedy serta mengombinasikan dengan representasi graph G yang terdiri dari Graph Summary dan sebuah set Correction, maka dapat dihasilkan graph database yang dikompres dengan baik.

Kata Kunci: graph database, graph summarization, graph representation, MDL principle, lossles, lossy, compression, greedy, Rissaenen’s Minimum Description Length