Traversal Struktur Data Bipartite Graph dalam Graph Database menggunakan Depth-First Search

Pradana Setialana, Universitas Negeri Yogyakarta, Indonesia
Muhammad Nurwidya Ardiansyah, Universitas Negeri Yogyakarta, Indonesia

Abstract


Bipartite graph merupakan satu bentuk graph yang dapat digunakan dalam membentuk sebuah strukur data yang saling berelasi namun memiliki karakteristik dengan dua jenis node yang berbeda seperti data hubungan keluarga atau data pohon keluarga. Dalam menyimpan struktur data bipartite graph ke sebuah database dapat digunakan graph database dengan konsep dimana node saling saling terhubung dengan node lainnya. Bipartite graph yang dikombinasikan dengan graph database menghasilkan solusi yang tepat dalam menyimpan data berelasi dengan dua jenis node yang berbeda. Namun dalam solusi tersebut menimbulkan permasalahan baru mengenai pencarian atau penelusuran (traversal) terhadap data yang terdapat dalam struktur data tersebut. Tujuan dari penelitian ini adalah mengembangkan algoritma yang dapat digunakan dalam penelusuran (traversal) data pada struktur bipartite graph dalam graph database. Algoritma yang dikembangkan adalah terapan dari algoritma depth-first search (DFS) yang telah dimodifikasi sehingga dapat digunakan dalam penelusuran (traversal) data pada bipartite graph dalam graph database. Hasil pengujian terhadap algoritma tersebut yang telah diimplementasikan ke dalam program terhadap data yang ada pada satu garis ikatan keluarga besar yaitu keluarga “George Washington /CASSIDY/” pada 30 kali percobaan dengan satuan waktu nanosecond yaitu 10-9 detik menunjukkan waktu maksimal yang didapat sebesar 42831 nanosecond, waktu minimal 5150 nanosecond, dan didapat rata-rata waktu penelusuran sebesar 9407,93 nanosecond.


Keywords


struktur data, bipartite graph, graph database, graph traversal, depth-first search

Full Text:

PDF

References


R. Diestel, GraphTheory, vol. 3, no. 1. Springer, 2016.

L. Lan, S. Ju, and H. Jin, “Anonymizing social network using bipartitegraph,” Proc. -2010 Int. Conf. Comput. Inf. Sci. ICCIS 2010, pp. 993–996, 2010, doi: 10.1109/ICCIS.2010.245.

A. Bezerianos, P. Dragicevic, J. D. Fekete, J. Bae, and B. Watson, “GeneaQuilts: A system for exploring large genealogies,” IEEE Trans. Vis. Comput. Graph., vol. 16, no. 6, pp. 1073–1081, 2010, doi: 10.1109/TVCG.2010.159.

P.Setialana, T. B. Adji, and I. Ardiyanto, “Analisis BipartiteGraph, Ore-Graphdan P-Graphuntuk Struktur Data Genealogy dalam GraphDatabase,” in The 9th National Conference on Information Technology and Electrical Engineering, 2017, pp. 173–180.

Z. J. Zhang, “GraphDatabases for Knowledge Management,” IT Prof., vol. 19, no. 6, pp. 26–32, 2017, doi: 10.1109/MITP.2017.4241463.

R. Angles and C. Gutierrez, “Survey of graphdatabasemodels,” ACM Comput. Surv., vol. 40, no. 1, pp. 1–39, 2008, doi: 10.1145/1322432.1322433.

I. Robinson, J. Webber, and E. Eifrem, GraphDatabases. Sebastopol: O’Reilly Media, Inc, 2015.

D. Shimpi, “An overview of GraphDatabases,” IJCA Proc. Int. Conf. Recent Trends Inf. Technol. Comput. Sci. 2012, vol. ICRTITCS, no.3, pp. 16–22, 2013.

R. Kumar Kaliyar, “Graphdatabases: A survey,” Int. Conf. Comput. Commun. Autom. ICCCA 2015, pp. 785–790, 2015, doi: 10.1109/CCAA.2015.7148480.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009




DOI: https://doi.org/10.21831/elinvo.v5i2.28326

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Elinvo (Electronics, Informatics, and Vocational Education)

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Our Journal indexed by:

ISSN 2477-2399 (online) || ISSN 2580-6424 (print)

View My Stats

Flag Counter