Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
kent1333472725.pdf (527.93 KB)
ETD Abstract Container
Abstract Header
Computing Label-Constraint Reachability in Graph Databases
Author Info
HONG, HUI
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=kent1333472725
Abstract Details
Year and Degree
2012, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
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.
Committee
RUOMING JIN (Advisor)
Peyravi Hassan (Committee Member)
YE ZHAO (Committee Member)
Pages
53 p.
Subject Headings
Computer Science
Keywords
reachability
;
graph databases
;
algorithm
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
HONG, H. (2012).
Computing Label-Constraint Reachability in Graph Databases
[Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1333472725
APA Style (7th edition)
HONG, HUI.
Computing Label-Constraint Reachability in Graph Databases.
2012. Kent State University, Master's thesis.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=kent1333472725.
MLA Style (8th edition)
HONG, HUI. "Computing Label-Constraint Reachability in Graph Databases." Master's thesis, Kent State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=kent1333472725
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
kent1333472725
Download Count:
732
Copyright Info
© 2012, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.