On incremental maintenance of 2-hop labeling of graphs
Citations Over TimeTop 10% of 2008 papers
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. Recently, 2-hop labeling has been proposed to index large collections of XML and/or graphs for efficient reachability tests. However, there has been few work on updates of 2-hop labeling. This is compounded by the fact that Web data changes over time. In response to these, this paper studies the incremental maintenance of 2-hop labeling. We identify the main reason for the inefficiency of updates of existing 2-hop labels. We propose two updatable 2-hop labelings, hybrids of 2-hop labeling, and their incremental maintenance algorithms. The proposed 2-hop labeling is derived from graph connectivities, 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. The main conclusion is that there is a natural way to spare some index size for update performance in 2-hop labeling.
Related Papers
- → On the reachability properties of continuous-time positive systems(2008)8 cited
- → Improving Reachability Analysis of Infinite State Systems by Specialization(2011)7 cited
- → Reachability and reverse reachability analysis of CFSMs(1996)
- → On reachability and reverse reachability analysis of communicating finite state machines(2002)
- Configuration Optimizing of Repairable Spare Parts for Mission-Oriented(2005)