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

Authors

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

Keywords

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

Document Type

Article

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.

First Page

141

Last Page

148

Page Range

141-148

Issue

2

Volume

5

Digital Object Identifier (DOI)

10.21831/elinvo.v5i2.28326

Source

https://journal.uny.ac.id/index.php/elinvo/article/view/28326

Recommended Citation

P. Setialana and M. N. Ardiansyah, "Traversal Struktur Data Bipartite Graph dalam Graph Database menggunakan Depth-First Search,", vol. 5, no. 2, pp. 141 - 148, Dec 2020.

The definitive version is available at https://doi.org/10.21831/elinvo.v5i2.28326

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