Please use this identifier to cite or link to this item:
|Title:||On incremental maintenance of 2-hop labeling of graphs||Authors:||Bramandia Ramadhana||Keywords:||DRNTU::Engineering::Computer science and engineering::Information systems||Issue Date:||2009||Source:||Bramandia, R. (2009). On incremental maintenance of 2-hop labeling of graphs. Master’s thesis, Nanyang Technological University, Singapore.||Abstract:||Recent 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.||URI:||https://hdl.handle.net/10356/42234||DOI:||10.32657/10356/42234||Fulltext Permission:||open||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SCSE Theses|
Page view(s) 50378
Updated on Jun 23, 2021
Updated on Jun 23, 2021
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.