Categories and Subject Descriptors

Our world today is generating huge amounts of graph data such as social networks, biological networks, and the semantic web. Many of these real-world graphs are edge-labeled graphs, i.e., each edge has a label that denotes the relationship between the two vertices connected by the edge. A fundamental research problem on these labeled graphs is how to handle the label-constraint reachability query: Can vertex u reach vertex v through a path whose edge la-bels are constrained by a set of labels? In this work, we introduce a novel tree-based index framework which utilizes the directed max-imal weighted spanning tree algorithm and sampling techniques to maximally compress the generalized transitive closure for the la-beled graphs. An extensive experimental evaluation on both real and synthetic datasets demonstrates the efficiency of our approach in answering label-constraint reachability queries