On incremental maintenance of 2-hop labeling of graphs

Ramadhana Bramandia*, Byron Koon Kau Choi, Wee Keong Ng

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

24 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationWWW '08: Proceedings of the 17th international conference on World Wide Web
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Print)9781605580852
Publication statusPublished - 21 Apr 2008
Event17th International Conference on World Wide Web, WWW 2008 - Beijing, China
Duration: 21 Apr 200825 Apr 2008

Publication series

NameProceeding of International World Wide Web Conference


Conference17th International Conference on World Wide Web, WWW 2008
Internet address

Scopus Subject Areas

  • Computer Networks and Communications

User-Defined Keywords

  • 2-hop
  • Graph Indexing
  • Incremental Maintenance
  • Reachability Test


Dive into the research topics of 'On incremental maintenance of 2-hop labeling of graphs'. Together they form a unique fingerprint.

Cite this