document: On incremental maintenance of 2-hop labeling of graphs 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 .
doc_bio_tags: O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O