.jpg)
Refereed Papers
Track: XML I
Paper Title:
On Incremental Maintenance of 2-hop Labeling of Graphs
Authors:
- Ramadhana Bramandia(Nanyang Technological University)
- Byron Choi(Nanyang Technological University)
- Wee Keong Ng(Nanyang Technological University)
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, {it 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 {it 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 {it 2-hop} labeling. We identify the main reason for the inefficiency of updates of existing {it 2-hop} labels. We propose two updatable {it 2-hop} labelings, hybrids of {it 2-hop} labeling, and their incremental maintenance algorithms. The proposed {it 2-hop} labeling is derived from graph connectivities, as opposed to {sc set cover} which is used by {em all} previous work. Our experimental evaluation illustrates the space efficiency and update performance of various kinds of {it 2-hop} labeling. The main conclusion is that there is a natural way to spare some index size for update performance in {it 2-hop} labeling.
Inquiries can be sent to:
