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.
DOI: 10.32657/10356/42234
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Theses

Files in This Item:
File Description SizeFormat 
BramandiaRamadhana09.pdf2.23 MBAdobe PDFThumbnail

Page view(s) 50

Updated on Jun 23, 2021

Download(s) 20

Updated on Jun 23, 2021

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.