Penerapan Algoritma DBFS (Distributed Breadth-First Search) untuk Graph Database Partition

ANITA DWI JAYANTI

Informasi Umum

Kode

16.04.722

Klasifikasi

518.1 - Algorithms

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Graph Theory

Dilihat

250 kali

Informasi Lainnya

Abstraksi

Terdapat dua kekurangan pada massive graph yang diimplementasikan hanya menggunakan satu komputer yaitu masalah waktu pencarian dan keterbatasan memori. Setiap komputer memiliki keterbatasan memori sehingga implementasi massive data graf dapat menurunkan performansi komputer. Kedua kekurangan yang telah dijelaskan sebelumnya dapat diatasi dengan distribusi data. Distribusi data dilakukan dengan cara mempartisi graph database yang ada. Terdapat berbagai teknik partisi untuk graph database. Pada tugas akhir ini, partisi graph database diimplementasikan menggunakan teknik pembagian graf atau partisi dengan menggunakan metode minimum communication partitioning (MCP). MCP merupakan metode partisi berdasarkan algoritma Distributed Breadth-First Search (DBFS). Distribusi data dilakukan pada shared-nothing parallel system. Terdapat tiga fungsionalitas pada sistem yang dibangun dengan distribusi data yaitu mencari keberadaan letak ketetanggan vertex (pola), mencari tetangga pada tiap node (lintas partisi), dan mencari waktu pencarian berdasar id vertex pada tiap node. Tujuan dari tugas akhir ini adalah untuk mengetahui cara implementasi distribusi data menggunakan teknik partisi MCP dan untuk mengetahui performansi query response time pada sistem yang menerapkan distribusi data dan sistem yang tidak menerapkan distribusi data.

Kata Kunci: Graph Database, distribusi data, partisi graph database, massive graph, DBFS, MCP