On incremental maintenance of 2-hop labeling of graphs

• Main Author: Bramandia Ramadhana
• Other Authors: Choi Koon Kau, Byron
• Format: Theses and Dissertations
• Language: English
• Published: 2010
• Subjects: DRNTU::Engineering::Computer science and engineering::Information systems
• Online Access: https://hdl.handle.net/10356/42234
• Institution: Nanyang Technological University

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.