dc.contributor.authorBramandia Ramadhana
dc.identifier.citationBramandia, R. (2009). On incremental maintenance of 2-hop labeling of graphs. Master’s thesis, Nanyang Technological University, Singapore.
dc.description.abstractRecent interests on XML, Semantic Web, and Web ontology, among other topics, have sparked a renewed interest on graph-structured databases. A fundamental query on graphs is the reachability test of nodes. This thesis includes a survey on various indexes to optimize reachability tests. The focus of this thesis is 2-hop labeling indexing method which was recently proposed to index large collections of XML and/or graphs for efficient reachability tests. In particular, we note that there has been few works on 2-hop labeling in dynamic setting where the graph is frequently updated. This is compounded by the fact that data may change over time. In response to these, this thesis studies the incremental maintenance of 2-hop labeling. We analyze the main reason for the inefficiency of updates of existing 2-hop labels. Based on our analysis, we propose node-separation property that leads to efficient incremental maintenance. Subsequently, we present novel incremental maintenance algorithms for 2-hop labels. Wepropose three updatable 2-hop labelings, hybrids of 2-hop labeling that satisfies node-separation property. The proposed 2-hop labeling is derived from graph connectivity, as opposed to SET COVER which is used by all previous work. Our experimental evaluation illustrates the space efficiency and update performance of various kinds of 2-hop labeling. Our results show that the incremental maintenance algorithm can be two orders of magnitude faster than previous methods and the size of our 2-hop labeling can be comparable to the existing 2-hop labeling.en_US
dc.format.extent110 p.en_US
dc.subjectDRNTU::Engineering::Computer science and engineering::Information systemsen_US
dc.titleOn incremental maintenance of 2-hop labeling of graphsen_US
dc.contributor.researchCentre for Advanced Information Systemsen_US
dc.contributor.schoolSchool of Computer Engineeringen_US
dc.contributor.supervisorChoi Koon Kau, Byron
dc.description.degreeMASTER OF ENGINEERING (SCE)en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record