- Title
- Computing label-constraint reachability in graph databases
- Creator
- Jin, Ruoming; Hong, Hui; Wang, Haixun; Ruan, Ning; Yang, Xiang
- Date
- 2010
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/76113
- Identifier
- vital:7507
- Identifier
-
https://doi.org/10.1145/1807167.1807183
- Abstract
- 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 labels are constrained by a set of labels? In this work, we introduce a novel tree-based index framework which utilizes the directed maximal weighted spanning tree algorithm and sampling techniques to maximally compress the generalized transitive closure for the labeled graphs. An extensive experimental evaluation on both real and synthetic datasets demonstrates the efficiency of our approach in answering label-constraint reachability queries.
- Relation
- SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,
- Rights
- This metadata is freely available under a CCO license
- Subject
- Generalized transitive closure; Hoeffding and bernstein bounds; Label-constraint reachability; Maximal directed spanning tree
- Reviewed
- Hits: 767
- Visitors: 773
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|